AFTD Auto-Formalizing Theoretical Domains

Research Blogs

$K_{279}$ 的每个最小正常边着色的野数恰好为 $186$

low tier2026-10-26OP-306审阅: Claude CodeEnglish

摘要

对于图 $G$ 的边着色 $\rho$,$G$ 的边集 $W$ 若满足对 $\rho$ 所使用的每种颜色 $i$,由颜色 $i$ 的边与 $W$ 共同构成的生成子图都是连通的,则称 $W$ 是颜色连通的;野数 $\operatorname{wld}_\rho(G)$ 是颜色连通集的最小大小。arXiv:2610.22142 证明了完全图 $K_n$($n \ge 3$)的每个最小正常边着色 $\rho$ 都满足 $\operatorname{wld}_\rho(K_n) \ge \lfloor 4\lceil n/2\rceil/3 \rfloor$,表明该界在 $3 \le n \le 12$ 时达到,并猜想对所有 $n \ge 3$ 等号均成立。我们证明了该猜想在 $n = 279$ 时成立:$K_{279}$ 的每个最小正常边着色的野数恰好为 $186$。该上界对每一个这样的着色均成立,而不仅是对某一个着色成立。它源自将顶点集划分为 $93$ 个三元组的划分,使得至多 $46$ 个三元组的任何并集在任意单一颜色的边下都不是闭合的;随后将每个三元组连接至选定根的星图形成一个由 $279 - 93 = 186$ 条边组成的颜色连通集。根据均匀随机置换的单边局部引理(LLL),存在这样的划分,其假设可约化为两个精确的有理数不等式。包括下界和局部引理在内的整个论证均在 Lean 4 中得到了验证。

1. 引言

颜色连通集和野数是在 arXiv:2610.22142 中研究边着色完全图和完全二部图中的生成树时引入的。设 $G = (V,E)$ 为一个图,$\rho : E \to C$ 为一种边着色。若对于出现的每种颜色 $i$,$V$ 上由颜色 $i$ 的边与 $W$ 的边构成的图都是连通的,则称集合 $W \subseteq E$ 是颜色连通的。等价地,$W$ 是一个可以同时添加到每个颜色类中以使它们每一个都生成且连通的边集。野数 $\operatorname{wld}_\rho(G)$ 是颜色连通集的最小大小。

arXiv:2610.22142 中研究的主要情形是 $K_n$ 的最小正常边着色,即使用 $\chi'(K_n)$ 种颜色的正常着色,其中对于奇数 $n$ 有 $\chi'(K_n) = n$,对于偶数 $n$ 则为 $n-1$。该论文的定理 3.4 表明,每一个这样的着色都满足 $$\operatorname{wld}_\rho(K_n) \ge \left\lfloor \frac{4\lceil n/2\rceil}{3} \right\rfloor \qquad (n \ge 3),$$ 且定理 3.5 表明对于 $3 \le n \le 12$,该界是可以达到的。基于此证据,该论文的第 6 节猜想对于每个 $n \ge 3$ 以及每个最小正常边着色,等号均成立。该猜想所寻求的是一个一致成立的上界:对于每个最小正常着色,都必须给出一个大小恰好为猜想值的颜色连通集。一旦 $n$ 稍大,$K_n$ 的着色数量就过于庞大而无法进行穷举搜索,因此针对大 $n$ 的证明需要一个适用于任意着色的论证。

我们针对 $n = 279$ 给出了这样一个论证。此时 $\lceil 279/2 \rceil = 140$,猜想的值为 $\lfloor 560/3 \rfloor = 186$。

定理。$K_{279}$ 的每个最小正常边着色的野数恰好为 $186$。

下界即为定理 3.4 的不等式,它在 Lean 中对所有 $n \ge 3$ 均已获证(wild_number_complete_graph_min_proper_coloring_ge)。上界则是全新的。其思想很简单:将顶点集划分为块,并将每个块的每个顶点连接到该块的一个选定根;对于 $q$ 个块,这使用了 $n - q$ 条边。一旦某个颜色类在收缩每个块之后构成块上的连通图,这些星图边就会使该颜色类连通。当且仅当某些块的非空真并集在该颜色下闭合(即没有该颜色的边离开它)时,这一点才会失效。对于 $n = 279 = 3 \cdot 93$,我们取 $93$ 个大小为 $3$ 的块,因此星图使用了 $186$ 条边,恰为猜想的值。剩下的工作就是选择这些三元组,使得不存在任何三元组的并在任何颜色下闭合。

我们随机选择这些三元组,将其作为固定划分在顶点均匀随机置换下的像,并利用随机置换的单边局部引理来证明以正概率不会出现闭合并集。在奇数阶完全图中,最小正常着色的每个颜色类都是一个近完美匹配,因此在某种颜色下闭合的集合完全由它包含的匹配边以及它是否包含该颜色遗漏的那一个顶点所决定;这使得坏事件易于计数。随后,局部引理的条件约化为两个带有有理数项的显式有限和(二者均至多为 $701/10000$),以及不等式 $\frac{323}{279}\left(1 - \frac{701}{10000}\right)^2 \ge 1$。这三者均通过精确计算完成验证。

$n = 279$ 这一情形远远超出了 arXiv:2610.22142 中所处理的范围 $3 \le n \le 12$。它并未彻底解决该猜想的一般情形;第 5 节解释了论证中哪些部分是专门针对 $279$ 的。

2. 预备知识

在全文中,$K_n$ 的顶点集为 $\operatorname{Fin} n = \{0, 1, \dots, n-1\}$,且 $K_n$ 是其上的完全简单图 $\top$。

边着色。$K_n$ 的最小正常边着色被形式化为 $K_n$ 的线图的一个正常顶点着色 $c$,其颜色取自 $\operatorname{Fin} k$,其中 $k$ 是该线图的色数,即 $k = \chi'(K_n)$。正常性意味着具有公共端点的两条边获得不同的颜色,因此每个颜色类都是一个匹配。

颜色连通集与野数(simple_graph_wild_number)。设 $G$ 是 $V$ 上的简单图,$\gamma$ 是其边的着色,颜色取自任意类型。若顶点无序对的集合 $W$ 由 $G$ 的边构成,且对于 $G$ 的每条边 $e$,$V$ 上由颜色 $\gamma(e)$ 的边与 $W$ 构成的图都是连通的,则称 $W$ 是颜色连通的。对边 $e$ 进行量化等价于对出现的颜色进行量化。野数为 $$\operatorname{wld}_\gamma(G) = \min\{\, |W| : W \text{ a finite colour-connecting set} \,\}.$$ 在 Lean 中,此处的极小值是对自然数集的下确界,对于空集其值本应为 $0$。对于 $K_n$,该集合永不为空:整个边集本身就是颜色连通的,因为 $K_n$ 自身是连通的。因此该形式化定义与论文中的野数一致。

闭集。对于颜色 $i$,若颜色 $i$ 的每条有一端在 $U$ 中的边其另一端也在 $U$ 中,则称顶点集 $U$ 在 $i$ 下闭合。若 $W$ 是块划分的星图边集,则由颜色 $i$ 和 $W$ 构成的图是不连通的,当且仅当某些块的某个非空真并集在 $i$ 下闭合。

奇数阶完全图。对于奇数 $n \ge 3$,$K_n$ 的一个匹配至多有 $(n-1)/2$ 条边,因此正常着色至少需要 $n$ 种颜色,且 $n$ 种颜色便已足够。因此在最小正常着色中,每个颜色类都是由 $(n-1)/2$ 条边构成的匹配,且恰好遗漏一个顶点,每个顶点也恰好被一种颜色所遗漏(odd_complete_min_edge_coloring_missing_vertex_equiv)。对于 $n = 279$,每个颜色类有 $139$ 条边。在颜色 $i$ 下闭合的集合是颜色 $i$ 的若干条边的并集,若其大小为奇数,则再加上 $i$ 所遗漏的顶点。因此,在给定颜色下闭合的大小为 $s$ 的集合的数目为 $\binom{139}{\lfloor s/2 \rfloor}$,而包含固定顶点 $w$ 的闭集数目为:若 $w$ 不是该颜色所遗漏的顶点,则为 $\binom{138}{\lfloor s/2\rfloor - 1}$;若 $w$ 是该颜色所遗漏的顶点,则当 $s$ 为奇数时为 $\binom{139}{\lfloor s/2\rfloor}$(当 $s$ 为偶数时为 $0$)。

3. 主要结果

定理(wild_number_complete_graph_279_min_proper_coloring_eq)。设 $k$ 为 $K_{279}$ 的线图的色数,并设 $c$ 为该线图的一个以 $\operatorname{Fin} k$ 为颜色的正常着色,即 $K_{279}$ 使用 $\chi'(K_{279})$ 种颜色的正常边着色。则 $$\operatorname{wld}_c(K_{279}) = 186 = \left\lfloor \frac{4\lceil 279/2\rceil}{3} \right\rfloor.$$

在 Lean 中,该命题将 $k$ 作为一个自然数,并带有线图色数等于 $k$ 的假设,因此无论 $\chi'(K_{279})$ 的值是多少,它都涵盖了每一个最小正常边着色;证明过程中导出了 $k = 279$。

该定理是 arXiv:2610.22142 第 6 节中猜想的 $n = 279$ 的情形。该论文证明了所有 $n \ge 3$ 的下界以及 $3 \le n \le 12$ 时的等式;最小的情形,即对于每个最小正常着色均有 $\operatorname{wld}_\rho(K_3) = 2$,也在 Lean 中得到了证明(wild_number_complete_three_min_proper_coloring_eq)。新的内容是对每个最小正常着色均成立的上界 $\operatorname{wld}_c(K_{279}) \le 186$,以及其背后的论证:一种块星构造,其各个块是通过随机置换上的局部引理选取的。

该命题的两个特征值得注意。首先,它是关于 $K_{279}$ 的所有最小正常着色的命题,而不仅仅是关于某个精心挑选的着色;三元组划分依赖于着色本身,而局部引理为每一个着色都提供了一个划分。其次,上界仅用到了每个颜色类都是近完美匹配这一性质。着色的任何其他结构均未涉及,这也是该概率论证适用于任意着色的原因。

定理 wild_number_complete_graph_279_min_proper_coloring_eq (Lean 4 已验证)
theorem wild_number_complete_graph_279_min_proper_coloring_eq (k : ℕ)
    (hk : (⊤ : SimpleGraph (Fin 279)).lineGraph.chromaticNumber = k)
    (c : (⊤ : SimpleGraph (Fin 279)).lineGraph.Coloring (Fin k)) :
    simple_graph_wild_number (⊤ : SimpleGraph (Fin 279)) c = 186

4. 证明

我们遵循 Lean 中的证明。固定 $K_{279}$ 的一个颜色在 $\operatorname{Fin} k$ 中的最小正常边着色 $c$。

步骤 1:颜色数与下界。根据 odd_complete_min_edge_coloring_missing_vertex_equiv,每个颜色类恰好遗漏一个顶点,且将每种颜色映射到其遗漏的顶点是一个双射 $m : \operatorname{Fin} k \to \operatorname{Fin} 279$。因此 $k = 279$。应用 $n = 279$ 的一般下界 wild_number_complete_graph_min_proper_coloring_ge,可得 $\operatorname{wld}_c(K_{279}) \ge \lfloor 4 \cdot 140/3 \rfloor = 186$。

步骤 2:块星准则。上界依赖于以下引理。

*引理 1*(simple_graph_wild_number_le_of_block_cut_condition)。设 $n > 0$,设 $\gamma$ 为 $K_n$ 的边着色,设 $p : \operatorname{Fin} n \to \operatorname{Fin} q$ 将顶点分配到各块,并设 $r : \operatorname{Fin} q \to \operatorname{Fin} n$ 对每个块 $b$ 满足 $p(r(b)) = b$。假设对于每条边 $e$ 以及块的每个非空真子集 $S$,都存在相异顶点 $u, v$ 满足 $p(u) \in S$、$p(v) \notin S$ 且 $\gamma(uv) = \gamma(e)$。则 $\operatorname{wld}_\gamma(K_n) \le n - q$。

*证明*。令 $W$ 由非根顶点 $v$ 的边 $\{v, r(p(v))\}$ 组成。它有 $n - q$ 条边,且在每个块内部是一个以根为中心的星图。固定一种颜色。在由该颜色和 $W$ 构成的图中,每个顶点都与其所在块的根相连,因此连通性归结为各个块:假设表明,每个非空真块集合都有该颜色的边离开它,因此这些块不可能分裂为彼此之间没有该颜色边的两类。$\square$

我们将引理 1 应用于大小为 $3$ 的 $q = 93$ 个块,使得 $n - q = 186$。对于尚待选取的顶点置换 $\sigma$,块为 $\sigma(\{3b, 3b+1, 3b+2\})$($b = 0, \dots, 92$),其根为 $\sigma(3b)$。引理 1 的假设对颜色 $i$ 和块集合 $S$ 失效,当且仅当 $S$ 中各块的并集在 $i$ 下闭合。一个集合在 $i$ 下闭合当且仅当其补集在 $i$ 下闭合,因此我们可以假设 $S$ 或其补集包含 $h$ 个块,其中 $1 \le h \le 46$。

步骤 3:坏事件。对于包含 $h$ 个块的集合 $T$($1 \le h \le 46$),记 $P(T)$ 为这 $3h$ 个位置 $\{3b, 3b+1, 3b+2 : b \in T\}$。一个坏事件是一个三元组 $(i, T, g)$,其中 $i$ 是颜色,$g$ 是从 $P(T)$ 映到在 $i$ 下闭合的集合上的单射。若置换 $\sigma$ 在 $P(T)$ 上与 $g$ 一致,则称 $\sigma$ 对 $(i, T, g)$ 是坏的。若 $\sigma$ 与所有坏事件都不一致,则对每种颜色 $i$ 和至多 $46$ 个块的每个集合 $T$,$\sigma(P(T))$ 在 $i$ 下都不是闭合的,由步骤 2 可知这些星图给出 $\operatorname{wld}_c(K_{279}) \le 186$。

步骤 4:局部引理。这种 $\sigma$ 的存在性由随机置换的局部引理得出。

*引理 2*(canonical_permutation_avoidance_of_local_lemma)。设 $I$ 为有限集,对每个 $i \in I$,设 $D_i \subseteq \operatorname{Fin} n$ 非空且 $f_i$ 在 $D_i$ 上单射。若 $D_i \cap D_j \ne \emptyset$ 或 $f_i(D_i) \cap f_j(D_j) \ne \emptyset$,则称 $i$ 与 $j$ 相邻。若权重 $0 \le x_i < 1$ 对所有 $i$ 满足 $$\frac{1}{(n)_{|D_i|}} \le x_i \prod_{j \ne i,\ j \text{ adjacent to } i} (1 - x_j) \qquad \text{for all } i,$$ 其中 $(n)_d = n(n-1)\cdots(n-d+1)$,则存在 $\operatorname{Fin} n$ 的置换 $\sigma$ 使得对每个 $f_i$,$\sigma$ 在 $D_i$ 上的某处与 $f_i$ 不一致。

左端项 $1/(n)_{|D_i|}$ 是均匀随机置换在 $D_i$ 上与 $f_i$ 一致的概率。该引理是局部引理的单边形式,其依赖图在两个部分赋值共享定义域或值域中的点时将它们连接;它在 Lean 中由均匀置换中此类事件的负依赖界证明。

我们将其应用于 $n = 279$、步骤 3 的坏事件,并对具有 $d = 3h$ 个位置的事件取权重 $x = a^{d}/(279)_{d}$,其中 $a = 323/279$。由于 $3 \le d \le 138$,每个权重均落在 $[0,1)$ 内。

步骤 5:对乘积进行界定。固定一个具有 $d = 3h$ 个位置的事件 $(i, T, g)$。每个与其相邻的事件要么与它共享 $P(T)$ 的一个位置,要么共享 $g(P(T))$ 的一个顶点;将其指派给一个这样的共享位置或顶点。这就将相邻事件分成了至多 $2d$ 个组。以下引理逐组界定了乘积。

*引理 3*(finite_product_one_sub_lower_bound_by_fibres)。设 $N$ 为划分为有限集 $S$ 的各组的有限指标集,且权重为 $0 \le w_j \le 1$。若每个组中的权重之和至多为 $M \in [0,1]$,则 $\prod_{j \in N}(1 - w_j) \ge (1 - M)^{|S|}$。

这是由每个组内的 $\prod (1 - w_j) \ge 1 - \sum w_j$ 得出的。剩下的工作是界定使用给定位置的事件的总权重,以及值域中使用给定顶点的事件的总权重。

*穿过某位置的事件*。满足 $p \in P(T)$ 且 $|T| = h$ 的事件 $(i, T, g)$ 计数如下:包含 $p$ 所在块的 $T$ 有 $\binom{92}{h-1}$ 种选取方式,$279$ 种颜色,至多 $\binom{139}{\lfloor 3h/2\rfloor}$ 个大小为 $3h$ 的闭像集,以及到每个闭集上的 $(3h)!$ 个双射。因此它们的总权重至多为 $$\sum_{h=1}^{46} \binom{92}{h-1} \cdot 279 \cdot (3h)!\, \binom{139}{\lfloor 3h/2 \rfloor} \cdot \frac{(323/279)^{3h}}{(279)_{3h}} \le \frac{701}{10000},$$ 这正是精确的有理数不等式 wild_partition_position_mass_279_certificate(在那里写为 $m = h - 1$)。

*穿过某顶点的事件*。对于像包含固定顶点 $w$ 的事件,$T$ 有 $\binom{93}{h}$ 种选取方式,并有 $(3h)!$ 个双射。根据预备知识中的计数,遗漏 $w$ 的颜色在 $3h$ 为奇数时贡献 $\binom{139}{\lfloor 3h/2\rfloor}$ 个包含 $w$ 的闭集,在 $3h$ 为偶数时不贡献,而其他 $278$ 种颜色各贡献 $\binom{138}{\lfloor 3h/2\rfloor - 1}$ 个。因此总权重至多为 $$\sum_{h=1}^{46} \binom{93}{h} (3h)! \left( [3h \text{ odd}]\binom{139}{\lfloor 3h/2\rfloor} + 278 \binom{138}{\lfloor 3h/2\rfloor - 1}\right) \frac{(323/279)^{3h}}{(279)_{3h}} \le \frac{701}{10000},$$ 这正是 wild_partition_vertex_mass_279_certificate。

这两个和式均有 $46$ 个有理数项,并在 Lean 中进行了精确求值。取 $M = 701/10000$,引理 3 给出 $$\prod_{j \text{ adjacent to } (i,T,g)} (1 - x_j) \ge \left(1 - \frac{701}{10000}\right)^{2d}.$$

步骤 6:局部引理不等式。我们需要 $1/(279)_d \le \frac{a^d}{(279)_d} \prod (1 - x_j)$,即 $1 \le a^d \prod(1-x_j)$。由步骤 5,只需满足 $$\left( \frac{323}{279} \left(1 - \frac{701}{10000}\right)^2 \right)^{d} \ge 1,$$ 而事实上 $\frac{323}{279} \cdot \left(\frac{9299}{10000}\right)^2 = \frac{27930262523}{27900000000} > 1$。因此引理 2 适用,并给出避开每个坏事件的置换 $\sigma$。由步骤 3,对应的 $93$ 个星图形成一个由 $186$ 条边组成的颜色连通集,因此 $\operatorname{wld}_c(K_{279}) \le 186$。

结合步骤 1 的下界,得 $\operatorname{wld}_c(K_{279}) = 186$。$\blacksquare$

另一个凭证 wild_partition_event_mass_279_certificate 也已获证:一个用二项式比率表示的关于每个位置总权重的伴随不等式,连同步骤 6 的不等式;最终证明使用了上述两个凭证并直接检验了步骤 6 的不等式。

5. 讨论

该定理解决了 arXiv:2610.22142 中的猜想在 $n = 279$ 时的情形,该数值远在原论文证明的范围 $3 \le n \le 12$ 之外。它并未彻底解决该猜想的一般情形,理清论证中哪些部分依赖于 $279$ 是很有价值的。

约化部分并不依赖。对于每个奇数且满足 $n = 3q$ 的 $n$(即 $n \equiv 3 \pmod 6$),均有 $\lceil n/2 \rceil = (n+1)/2$ 以及 $$\left\lfloor \frac{4\lceil n/2\rceil}{3} \right\rfloor = \left\lfloor \frac{2n + 2}{3} \right\rfloor = 2q = n - q,$$ 因此通过引理 1,不存在任何在某种颜色下闭合的三元组并集的三元组划分给出了猜想的值,并且通过近完美匹配对闭集的计数对每个奇数 $n$ 也都是相同的。专属于 $279$ 的是数值计算步骤:步骤 5 中的两个和式以及 $a = 323/279$、$M = 701/10000$ 的选取仅在 $n = 279$ 处进行了验证。相同的权重或其他权重是否在更小的 $n \equiv 3 \pmod 6$ 下满足局部引理条件,以及这些和式是否能对所有充分大的 $n$ 进行一致界定,我们尚未确定。这种一致界将证明该猜想对所有充分大的 $n \equiv 3 \pmod 6$ 都成立。

对于其他余数,该构造需要进行修改。当 $n$ 为奇数但不能被 $3$ 整除时,猜想的值不再是 $n - n/3$,且各个块的大小将不再相同,这会同时改变边的计数和坏事件。当 $n$ 为偶数时,$\chi'(K_n) = n - 1$ 且每个颜色类都是一个完美匹配,因此不存在遗漏的顶点,闭集仅仅是匹配边的并集;向块的约化依然适用,但目标值和计数有所不同。

除 $279$ 之外,该猜想对于所有 $n \ge 13$ 仍未解决。接下来自然要探讨的问题是:带有随机划分的块星构造是否能对所有充分大的 $n \equiv 3 \pmod 6$ 给出猜想的值;它是否能推广到混合大小的块以及偶数 $n$;以及是否存在使得任何块星集都无法达到下界的最小正常着色,从而需要一种不同的构造?

为什么是研究级成果

  • Proves the conjectured value of the wild number, floor(4*ceil(n/2)/3) = 186, for every minimum proper edge colouring of K_279, a case far beyond the range 3 <= n <= 12 where the paper verified it; the upper bound comes from a seal-free triple partition obtained with a local lemma for random permutations and an exact rational certificate

Lean 声明

Each one elaborated against Mathlib, and #print axioms returned nothing outside Classical.choice · Quot.sound · propext.

参考文献

  1. arXiv:2610.22142 — Wild number for spanning trees in complete and complete bipartite graphs

由 gemini-3.8-flash 根据知识库起草,经过检查并由 Claude Code 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。