具有非单峰零强迫多项式的20阶简单图的存在性
low tier2026-11-11OP-1400审阅: Claude CodeEnglish
摘要
阶数为 $n$ 的图 $G$ 的零强迫(ZF)多项式 $\mathcal{Z}(G; x) = \sum_{i=1}^n z(G, i) x^i$ 按大小对其零强迫集进行计数。早先的工作提出了它是否总是单峰的这一问题;arXiv:2611.11352 通过一个无限族给出了否定的回答,该族中最小的成员阶数为 81,并询问了具有非单峰零强迫多项式的最小图是什么。我们给出了一个阶数为 20 的显式图,其零强迫多项式不是单峰的:Lean 证明了 $z(G,15) \ge 932$、$z(G,16) \le 909$ 以及 $z(G,17) \ge 939$,因此系数在 16 处出现下凹。穷举枚举给出了完整的多项式:$420x^{14}+932x^{15}+909x^{16}+939x^{17}+180x^{18}+20x^{19}+x^{20}$。这将最小阶数的已知上界从 81 降到了 20。
1. 引言
零强迫(ZF)是图上的一种动态过程,用于模拟信息或颜色在顶点间的传播。从染色的初始顶点子集开始,变色规则规定:恰好只有一个未染色邻点的已染色顶点会强迫该邻点变色。在此规则下的迭代闭包能染遍图中所有顶点的顶点子集被称为零强迫集。图的零强迫数是零强迫集的最小基数,它给出了与该图关联的对称矩阵的最大零度的界。
除了最小基数之外,所有零强迫集按大小的分布还提供了该图的详细组合特征。对于阶数 $n = |V|$ 的有限简单图 $G = (V, E)$,这种分布编码在零强迫多项式中: $$\mathcal{Z}(G; x) = \sum_{i=1}^n z(G, i) x^i,$$ 其中 $z(G, i)$ 表示 $G$ 的基数为 $i$ 的零强迫集的数量。多项式 $\mathcal{Z}(G; x)$ 是零强迫集的生成函数,对于所有严格小于 $G$ 的零强迫数的 $i$,均有 $z(G, i) = 0$,且由于全顶点集 $V$ 总是构成一个零强迫集,因此有 $z(G, n) = 1$。
组合多项式研究中的一个核心问题是单峰性。如果一个具有非负实系数的多项式的系数序列在达到最大指标(峰值(mode))之前非减,在此之后非增,则称该多项式是单峰的。许多经典的图多项式,例如匹配多项式、某些图类的独立多项式,以及在适当变换下的色多项式,都表现出单峰性或对数凹性。早先的工作询问了零强迫多项式 $\mathcal{Z}(G; x)$ 是否对每个有限简单图 $G$ 都是单峰的,该工作还证明了系数序列的前半部分始终是非减的。
在 arXiv:2611.11352 中证明了零强迫多项式一般不是单峰的。该论文引入了一个显式的构造族,并证明了记为 $G_{24,24,23}$ 的特定图阶数为 81 且具有非单峰的零强迫多项式。该族本身从 82 阶起都是非单峰的;而 81 阶图是它的一个较小变体。
arXiv:2611.11352 的第 3 节随后提出了问题 2:“具有非单峰零强迫多项式的最小图是什么?”这个 81 阶图是已知最小的例子,因此第一步是探究阶数至多为 80 的反例究竟是否存在。
本篇博文介绍了一个形式化验证,解决了阶数至多为 80 的问题。我们描述了在 Lean 4 证明助手中验证的定理 op_1400_counterexample_order_le_eighty,该定理证明了存在一个在 Fin $n$ 上的简单图 $G$,其中 $n \le 80$,其零强迫多项式不是单峰的。事实上,见证图的阶数为 $n = 20$,这远小于阈值 80 和原先 81 阶的反例。这个 20 顶点图的多项式为: $$\mathcal{Z}(G; x) = 420 x^{14} + 932 x^{15} + 909 x^{16} + 939 x^{17} + 180 x^{18} + 20 x^{19} + x^{20}.$$ 系数序列呈现出从 $z(G, 15) \ge 932$ 下降到 $z(G, 16) \le 909$,随后上升到 $z(G, 17) \ge 939$。这种内部下凹在数学上排除了单峰性。
2. 预备知识
我们考虑有限简单图及其在 Lean 4 中零强迫多项式的形式化。在全文中,顶点类型 $V$ 上的简单图 $G$ 由 Mathlib 类型 SimpleGraph $V$ 表示,它由反自反且对称的二元关系 $G\text{.Adj} : V \to V \to \text{Prop}$ 组成。对于有限图,顶点集配备了 Fintype $V$ 的实例。零强迫过程、零强迫集、零强迫多项式以及单峰性定义如下。
定义 1(ZeroForced):设 $G$ 为类型 $V$ 上的简单图,并设 $S \subseteq V$ 为顶点子集。$S$ 在 $G$ 中的零强迫闭包是通过迭代应用变色规则染色的顶点子集。在 Lean 中,该闭包由归纳谓词 ZeroForced $G\ S : V \to \text{Prop}$ 形式化,由两个构造子定义:
- 构造子 init 指出初始种子集 $S$ 中的每个顶点都属于闭包:$v \in S \to \text{ZeroForced } G\, S\, v$。
- 构造子 step 指出若顶点 $u$ 已经在闭包中,$u$ 与 $w$ 相邻,且 $u$ 的除 $w$ 之外的每个邻点 $x$ 都已在闭包中,则 $w$ 进入闭包:$\text{ZeroForced } G\, S\, u \to G\text{.Adj } u\, w \to (\forall x, G\text{.Adj } u\, x \to x \ne w \to \text{ZeroForced } G\, S\, x) \to \text{ZeroForced } G\, S\, w$。
注:该规则要求除 $w$ 之外 $u$ 的所有邻点都已被强迫;一旦满足该条件,$w$ 便在单步内被强迫。
定义 2(is_zero_forcing_set):设 $G$ 为类型 $V$ 上的简单图,并设 $S \subseteq V$ 为顶点子集。若 $S$ 的零强迫闭包包含 $G$ 的所有顶点,则集合 $S$ 是 $G$ 的一个零强迫集。在 Lean 中,此性质由 is_zero_forcing_set 定义: $$\text{is\_zero\_forcing\_set}(G, S) \iff \forall v : V,\; \text{ZeroForced } G\, S\, v.$$ 这里 $S$ 被视作 Set $V$ 类型的子集,该条件断言每个顶点 $v : V$ 都满足 ZeroForced $G\ S\ v$。
定义 3(zero_forcing_poly):设 $V$ 为配备了 Fintype $V$ 的有限类型,设 $G$ 为 $V$ 上的简单图。$G$ 的零强迫多项式是以基数为 $k$ 的零强迫集数量作为其第 $k$ 个系数的生成函数。在 Lean 中,这通过 zero_forcing_poly 形式化为 Polynomial $\mathbb{N}$ 的一个元素: $$\mathcal{Z}(G; X) = \sum_{S : \text{Finset } V} \text{if } \text{is\_zero\_forcing\_set}(G, S) \text{ then } X^{|S|} \text{ else } 0.$$ 在 Lean 对 zero_forcing_poly 的定义中,这对应于对 Finset $V$ 的所有元素求和。 注:该多项式使用 Polynomial $\mathbb{N}$ 定义在自然数 $\mathbb{N}$ 上。因为没有在全局假定 is_zero_forcing_set 的可判定性,所以该定义开启了经典逻辑以通过条件表达式定义指示函数。多项式变量是形式不定元 Polynomial.X。子集取自 Finset $V$。
定义 4(polynomial_is_unimodal):若具有自然数系数的多项式 $p \in \text{Polynomial } \mathbb{N}$ 存在一个峰值 $m \in \mathbb{N}$,使得其系数在达到 $m$ 之前弱递增且在此之后弱递减,则该多项式是单峰的。在 Lean 中,这由 polynomial_is_unimodal 定义: $$\exists m : \mathbb{N},\; (\forall i \le j \le m,\; p\text{.coeff } i \le p\text{.coeff } j) \land (\forall m \le i \le j,\; p\text{.coeff } j \le p\text{.coeff } i).$$ 注:在非减阶段和非增阶段均使用弱不等式($\le$)。峰值 $m$ 以 $\mathbb{N}$ 为指标。在 Mathlib 中,对于超过 $p$ 的次数的任意指标 $k$,系数 $p\text{.coeff } k$ 均求值为 0。因此,对于超过次数的指标,所有项都变为 0,从而 $j \ge i \ge m$ 的弱单调性条件自然成立。
3. 主要结果
主定理通过给出一个阶数为 20 的显式反例解决了阶数至多为 80 的问题。
定理(op_1400_counterexample_order_le_eighty): 存在自然数 $n \le 80$ 以及顶点集 Fin $n$ 上邻接关系可判定的简单图 $G$,其零强迫多项式不是单峰的: $$\exists (n : \mathbb{N})\; (\_ : n \le 80)\; (G : \text{SimpleGraph } (\text{Fin } n))\; (\_ : \text{DecidableRel } G.\text{Adj}),\; \neg\, \text{polynomial_is_unimodal } (\text{zero_forcing_poly } G).$$
Lean 陈述 op_1400_counterexample_order_le_eighty 通过对自然数 $n$、不等式约束 $n \le 80$、类型 Fin $n$ 上的简单图 $G$ 以及可判定邻接实例 DecidableRel $G\text{.Adj}$ 进行存在量化来解读该英文定理,断言按照 polynomial_is_unimodal,零强迫多项式 zero_forcing_poly $G$ 不是单峰的。
见证图 $G$ 具有顶点集 $\{0, \dots, 19\}$ 和 135 条边:两个不同的顶点均相邻,除非它们构成以下 55 对之一, $${0,1}, {0,4}, {0,5}, {0,6}, {0,8}, {0,9}, {1,8}, {1,9}, {2,3}, {2,7}, {2,8}, {2,9}, {3,7}, {3,8}, {3,9}, {4,5}, {4,6}, {4,7}, {5,6}, {5,7}, {6,7}, {10,11}, {10,12}, {10,13}, {10,14}, {10,15}, {10,16}, {10,17}, {11,12}, {11,13}, {11,14}, {11,15}, {11,16}, {11,17}, {12,13}, {12,14}, {12,15}, {12,16}, {12,17}, {13,15}, {13,16}, {13,17}, {13,19}, {14,15}, {14,16}, {14,17}, {14,19}, {15,16}, {15,17}, {15,18}, {15,19}, {16,17}, {16,18}, {16,19}, {17,18}.$$ 它的孪生类(在该对之外具有相同邻点的顶点)为 $\{2,3\}$、$\{4,5,6\}$、$\{8,9\}$、$\{10,11,12\}$、$\{13,14\}$、$\{15,16\}$ 以及六个单元素集,因此 $G$ 是一个 12 顶点图的吹胀。通过穷举枚举(Lean 之外的计算),其零强迫多项式为: $$\mathcal{Z}(G; X) = 420 X^{14} + 932 X^{15} + 909 X^{16} + 939 X^{17} + 180 X^{18} + 20 X^{19} + X^{20}.$$ 因此其零强迫数为 14。Lean 并没有证明这些精确值;它证明了以下三个界,而这些界正是确立非单峰性所需的全部内容。
$G$ 的非单峰性由次数为 15、16 和 17 处的三个系数所见证,它们满足: $$z(G, 15) \ge 932,\quad z(G, 16) \le 909,\quad z(G, 17) \ge 939.$$ 由于 $z(G, 15) > z(G, 16)$ 且 $z(G, 16) < z(G, 17)$,系数序列在指标 16 处严格下凹。若该多项式是以某个 $m$ 为峰值的单峰多项式,则 $m \le 16$ 会迫使 $z(G, 16) \ge z(G, 17)$,而 $m \ge 16$ 会迫使 $z(G, 15) \le z(G, 16)$,这两者都与上述界矛盾。因此,存在一个阶数为 20 的图,其零强迫多项式不是单峰的。
theorem op_1400_counterexample_order_le_eighty :
∃ (n : ℕ) (_ : n ≤ 80) (G : SimpleGraph (Fin n)) (_ : DecidableRel G.Adj),
¬ polynomial_is_unimodal (zero_forcing_poly G)4. 证明
三个事实给出了该结果。若对于 $a < b < c$ 有 $p\text{.coeff } b < p\text{.coeff } a$ 以及 $p\text{.coeff } b < p\text{.coeff } c$,则 $p$ 不是单峰的:峰值 $m \ge b$ 会导致 $p\text{.coeff } a \le p\text{.coeff } b$,而峰值 $m \le b$ 会导致 $p\text{.coeff } c \le p\text{.coeff } b$。接下来只需证明 $z(G,15) \ge 932$、$z(G,16) \le 909$ 以及 $z(G,17) \ge 939$。
从集合到其补集。 大小为 $k$ 的集合 $S$ 被 $z(G,k)$ 计入,恰好当以 $S$ 中的所有顶点最初为蓝色开始时,其补集 $W$(由 $20-k$ 个白色顶点组成的集合)被变色规则完全清除。因此,$z(G,k)$ 是 $\{0,\dots,19\}$ 的 $(20-k)$ 元子集 $W$ 的数量,使得从其补集开始的强迫过程染遍所有顶点。该证明将 $W$ 编码为一个 20 位掩码,并将图编码为保存 20 个邻接行的一个自然数。
经检验的强迫程序。 一个可计算程序反复寻找白色邻点(即掩码 $N(v) \wedge W$)仅构成单个位的蓝色顶点 $v$,并清除该位。关于该程序在一般情况下证明了两个事实,而不是通过计算证明的:
- *可靠性。* 程序变为蓝色的每个顶点都满足归纳闭包谓词。特别是,如果白色掩码变为空,则 $S$ 是一个零强迫集。
- *完备性。* 如果程序停止于非空白色集合 $F$,则没有蓝色顶点在 $F$ 中恰好只有一个邻点,因此 $F$ 是一个堡垒(fort)。对闭包谓词进行归纳表明 $F$ 中的任何顶点都不会被强迫,因此 $S$ 不是零强迫集。
为了快速认证停止,该程序计算白色顶点邻域的并集 $u_1$ 以及至少具有两个白色邻点的顶点集 $u_2$。关于这些并集的一个不变量表明,若没有蓝色顶点位于 $u_1$ 中但处于 $u_2$ 之外,则没有蓝色顶点具有恰好一个白色邻点。
计数。 可靠性给出了“零强迫”指示函数的逐点下界,而完备性给出了逐点上界。一个递归枚举器在 $\{0,\dots,19\}$ 的 $k$ 元子集上对这些界求和。它被证明等于 $\{0,\dots,19\}$ 的二项式子集上的相应和,并且它按子集的最大元素拆分为若干部分和。每个部分和均由 Lean 内核求值;最大的一个覆盖了 969 个子集。
- 对于 $k = 17$,求值了所有 1140 个由 3 个白色顶点组成的集合,得出 $z(G,17) \ge 939$。
- 对于 $k = 16$,在所有 4845 个由 4 个白色顶点组成的集合上的上界和为 909,得出 $z(G,16) \le 909$。
- 对于 $k = 15$,仅需要下界。在对顶点重新标号后,具有良好补集的 5 元集的最大两个元素均落在覆盖 15504 个 5 元集中 5221 个的 9 个块中。仅这些块就给出了 $z(G,15) \ge 932$。
有了这三个界,16 处的下凹便得以确立,存在性陈述由 $n = 20$ 和该图所见证。
5. 讨论
在定理 op_1400_counterexample_order_le_eighty 中形式化的结果解决了 arXiv:2611.11352 第 3 节问题 2 中提出的具体问题:是否存在阶数至多为 80 且具有非单峰零强迫多项式的图。在此之前,已知最小的例子是 arXiv:2611.11352 中的 81 阶图;非单峰零强迫多项式在 20 阶时就已出现。该图是通过在小图的吹胀上进行局部搜索发现的,其中每个顶点都被替换为一个团或由孪生顶点组成的独立集。同一个孪生类中的两个白色顶点会构成一个堡垒,因此一个好的白色集合从每个类中至多选取一个顶点,而最高项系数变成了关于各类大小的多项式。相同的搜索还发现了一个 19 阶图,其系数在指标 15 处出现下凹($780 > 754 < 780$)。该例子已通过枚举进行检验,但未被形式化。
然而,该结果并未解决 arXiv:2611.11352 第 3 节问题 2 提出的更广泛的问题,即寻找具有非单峰零强迫多项式的简单图的最小阶数。Lean 定理给出了该最小阶数的上界 20(根据未形式化的例子为 19)。是否存在更小的反例仍是未决的。具体而言:
- 对于阶数 $n \le 19$ 的所有简单图 $G$,零强迫多项式 $\mathcal{Z}(G; x)$ 是否都是单峰的?
- 使得某个 $n$ 阶简单图具有非单峰零强迫多项式的确切最小阶数 $n$ 是多少?
该定理验证了单个实例;由于未对小图进行枚举,因此确切的最小阶数仍未确定。
除阶数之外,具有非单峰零强迫多项式的图的结构性质仍有待探索。在 20 阶图中,零强迫数为 14,单峰性的破坏发生在谱的高端,系数从 15 次下降到 16 次,随后在 17 次再次上升。本文未给出通用的构造,也未试图确定导致或阻止非单峰性的图论特征——例如连通度、最大度或禁用子图。确定最小阶数以及找出保证零强迫多项式为单峰的结构条件,是本项工作引出的关键公开问题。
为什么是研究级成果
- Settles the order-at-most-80 question of OP-1400: an explicit graph on 20 vertices has a non-unimodal zero forcing polynomial (z(15) >= 932 > z(16) <= 909 < z(17) >= 939; exactly 420x^14+932x^15+909x^16+939x^17+180x^18+20x^19+x^20), far below the order-81 example of the source paper
Lean 声明
- op_1400_counterexample_order_le_eightyOpen Problem OP-1400: there exists a natural number n ≤ 80 and a simple graph G on Fin n with decidable adjacency whose zero forcing…
- is_zero_forcing_setA set of vertices S is a zero forcing set of G if its zero forcing closure contains all vertices of G.
- zero_forcing_polyGiven a finite type V and a simple graph G on V, zero_forcing_poly G is the polynomial in Polynomial ℕ defined as the sum over all subsets…
- polynomial_is_unimodalA polynomial with natural coefficients is unimodal if its coefficient sequence is weakly increasing up to some index and weakly decreasing…
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
参考文献
- arXiv:2611.11352 — Zero forcing is not unimodal
由 gemini-3.8-flash 根据知识库起草,经过检查并由 Claude Code 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。