结果族 157：Graph coloring, clique minors, and Colin de Verdière invariants · 学科：Combinatorics · 验证状态：暂无形式化证明，请以社区核验为准
给地图染色，相邻区域不同色，最少要几种颜色？这是图的色数 χ。另一把尺子：把图里若干连通块各自”捏成一点”，能捏出的最大完全图 Kₜ 的阶数 t，叫 Hadwiger 数 h。1943 年的 Hadwiger 猜想断言 χ≤h。这篇论文造出反例：颜色比”捏合能力”多得多的图真的存在。
关键词卡片
看个具体例子
“捏出 K₄”长什么样：四个连通块两两有边相连，各缩成一点就得到 K₄：
反例的数字版：图有 m 个点、独立数至多 2，于是每个色类至多 2 点，χ(G) 至少 m/2；而连通匹配不足 m/100，推出
@@M@@h(G)<\tfrac{26m}{75}+\tfrac23<\tfrac m2\le\chi_f(G)\le\chi(G)@@
取 m=15000：h(G) 小于 5201，而 χ(G) 至少 7500——颜色比最大团子式多出一大截，猜想连同分数版本被一并推翻。构造分三层：先用代数条件造”洞”保证任意三点有边，再用概率方法阻止大连通匹配，最后采样出有限图。
为什么值得关心
一个悬置 80 多年的著名猜想被否定；但姊妹篇表明”χ≤C·h”的线性松弛依然正确——失败恰好只在系数 1。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读里的两把尺子可以完全摊开：染色数 χ 说的是”把图中相邻顶点分开颜色，至少要几桶颜料”；Hadwiger 数 h 说的是”把若干连通块各自捏成一个点、块与块之间都有边，最多能捏出多大的完全图”。1943 年 Hadwiger 猜想断言”捏合能力”总不输”区分能力”，即 χ≤h。导读里的反例策略是：造一种图，其中任何三个点必有边相连，于是每种颜色至多染两点、颜色数被迫超过点数之半；同时图里却”捏”不出同样大的完全图。
第二级台阶
| 精确化：图 G 的独立数 α(G) 是两两不相邻的最大点集大小；χ(G) 是正常染色最少色数；h(G) 是最大团子式 K_t 的阶 t。称一组两两不交的边为连通匹配，若任两条边的端点集之间有边相连，其最大规模记 cm(G)。文中关键的计算工具是计数不等式 h(G)≤( | V | +4cm(G)+2)/3：大的团子式中大量分支集只能是单点或双边，必然导出大连通匹配。分数色数 χ_f 允许给独立集配实数权，恒有 χ_f≤χ 且 χ_f≥ | V | /α。 |
第三级台阶
定理断言：存在任意大的 m 点图同时满足 α≤2 与 cm<m/100；代入计数不等式得 h<26m/75+2/3<m/2≤χ_f≤χ。假设的作用：α≤2 直接压出下界 m/2，连通匹配的上界经计数不等式压出 h 的上界，两条线一夹，Hadwiger 猜想连同 Reed–Seymour 讨论的分数弱化（无 K_{p+1} 子式应有分数 p 染色）一并被否定。构造走”代数造洞、概率阻止匹配、采样成图”三层路线，其中”洞”的关系靠特征 2 的奇偶机制保证无三角形，这正是 α≤2 的来源。
构造出独立数至多 2、连通匹配数却不足 @@M@@m/100@@ 的任意大图 @@M@@G@@，由此 @@M@@h(G)<26m/75+2/3<m/2\le\chi_f(G)\le\chi(G)@@：1943 年的 Hadwiger 猜想及其分数染色弱化形式被一并推翻。
Hadwiger 猜想（1943）断言每个有限非空简单图的色数 @@M@@\chi(G)@@ 不超过其 Hadwiger 数 @@M@@h(G)@@，即最大团子式（clique minor）@@M@@K_t@@ 的阶数 @@M@@t@@。小 @@M@@t@@ 情形都是对的：@@M@@t=4@@ 由 Hadwiger 与 Dirac 证明，@@M@@t=5@@ 经 Wagner 结构定理等价于四色定理，@@M@@t=6@@ 由 Robertson、Seymour 与 Thomas 于 1993 年解决。对一般 @@M@@t@@，Kostochka 与 Thomason 的密度界给出 @@M@@O(t\sqrt{\log t})@@ 种颜色，此后不断改进，目前最好结果为 @@M@@O(t\log\log\log t)@@（Liu–Luo，2026），离线性仍有对数鸿沟。独立数（independence number）@@M@@\alpha(G)\le2@@ 的情形备受关注：Plummer–Stiebitz–Toft 证明此时猜想等价于”@@M@@m@@ 个点的图必含 @@M@@K_{\lceil m/2\rceil}@@ 子式”。而 Duchet–Meyniel 只证得 @@M@@h(G)\ge m/3@@，Fox 加强到 @@M@@m/3+c\,m^{4/5}(\log m)^{1/5}@@，距 @@M@@m/2@@ 一步之遥却久攻不下。本文证明：这一步其实跨不过去。
定理 1.1：存在任意大的整数 @@M@@m@@ 与 @@M@@m@@ 点有限简单图 @@M@@G@@，同时满足
@@M@@D\alpha(G)\le2,\qquad \mathrm{cm}(G)<\frac{m}{100},@@
其中 @@M@@\mathrm{cm}(G)@@ 是连通匹配数（connected matching），即两两接触（touching，共享端点或两端点集之间有边相连）的匹配的最大规模。作者进一步证明计数不等式
@@M@@Dh(G)\le\frac{|V(G)|+4\,\mathrm{cm}(G)+2}{3}@@
（大的团子式中大量分支集取单点或双边，必然导出大连通匹配）。由于每个色类至多含 @@M@@\alpha(G)@@ 个点，对分数染色数 @@M@@\chi_f(G)@@（fractional chromatic number）同样有 @@M@@\chi_f(G)\ge m/\alpha(G)@@，于是推论 1.2 给出：任意大的图满足
@@M@@Dh(G)<\frac{26m}{75}+\frac23<\frac m2\le\chi_f(G)\le\chi(G).@@
因此 Hadwiger 猜想不真；Reed–Seymour 1998 年讨论的分数弱化——无 @@M@@K_{p+1}@@ 子式的图应有分数 @@M@@p@@ 染色（他们只证得 @@M@@2p@@ 界）——同样被否定。历史章节还指出，Füredi–Gyárfás–Simonyi 的精确连通匹配猜想也随之失效。
构造分三层。第一层用代数定义”洞”（hole，即缺失的边）。从有限概率空间采样 @@M@@m@@ 个位置，两点相邻当且仅当它们之间没有洞。每个元素 @@M@@i@@ 带有进入公共二元向量空间的单射线性映射 @@M@@U_i@@ 与线性泛函 @@M@@u_i@@；固定泛函 @@M@@a@@ 与对称双线性型 @@M@@T@@，规定 @@M@@i,j@@ 有洞当且仅当存在 @@M@@\lambda_i,\lambda_j@@ 满足 @@M@@U_i\lambda_i=U_j\lambda_j@@、@@M@@u_jU_i=a+T(\lambda_i,\cdot)@@、@@M@@u_iU_j=a+T(\lambda_j,\cdot)@@、@@M@@a(\lambda_i)+a(\lambda_j)=1@@。把三条泛函恒等式沿假想的洞三角形求和：左端因共享向量条件成对抵消，双线性项因 @@M@@T@@ 的对称性成对抵消，只剩 @@M@@1+1+1=1@@（特征 2），矛盾。故洞关系无环、无三角形，图即使采样出现重复元素也有 @@M@@\alpha\le2@@、@@M@@\chi\ge m/2@@，分数同理。
第二层阻止大连通匹配。两条不相交边互不接触，恰当四条交叉点对全是洞，称之为冲突。原始超饱和定理断言：任何满足边际与联合密度上界（@@M@@\sigma_1\le M\mu@@、@@M@@\sigma_2\le M\mu@@、@@M@@\sigma\le2^{DN}\mu^2@@）的单位分布 @@M@@\sigma@@，两个独立单位以至少 @@M@@2^{-100gN}@@ 的概率冲突；单位（unit）指内部无洞的点对，允许两端点强相依——这正是匹配边所需的自由度。代数部分以布尔点上单项式赋值的秩一矩 @@M@@vv^{\top}@@ 为素材：键（key，帧映射像的元组）相等给出共享张量，针（pin）保留有界个系数方向的指定像，低秩矩分解化解交叉收缩方程，碰撞判据把”四洞”化为被接受键分布的重叠。概率部分先把条件于针像的分布分解成叶子并记录小表，相位估计在正测度上给出相容表；再用直方图与乘积比较把查询律送往公共极限，有限维对偶在极限处产生重叠的标量配方；测度极小的分支另用一致性大集估计处理。此段技术性较强，此处从略。
第三层把分布命题搬到有限图：以 Csiszár 信息投影（相对熵最小化）为势能运行 Kleitman–Winston 式指纹算法，超饱和保证每步删去足够大的冲突邻域；当不再有可行律时，用 Ford–Fulkerson 容量割把剩余单位族覆盖成小端点集加小点对集。最后采样 @@M@@m=2^{C_0gN}@@ 个位置，以 @@M@@1-\exp(-\Omega(m))@@ 的概率同时实现 @@M@@\alpha\le2@@ 与 @@M@@\mathrm{cm}<m/100@@，定理得证。
主结果暂无 Lean 形式化证明；OpenAI 官方声明”未经形式化的结果可能有问题”，请以社区核验为准。姊妹篇用同一套帧/洞机器证明 Colin de Verdière 染色猜想 @@M@@\chi\le\mu+1@@ 亦不成立，并给出一条独立的矩阵秩路线同样违反 Hadwiger 不等式；另一姊妹篇则证明线性列表染色界 @@M@@\chi_{\mathrm{list}}(G)\le Ch(G)@@ 成立。三篇合观：Hadwiger 猜想的失败只在系数 1，线性松弛仍然正确。
问 1：证明里最关键也最脆弱的一步是什么？
（答：超饱和分布定理——满足边际与联合密度上界的”单位”分布中，两个独立单位以至少 2⁻¹⁰⁰ᵍᴺ 的概率冲突（四条交叉点对全是洞）。它分三步：有限证书（键、针、低秩矩分解化解交叉收缩方程）、单位律制备（叶子分解、小表与相位估计）、强迫重叠（直方图逼近、乘积比较、公共极限加有限维对偶）。质量低至 N⁻⁴ 的相容分支在极限下消失，须另用一致性大集估计处理——最易藏错处。）
问 2：为什么把反例压在 α≤2 的图上是对的切口？
（答：因为 Plummer–Stiebitz–Toft 证明过：α≤2 情形的 Hadwiger 猜想等价于”任意 m 点图必含 K_{⌈m/2⌉} 子式”；而 Duchet–Meyniel 只证得 h≥m/3，Fox 加到 m/3+cm^{4/5}(log m)^{1/5}，离 m/2 一步之遥。本文直接证明这一步跨不过去：α≤2 且 cm<m/100 的图使 h<26m/75+2/3<m/2。）
问 3：洞关系为什么天然无三角形？
（答：纯特征 2 奇偶机制。每个采样元素带单射线性映射 U_i 与泛函 u_i；i,j 有洞需满足共享向量条件与三条泛函恒等式（含 a(λ_i)+a(λ_j)=1）。若三点两两有洞，把三条恒等式沿三角形求和：共享向量条件使线性项成对抵消，对称双线性型 T 使双线性项成对抵消，只剩 1+1+1=1（模 2），矛盾。采样即便出现重复元素，补图的 α≤2 也保持。）
问 4：与已有工作相比真正的新意是什么？
（答：此前八十年无人撼动猜想本体，最好的一般界是 O(t log log log t)（Liu–Luo 2026）与 Kostochka–Thomason 密度路线；本文给出首个反例，并顺带否定 Reed–Seymour 的分数弱化——失败不在染色的取整缝隙，而是结构性失败。同时姊妹篇证明线性松弛 χ_list≤C·h 仍成立，说明失败恰好只在系数 1。）
问 5：AI 生成证明在这篇的典型风险是什么？
（答：参数顺序。全文常数有严格的选取次序——n 唯一无界、维数 N=M₀n、M₀ 在取极限前固定、O(n) 比特标量记录的系数先于 M₀ 固定、测试精度与分块再后选——叙述里一句”常数有界”背后是多重量词嵌套，最易出现循环依赖或前后次序颠倒。加之 14 节的分析机械（相位、直方图、公共极限、稀有分支）全无形式化背书，属高危长论证。）
问 6：从分布命题到有限图那步为什么不是例行公事？
（答：它以 Csiszár 信息投影为势能运行 Kleitman–Winston 式指纹算法，超饱和保证每步删去足够大的冲突邻域；终止后用 Ford–Fulkerson 容量割把剩余单位族覆盖成小端点集加小点对集，最后采样 m=2^{C₀gN} 个位置以高概率同时实现两条性质。容器与割的接口若松一丝，cm<m/100 就保不住。）
问 7：谁会用到它？
（答：结构图论与染色社区：Hadwiger 猜想、其分数版、Füredi–Gyárfás–Simonyi 的连通匹配精确猜想同时改判；此后问题从”猜想真伪”转为”最优常数与比率”，姊妹篇的线性列表染色界正是紧随其后补上的另一半答案。）
总评
一个八十年的著名猜想被否定，且连分数弱化一并推翻、切口（α≤2）选在最关键的等价形式上，分量极重；但支撑它的是一整套未形式化、参数次序极繁重的代数—概率长论证，核验门槛同样是本批最高的之一。