平面拓扑图论的突破：花束受限部分对偶多项式的插值与对数凹性

《Discrete Mathematics》：Several new results on partial-twuality polynomials

这篇研究在拓扑图论领域取得了重要进展。它针对 Gross、Mansour 和 Tucker 提出的两个核心问题，系统刻画了平面花束图（bouquet）的五类部分对偶多项式（partial-twuality polynomials）的插值（interpolation）与对数凹性（log-concavity）行为，并构建了一系列不可定向的带图（ribbon graph）反例，证伪了一个关于部分对偶多项式（partial-* polynomial）的重要猜想，深化了对这类多项式组合与几何性质的理解。

　　

亮点

我们部分解决了一个问题，并证伪了由 Gross、Mansour 和 Tucker 最初提出的一个猜想。我们首先刻画了五类平面带图（ribbon graphs）的花束受限部分对偶多项式（bouquet-restricted partial-twuality polynomials）的插值（interpolating）或对数凹（log-concave）行为。随后，我们引入了一个无限族的不可定向带图（non-orientable ribbon graphs）作为反例，其部分对偶多项式（partial-dual polynomials）表现出插值性，但对应的偶次度或奇次度序列却不符合对数凹性。

引言

在[18]中，Wilson 证明了两个著名的对偶算子 （几何对偶）和 ×（佩特里对偶）生成了一组六个带图算子。具体而言，和 × 的任何组合都等价于五个算子之一 、×、×、×、×* 或恒等算子。Abrams 和 Ellis-Monaghan [1] 随后引入术语“对偶性”（twualities）来指代这五个算子。Chmutov [4] 引入了关于带图 G 的边子集 A 的部分对偶（partial duality）概念，旨在统一琼斯-考夫曼（Jones-Kauffman）和博洛巴斯-里奥丹（Bollobás-Riordan）多项式之间的各种联系。给定一个带图 G 及其边带子集 A ? E(G)，关于 A 的部分对偶 G^＊|A是通过沿生成带子图 (V(G), A) 的每个边界分量将一张圆盘粘贴到 G 上（这些圆盘将成为 G^＊|A的顶点圆盘），移除 G 所有顶点圆盘的内部，并保持边带子不变而得到的带图。

Ellis-Monaghan 和 Moffatt [7] 后来将这种部分对偶构造推广到其余四个算子，称它们为部分对偶性（partial-twualities）。设 G 为一个带图且 A ? E(G)。那么 G 关于 A 的部分佩特里对偶（partial Petrial） G^×|A[7] 是通过对 A 中的每条边添加半扭转（adding a half-twist）而得到的带图。由此可知，部分佩特里对偶（partial Petrie duality）保留了底图（underlying graph）。

图1显示了 * 和 × 在一条边 e 上的作用。在图1（a）中，如果 e 的两端关联于同一顶点（两种不同的识别方法分别对应可定向和不可定向的环），则 e 是一个环；如果其两端关联于两个不同的顶点，则 e 是一个非环。如图所示，尽管面或顶点的数量可能改变，边的数量在部分对偶下是不变的。我们约定 G^*×|A= (G^＊|A)^×|A，类似地定义 ×* 和 ×。我们假定读者对图论和拓扑图论有基本理解，关于未定义的术语，请参阅 [2]、[8]、[12]、[17]。

我们用 v(G), e(G), f(G) 和 c(G) 分别表示带图 G 的顶点数、边数、边界分量数和连通分量数。符号 ε(G) 表示 G 的欧拉亏格（Euler genus），定义为 ε(G) = 2c(G) ? v(G) + e(G) ? f(G)。亏格是嵌入图（embedded graphs）的一个拓扑不变量，是一个广泛的主题，起着至关重要的结构作用。如果 G 不可定向，则其欧拉亏格等于其亏格；如果 G 可定向，则等于其亏格的两倍。欧拉亏格为0的带图称为平面带图。类似于枚举图按亏格所有嵌入的亏格多项式（genus polynomial），Gross、Mansour 和 Tucker [10] 为带图 G 引入了部分多项式（partial-polynomial），定义为 E_G^*(z) = Σ_A?E(G)z^ε(G*|A)，其中 * ∈ {*, ×, ×, ×, ×}。

一个花束（bouquet）被定义为一个只有一个顶点的带图。设 A 是一个带图 G 的某个生成树（spanning tree）的边集。那么对于 * ∈ {, ×, ×, ×}，G^•|A是一个花束 [10]。随后，Gross、Mansour 和 Tucker [10] 引入了花束受限部分多项式（bouquet-restricted partial-• polynomial），其定义是将求和限制在那些使得 G^•|A成为花束的子集 A ? E(G) 上。该多项式记为 B_G^•(z)。

如果一个多项式中介于其最高和最低次项之间的所有项的系数都是非零的，则称该多项式是插值的（interpolating）。如果多项式 Σa_izⁱ满足不等式 a_i-1a_i+1≤ a_i²（其中 i>0），则称其为对数凹（log-concave）的。偶次（奇次）插值与偶次（奇次）对数凹的定义类似。若多项式所有非零系数均对应于偶次（奇次）项，则称其为偶（奇）多项式。一个生成树 T 的补 G-E(T) 称为余树（cotree），记为 T^c。G 的零度（nullity），记作 μ(G)，定义为 μ(G) = e(G) ? v(G) + c(G)。

1989年，Gross、Robbins 和 Tucker [11] 证明了圆花束的亏格多项式的对数凹性，并猜想该性质对所有图都成立。Mohar [16] 在2026年构造了多个反例族，从而证伪了这一一般性猜想。受其早期工作中观察到的花束与对数凹性之间特定联系的启发，Gross、Mansour 和 Tucker 开始研究花束受限部分*多项式。

Chmutov [4] 指出部分对偶保持可定向性。对于一个可定向带图 G，其欧拉亏格是亏格的两倍，这迫使部分对偶多项式 E_G^*(z) 为偶多项式，因而不是插值的。这与部分×多项式形成了对比：Gross 等人 [10] 证明了 E_G^×(z) 是插值的但不是对数凹的。现在考虑花束受限多项式 B_G^×(z)。由于部分佩特里对偶（partial Petrial）保留了底图，G^×|A是花束当且仅当 G 本身是花束。因此，如果 G 不是花束，则 B_G^×(z) = 0。反之，如果 G 是花束，则 B_G^×(z) 与部分×多项式 E_G^×(z) 相同，因此是插值的。总之，B_G^×(z) 要么是插值的，要么为零。

本文重点讨论 Gross、Mansour 和 Tucker 提出的两个问题：一个关于花束受限部分多项式 B_G^•(z)，见第2节；另一个是关于部分多项式 E_G^*(z) 的猜想，见第3节，陈述如下。

问题 1.1 [10]

确定使得多项式 B_G^•(z) 是插值或对数凹的带图 G 的类别。理想情况下，将花束受限多项式的行为与完全多项式联系起来。

我们讨论关于平面带图的问题 1.1，如定理 1.2 所述。

定理 1.2

设 G 为一个平面带图。那么

• •
  (1) B_G^*(z) 是偶多项式且是偶次插值的。
• •
  (2) 若 G 是边数为 n 的花束，则 B_G^×(z) = (1+z)ⁿ，否则为 0。因此，B_G^×(z) 是对数凹的。
• •
  (3) 若 G 是二分的（bipartite），则 B_G^×*(z) 是偶多项式且是偶次插值的；若 G 是非二分的且所有余树均是无环的，则 B_G^×*(z) 是插值的。
• •
  (4) B_G^×(z) = C z^1+e(G)?f(G)，其中 C 是使得 G^×|A成为花束的边子集 A 的数量。
• •
  (5) B_G^*×(z) 可能不是插值的。

定理 1.2 的证明将在第2节中按其陈述顺序给出。我们注意到，定理 1.2 (4) 实际上适用于所有带图，而不仅仅是平面带图。

猜想 1.3 [9]

对于任何不可定向带图的部分多项式 E_G^*(z)，其偶次度序列 {a_i/2} 和奇次度序列 {a_(i+1)/2} 都是对数凹的。*

Gross 等人 [10] 给出了一个可定向带图，其多项式 E_G^*(z) 不是偶次对数凹的。在第3节中，我们提供了一个无限族的不可定向带图作为猜想 1.3 的反例。这些带图的多项式 E_G^*(z) 是插值的，但它们的偶次度或奇次度序列不是对数凹的。

第2节片段

花束受限多项式 B_G^•(z) 的插值行为与对数凹性

如果一个带图 G 是不连通的，则 B_G^•(z) 等于 0。因此，除非特别说明，本文讨论的所有带图都假定是连通的。我们用 G[A] 表示由边集 A 诱导的 G 的生成子图（spanning subgraph）。由于频繁使用，在不会引起歧义的情况下，我们将简单地用 A 来表示 G[A]。为了方便起见，在单元素集的情况下，我们省略集合的括号。

带图 G 的一个生成子图如果恰好包含一个...

第3节片段

关于猜想 1.3 的反例

本节研究关于部分多项式 E_G^*(z) 的猜想 1.3*。花束的带符号轮换（signed rotation）[19] 是关联于该顶点的半边（half-edges）的一个循环序。如果边是可定向环，我们为其两个半边分配相同的符号（+ 或 ?）。否则，我们分配不同的符号（+ 和 ?）。注意，符号 + 是隐含的，在记法中通常被省略。

引理 3.1 [9]

设 G 是一个花束，且 A ? E(G)。那么 ε(G^＊|A) = ε(A) + ε(A^c)。

命题 3.2

设 H₁是一个具有带符号轮换 (?1, 2, 3, 4, 5, ... 的花束...

结论

在第3节中，带图 H₁作为 [9] 中猜想 5.3 和 [10] 中猜想 8.1 的一个反例。设 G 是一个具有带符号轮换 (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 5, 8, 3, 7, 10, 4, 9, 2, 6) 的花束。通过计算，我们得到 E_G^*(z) = 96z¹⁰+ 588z⁸+ 314z⁶+ 24z⁴+ 2z²。这个多项式是 [9] 中猜想 5.1 的一个反例，由不等式 314·2 > 24²可证。值得注意的是，上述三个猜想已被所呈现的不同例子证伪。