阶至少为 30000001 的完全图最小正常染色的野数下界紧性
medium tier2026-10-28OP-306审阅: Claude CodeEnglish
摘要
设 $n \ge 3$,且设 $\rho$ 为完全图 $K_n$ 的最小正常边染色。arXiv:2610.22142 证明了 $\operatorname{wld}_\rho(K_n) \ge \lfloor 4\lceil n/2\rceil/3 \rfloor$,表明等号对 $3 \le n \le 12$ 成立,并猜想对所有 $n \ge 3$ 等号均成立。我们对所有 $n \ge 30000001$ 证明了该猜想。对于奇数 $n$,我们将顶点划分为 $q = \lfloor n/3 \rfloor$ 个由三个或四个顶点组成的块;将每个顶点连接到其所在块的根节点得到 $n - q$ 条边,只要没有非空真块并集在某个颜色类下封闭,这些边就构成一个颜色连通集。由针对随机排列的单侧局部引理可知,存在具有该性质的划分:一旦 $q \ge 10^7$,经过任一位置或任一顶点的坏事件加权计数至多为 $1/50$。对于偶数 $n$,多出的顶点自成一个块,这恢复了该论文从 $K_n$ 到 $K_{n-1}$ 的归约。整个证明已在 Lean 4 中得到验证。
1. 引言
设 $\gamma$ 为图 $G$ 的边染色。若对于每种颜色 $c_i$,以颜色 $c_i$ 的边与 $W$ 共同作为边集的生成子图都是连通的,则称边集 $W$ 是颜色连通的。野数 $\operatorname{wld}_\gamma(G)$ 是颜色连通集大小的最小值。论文 arXiv:2610.22142 研究了完全图与完全二部图的这一参数。
对于 $K_n$ 的最小正常边染色,即使用 $\chi'(K_n)$ 种颜色的正常染色(奇数 $n$ 为 $n$ 种颜色,偶数 $n$ 为 $n-1$ 种颜色),arXiv:2610.22142 的定理 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$ 为奇数时,每个颜色类 $M_i$ 都是一个避开一个顶点 $v_i$ 的近完美匹配。给定顶点的一个大小至少为三的块的划分 $P$,每个块中的生成树给出一个具有 $n - |P|$ 条边的集合 $W$,第 3.3.2 节表明 $W$ 是颜色连通的当且仅当 $P$ 是无封印的:没有颜色类 $M_i$ 能完美匹配避开 $v_i$ 的块的非空并集。将 $n$ 记为 $n = 3q + a$,其中 $a \in \{0,1,2\}$,划分为 $q$ 个块的无封印划分(即 $q - a$ 个三元组和 $a$ 个四元块)给出 $n - q$ 条边,其等于 $\lfloor 4\lceil n/2\rceil/3 \rfloor$。对于偶数阶,第 3.3.3 节证明了 $\operatorname{wld}_\rho(K_{2k}) \le \operatorname{wld}_{\rho_v}(K_{2k-1})$,其中 $\rho_v$ 是在 $K_{2k} - v$ 上的限制。该论文对较小的 $n$ 手工构造了无封印划分。在 $n = 12$ 之外,此前唯一解决的情形是 $n = 279$(wild_number_complete_graph_279_min_proper_coloring_eq),通过对该单一阶给出的精确凭证解决。
我们对所有 $n \ge 30000001$ 证明了该猜想(wild_number_complete_graph_large_eq)。新的要素是对每个大阶下无封印划分的存在性证明。顶点的均匀随机排列将顶点放置到固定划分形状的块中。每个潜在的封印都是形如“排列将 $h$ 个块的位置映射到在某一颜色下封闭的给定集合上”的事件。针对随机排列的单侧局部引理表明,当 $q$ 足够大时,存在某个排列能避开所有这些事件。
2. 预备知识
定义 1(最小正常边染色)。对于 $n \ge 1$,完全图 $K_n$ 是 $\operatorname{Fin} n$ 上的完全简单图。以颜色集 $\operatorname{Fin} k$ 进行的正常边染色是 $K_n$ 的线图的正常顶点染色。当 $k$ 为线图的色数 $\chi'(K_n)$ 时,它是最小的;对于奇数 $n \ge 3$,这等于 $n$,对于偶数 $n$,这等于 $n - 1$。
定义 2(野数)。对于图 $G$ 和边染色 $\gamma$,如果对于 $\gamma$ 所使用的每种颜色 $c$,边集为 $\gamma^{-1}(c) \cup W$ 的生成子图都是连通的,则称边集 $W$ 是颜色连通的。野数 simple_graph_wild_number 是有限颜色连通集大小 $|W|$ 的下确界。在 $\mathbb{N}$ 上,空集的下确界为 $0$,但对于此处所考虑的完全图,整个边集是颜色连通的,因此该下确界是最小值。
定义 3(块划分与割条件)。$K_n$ 到 $q$ 个块的块划分是一个带有根映射 $r : \operatorname{Fin} q \to \operatorname{Fin} n$ 的映射 $p : \operatorname{Fin} n \to \operatorname{Fin} q$,满足 $p(r(i)) = i$。若对于每条边 $e$ 以及每个非空块集合 $S \subsetneq \operatorname{Fin} q$,都存在一条边 $uv$ 满足 $p(u) \in S$、$p(v) \notin S$ 且 $\gamma(uv) = \gamma(e)$,则称染色 $\gamma$ 满足 $p$ 的块割条件。
定义 4(封印事件与权重)。固定块映射 $b : \operatorname{Fin} n \to \operatorname{Fin} q$ 以及使用 $n$ 种颜色的正常染色 $c$。对于块集合 $T$,令 $\operatorname{pos}(T) = b^{-1}(T)$。封印事件是一个三元组 $(i, T, f)$,满足 $1 \le |T| \le \lfloor q/2 \rfloor$ 且 $f$ 是 $\operatorname{pos}(T)$ 到顶点集的单射,其像在颜色 $i$ 下封闭:颜色为 $i$ 且有一个端点在像中的每条边,其两个端点都在像中。若顶点排列 $\sigma$ 在 $\operatorname{pos}(T)$ 上满足 $\sigma = f$,则称其实现该事件。对于 $d = |\operatorname{pos}(T)|$,赋予该事件权重 $$\operatorname{wt}_n(d) = \frac{(21/20)^d}{(n)_d}, \qquad (n)_d = n(n-1)\cdots(n-d+1).$$ 均匀随机排列以恰好 $1/(n)_d$ 的概率实现给定的事件。
约定。在 Lean 中,自然数的除法是向下取整除法。数值 $\lfloor 4\lceil n/2\rceil/3 \rfloor$ 记作 4*((n+1)/2)/3,且对每个 $n$ 都有 $(n+1)/2 = \lceil n/2\rceil$。
3. 主要结果
定理(wild_number_complete_graph_large_eq)。设 $n \ge 30000001$,令 $k = \chi'(K_n)$($K_n$ 线图的色数),并设 $c$ 是 $K_n$ 以 $\operatorname{Fin} k$ 为颜色的正常边染色。则 $$\operatorname{wld}_c(K_n) = \left\lfloor \frac{4\lceil n/2\rceil}{3} \right\rfloor .$$
在 Lean 中,前提假设为 30000001 ≤ n、Fin n 上完全图的线图色数与 k 相等的等式,以及该线图用 Fin k 进行的染色 c。结论为 simple_graph_wild_number ⊤ c = 4*((n+1)/2)/3。因此,该定理对所有阶 $n \ge 30000001$、两种奇偶性以及每种最小正常染色,都解决了 arXiv:2610.22142 第 6 节的猜想。
下界是 arXiv:2610.22142 的定理 3.4,形式化为 wild_number_complete_graph_min_proper_coloring_ge。新的部分是每个大阶下相匹配的上界。在此之前,已知上界对 $3 \le n \le 12$ 成立(该论文的定理 3.5;$n = 3$ 的情形为 wild_number_complete_three_min_proper_coloring_eq)以及对单一阶 $n = 279$ 成立。
theorem wild_number_complete_graph_large_eq (n k : ℕ) (hn : 30000001 ≤ n)
(hk : (⊤ : SimpleGraph (Fin n)).lineGraph.chromaticNumber = k)
(c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k)) :
simple_graph_wild_number (⊤ : SimpleGraph (Fin n)) c = 4*((n+1)/2)/34. 证明
下界即为 wild_number_complete_graph_min_proper_coloring_ge,因此只需证明 $\operatorname{wld}_c(K_n) \le \lfloor 4\lceil n/2\rceil/3 \rfloor$。证明结合了三条引理。
引理 1(simple_graph_wild_number_le_of_block_cut_condition)。若 $K_n$(其中 $n > 0$)的边染色 $\gamma$ 对带有根 $r$ 的划分到 $q$ 个块的块划分 $p$ 满足块割条件,则 $\operatorname{wld}_\gamma(K_n) \le n - q$。
证明。取 $W = \{\, u\,r(p(u)) : u \ne r(p(u)) \,\}$,即将每个顶点连接到其所在块之根的星图。则 $|W| = n - q$ 且每个块在 $W$ 内部都是连通的。固定一种颜色。如果由该颜色与 $W$ 构成的子图不连通,则某个连通分支将是由块构成的并集,形成块的非空真子集 $S$,且没有该颜色的边从 $S$ 跨越到其补集,这与割条件矛盾。
引理 2(wild_partition_of_resource_bounds)。设 $c$ 是 $K_n$ 使用 $n$ 种颜色的正常染色,且设 $b$ 是到带有根的 $q$ 个块的块映射。假设对于每个位置 $x$,定义域 $\operatorname{pos}(T)$ 包含 $x$ 的封印事件的总权重至多为 $1/50$,且对于每个顶点 $w$,像包含 $w$ 的封印事件的总权重至多为 $1/50$。则存在一个划分到 $q$ 个带根块的块划分,使得 $c$ 满足块割条件。
证明。当两个封印事件的定义域或像相交时,称它们为邻居。针对随机排列的单侧局部引理表明,只要每个定义域大小为 $d$ 的事件 $E$ 满足 $$\frac{1}{(n)_d} \le \operatorname{wt}_n(d) \prod_{E' \text{ neighbour of } E} \bigl(1 - \operatorname{wt}_n(d')\bigr).$$ 就存在某个排列 $\sigma$ 不实现任何封印事件。$E$ 的邻居被 $2d$ 个族所覆盖:$d$ 个族分别穿过其 $d$ 个定义域位置,另 $d$ 个族分别穿过其 $d$ 个像顶点,且每个族的总权重至多为 $1/50$。因此该乘积至少为 $(49/50)^{2d} \ge (20/21)^d$,这恰好是所需的乘积不等式。现在通过 $\sigma$ 对顶点重新标号,使得顶点 $v$ 去到块 $b(\sigma^{-1}(v))$。设 $S$ 为块的非空真子集,并设 $i$ 为一种颜色。若有必要,将 $S$ 替换为其补集,我们可以假设 $|S| \le \lfloor q/2 \rfloor$;在匹配 $M_i$ 下封闭的集合的补集仍然是封闭的。若没有颜色 $i$ 的边跨越 $S$,则 $S$ 的顶点集在颜色 $i$ 下封闭,从而 $\sigma$ 将实现相应的封印事件。因此每种颜色都跨越每个非平凡割。
引理 3(wild_partition_large_order_resource_bounds)。设 $n$ 为奇数,满足 $3q \le n \le 3q + 2$ 且 $q \ge 10^7$。设 $c$ 为 $K_n$ 的正常 $n$-染色,使得每种颜色 $i$ 恰好避开一个顶点 $v_i$。设 $b$ 为块映射,使得 $h$ 个块的每个并集具有 $3h$ 到 $3h + (n - 3q)$ 个顶点。则引理 2 中的两族和都至多为 $1/50$。
证明。固定 $h$ 和大小为 $k$ 的定义域,其中 $3h \le k \le 3h + 2$。在颜色 $i$ 下封闭的大小为 $k$ 的顶点集 $U$ 由 $M_i$ 的 $\lfloor k/2 \rfloor$ 条边组成,当 $k$ 为奇数时还包含 $v_i$,因此 $U$ 至多有 $\binom{\lfloor n/2 \rfloor}{\lfloor k/2 \rfloor}$ 种选取方式,且到每个集合上都有 $k!$ 个单射。由于 $k!/(n)_k = 1/\binom{n}{k}$,对应于一种颜色 $i$ 和一个块集合 $T$ 的事件权重至多为 $$P(n,k) = \frac{\binom{\lfloor n/2\rfloor}{\lfloor k/2\rfloor}}{\binom{n}{k}} \left(\frac{21}{20}\right)^{k}.$$ 穿过一个固定位置有 $n$ 种颜色以及 $\binom{q-1}{h-1}$ 个包含该位置所在块的 $h$ 个块的集合 $T$,且 $n \binom{q-1}{h-1} \le 5q\binom{q-1}{h-1} = 5h\binom{q}{h}$。穿过一个固定顶点,包含它的所有颜色中大小为 $k$ 的封闭集合总数为 $k\binom{\lfloor n/2\rfloor}{\lfloor k/2\rfloor}$,其中 $k \le 3h + 2 \le 5h$,且有 $\binom{q}{h}$ 个集合 $T$;这给出了相同的量。因此在这两种情形中,$h$ 的贡献都至多为 $5h\binom{q}{h}P(n,k)$,并且 Lean 证明了 $$5h\binom{q}{h}P(n,k) \le \frac{1}{20000}\, h^2 \left(\frac{5}{6}\right)^h .$$ 对于 $h = 1$,这是在 $3 \le k \le 5$ 下的直接估计。对于 $h \ge 2$,它由四个事实推出:$\binom{q}{h}^3 \le \binom{n}{k}$ 与 $\binom{\lfloor n/2\rfloor}{\lfloor k/2\rfloor}^2 \le \binom{n}{k}$(二者均来自范德蒙德恒等式)、$\binom{q}{h} \ge q(q-1)2^{h-2}/(h(h-1))$ 以及 $(21/20)^6 \le 2(5/6)^2$。综合这些可得 $(5h\binom{q}{h}P(n,k))^2 \le C\,h^4(5/6)^{2h}/(q(q-1))$(其中 $C$ 为固定常数),一旦 $q \ge 10^7$ 这就足够小。最后,$\sum_{h \ge 0} h^2 (5/6)^h \le 330$,Lean 通过恒等式 $\sum_{h<N} h^2(5/6)^h + (6N^2 + 60N + 330)(5/6)^N = 330$ 证明了这一点。因此每个总和都至多为 $330/20000 < 1/50$。
定理的证明,奇数 $n$。此时 $k = n$,且每种颜色恰好避开一个顶点,这给出了颜色与所避开顶点之间的双射。将 $n$ 记为 $n = 3q + a$,其中 $a \in \{0,1,2\}$,故 $q \ge 10^7$。位置 $3j, 3j+1, 3j+2$ 构成块 $j$,剩余的 $a$ 个位置被分别添加到块 $0, \dots, a-1$ 中。此时 $h$ 个块的并集具有 $3h$ 到 $3h + a$ 个顶点。引理 3 给出了引理 2 所需的界,引理 2 给出了满足割条件的划分,而引理 1 给出 $\operatorname{wld}_c(K_n) \le n - q = 2q + a$。由于 $n$ 为奇数,当 $a \in \{0, 2\}$ 时 $q$ 为奇数,当 $a = 1$ 时 $q$ 为偶数,在每种情形下均有 $\lfloor 4\lceil n/2\rceil/3 \rfloor = 2q + a$。
定理的证明,偶数 $n$。将 $n$ 记为 $n = m + 1$,其中 $m$ 为奇数;则 $k = m$。$c$ 的每个颜色类都是 $K_n$ 的完美匹配,因此将 $c$ 限制在前 $m$ 个顶点上得到 $K_m$ 的一个正常 $m$-染色,其中每种颜色都恰好避开一个顶点。将 $m$ 记为 $m = 3q + a$。奇数情形提供了 $K_m$ 到 $q$ 个具有割性质的带根块的划分。将最后一个顶点自成一个块,得到 $K_n$ 的 $q + 1$ 个块。分割 $K_m$ 诸块的非平凡割被每种颜色的 $K_m$ 边所跨越。否则,割的一侧恰好是新的块,它被新顶点处给定颜色的边所跨越。于是引理 1 给出 $\operatorname{wld}_c(K_n) \le n - (q+1) = m - q = 2q + a$。这就是 arXiv:2610.22142 第 3.3.3 节的归约。余下只需验证在 $n = 3q + a + 1$ 时 $2q + a = \lfloor 4\lceil n/2\rceil/3 \rfloor$:
- $a = 0$: $q = 2j+1$ 为奇数,$\lceil n/2 \rceil = 3j + 2$,且 $\lfloor 4(3j+2)/3 \rfloor = 4j + 2 = 2q$。
- $a = 1$: $q = 2j$ 为偶数,$\lceil n/2 \rceil = 3j + 1$,且 $\lfloor 4(3j+1)/3 \rfloor = 4j + 1 = 2q + 1$。
- $a = 2$: $q = 2j+1$ 为奇数,$\lceil n/2 \rceil = 3j + 3$,且 $\lfloor 4(3j+3)/3 \rfloor = 4j + 4 = 2q + 2$。
在两种奇偶性下,上界均与下界相吻合,这就证明了等式。
5. 讨论
该定理对所有 $n \ge 30000001$ 解决了 arXiv:2610.22142 的猜想。该论文此前已将上界归约为无封印块划分的存在性,并针对小阶手工构造了这些划分。这里的贡献是一个一致的存在性论证:针对随机排列的局部引理,以及在近完美匹配下封闭的集合由其 $\lfloor k/2 \rfloor$ 条边决定的观察,这使得潜在的封印变得罕见。
除 $n = 279$ 外,有限范围 $13 \le n \le 30000000$ 仍未解决。选取该阈值是为了使估计留有余量地闭合,这远未达到该方法所能给出的极限。二项式界 $\binom{q}{h}^3 \le \binom{n}{k}$ 和 $\binom{\lfloor n/2\rfloor}{\lfloor k/2\rfloor}^2 \le \binom{n}{k}$ 在 $h$ 较小时较为粗糙。对给定的 $n$ 精确求和权重而非使用界 $(1/20000)h^2(5/6)^h$ 可以降低阈值,而精确权重和的计算,或如论文中的显式构造,有望覆盖余下的阶。
该论文还研究了完全二部图。同种类型的随机块放置论证是否能在该情形下给出相匹配的上界,是一个自然的后续问题。
为什么是研究级成果
- Proves the Section 6 conjecture of arXiv:2610.22142 for every n>=30000001 and every minimum proper edge coloring; before, equality was known only for n<=12 and n=279
Lean 声明
- wild_number_complete_graph_large_eqFor every integer n>=30000001, every natural number k equal to the chromatic number of the line graph of K_n, and every proper edge…
- wild_number_complete_graph_279_min_proper_coloring_eqNew case of OP-306: every minimum proper edge colouring of K_279 has wild number 186 = floor(4*ceil(279/2)/3). The lower bound is the…
- simple_graph_wild_numberThe wild number wld_γ(G) of an edge-coloured graph is the minimum size of a colour-connecting set of edges.
- wild_number_complete_graph_min_proper_coloring_geLet n ≥ 3 and let ρ be a minimum proper edge colouring of K_n (a proper colouring with χ'(K_n) colours). Then wld_ρ(K_n) ≥ ⌊4⌈n/2⌉/3⌋.
- wild_number_complete_three_min_proper_coloring_eqFor every minimum proper edge colouring of K_3, the wild number is 2 = ⌊4⌈3/2⌉/3⌋: the case n = 3 of the conjecture in Sec. 6.
- simple_graph_wild_number_le_of_block_cut_conditionLet a nonempty complete graph have a vertex-to-block map p and one root r(i) in each of q blocks. If every used color has an edge crossing…
- wild_partition_of_resource_boundsLet n>0 and let a proper coloring of K_n use the color set Fin n. Fix a partition map b from the vertices onto q blocks, with a specified…
- wild_partition_large_order_resource_boundsSuppose n is odd, q>=10000000, 3q<=n<=3q+2, and a proper n-coloring of K_n has a bijection between colors and their unique missing…
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
参考文献
- arXiv:2610.22142 — Wild number for spanning trees in complete and complete bipartite graphs
由 gemini-3.8-flash 根据知识库起草,经过检查并由 Claude Code 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。