结果族 157：Graph coloring, clique minors, and Colin de Verdière invariants · 学科：Combinatorics · 验证状态：暂无形式化证明，请以社区核验为准
给图的每条边装一根弹簧：在矩阵里，边上的元素取负值，非边取零。再要求整个矩阵恰有一个负特征值，问这样的矩阵最多能有多少个零特征值——这个数 μ(G) 是图的深层指纹。Colin de Verdière 染色猜想说 χ≤μ+1；本文造出反例，把等号永久打破。
关键词卡片
看个具体例子
公式卡：三角形 K₃ 上取矩阵
@@M@@-J_3=\begin{pmatrix}0&-1&-1\\-1&0&-1\\-1&-1&0\end{pmatrix}@@
特征值为 @@M@@-3,0,0@@：恰一个负特征值、核维数 2，故 μ(K₃)=2，而 χ(K₃)=3=μ+1，等号成立。
破坏发生在大图：论文构造独立数至多 2、共 m 个点的图，其上任何良符号、恰一个负特征值的矩阵秩都超过 m/2+1，于是 @@M@@\mu(G)+1<\tfrac m2\le\chi(G)@@——指纹比颜色矮了一截。连更宽容的姊妹参数 κ（Lovász–Schrijver 版本，取同类矩阵的最大余核）也被同样压过：κ(G)+1 小于 m/2。
为什么值得关心
μ 的小值有漂亮几何（μ≤2 恰是外可平面图，μ≤3 恰刻画可平面图），它能否控制染色悬置多年；本文连同分数版本一并否定；结合姊妹篇还得到列表色数不超过 C(μ+1)。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读里”给边装弹簧”说的是：把图翻译成一个实对称矩阵——有边的位置填负数（弹簧刚度），没边的位置填零，对角线随意。在这样的矩阵族里，要求恰有一个负特征值，问零特征值最多能有多少重：这个最大核维数 μ 就是图的谱指纹。Colin de Verdière 染色猜想说”指纹足够深，能控制染色”，即 χ≤μ+1。导读里的反例路线是：找独立数至多 2 的图，颜色被迫超过点数之半；再证明这类图上任何合格矩阵的秩都超过点数之半，核维数被压小——指纹比颜色矮了一截。
第二级台阶
精确化：实对称矩阵 M 称为对图 G 良符号，若不同两点 u,v 有边当且仅当 M_{uv}<0，无边则 M_{uv}=0；强 Arnold 性质是一个谱横截性（genericity）条件，排除凑出来的退化矩阵。不变量定义为 μ(G)=max dim ker M，最大值取遍良符号、恰一个负特征值、且满足强 Arnold 性质的 M。配套概念：独立数 α(G) 是最大两两不相邻点集，χ(G) 是最少染色数。小值有几何意义：μ≤2 恰是外可平面图，μ≤3 恰是可平面图，μ≤4 恰是无链嵌入图，且该范围内 χ≤μ+1 成立。
第三级台阶
| 主定理断言：存在任意大的图 G 满足 α(G)≤2 且 μ(G)+1< | V(G) | /2≤χ(G)，猜想被否定。证明实际建立了更强的矩阵障碍——在这些图上任何良符号、恰一个负特征值的矩阵（不要求强 Arnold 性质）秩都超过 | V | /2+1，故连 Lovász–Schrijver 的更大参数 κ 也被压过，分数链 χ_f≥m/2>κ+1≥μ+1≥h(G) 一并推翻分数弱化。构造的次序是关键：先固定带三类冲突性质的基础图，再做团膨胀并让膨胀参数趋于无穷，谱规范化在该极限下逼出秩增益。由于 μ 的子式单调性给出 h≤μ+1，这些图同时也违反 Hadwiger 不等式。 |
构造出独立数至多 2、且其上任何”良符号、恰一个负特征值”的实对称矩阵秩都超过 @@M@@m/2+1@@ 的任意大图，从而 @@M@@\mu(G)+1<m/2\le\chi(G)@@：Colin de Verdière 染色猜想 @@M@@\chi(G)\le\mu(G)+1@@ 及其分数版本被否定。
Colin de Verdière 不变量 @@M@@\mu(G)@@ 源自 1990 年前后对图上薛定谔算子的谱研究。称实对称矩阵 @@M@@M@@ 对图 @@M@@G@@ 良符号（well-signed），若 @@M@@M_{uv}<0@@ 当且仅当 @@M@@uv\in E@@（非边则取 0），对角元任意；若 @@M@@M@@ 还恰有一个负特征值并满足强 Arnold 性质（Strong Arnold Property，来自谱横截性条件），则这些矩阵核维数的最大值就是 @@M@@\mu(G)@@。该不变量的小值有几何意义：@@M@@\mu\le2@@ 刻画外可平面图，@@M@@\mu\le3@@ 刻画可平面图，@@M@@\mu\le4@@ 刻画无链嵌入（linklessly embeddable）图；且在 @@M@@\mu\le4@@ 范围内染色界 @@M@@\chi\le\mu+1@@ 成立。由 @@M@@\mu@@ 的子式单调性与 @@M@@\mu(K_t)=t-1@@（取矩阵 @@M@@-J_t@@ 即可）可得 @@M@@h(G)\le\mu(G)+1@@，故 Hadwiger 猜想蕴含 Colin de Verdière 染色猜想。这一谱不变量究竟能保留多少染色信息，是悬置多年的试金石问题；本文给出否定回答。
定理 1.2：存在任意大的图 @@M@@G@@ 满足
@@M@@D\alpha(G)\le2,\qquad \mu(G)+1<\frac{|V(G)|}{2}\le\chi(G).@@
证明实际建立了更强的矩阵障碍：在这些图上，任何良符号、恰一个负特征值的矩阵——不要求强 Arnold 性质——秩都严格大于 @@M@@|V(G)|/2+1@@；由秩–零化度关系，核维数小于 @@M@@m/2-1@@。这同时对 Lovász–Schrijver 考虑的更大参数 @@M@@\kappa@@（该类矩阵的最大余核）给出 @@M@@\kappa(G)+1<m/2@@。推论 1.5 给出分数染色链
@@M@@D\chi_f(G)\ge\frac{|V(G)|}{\alpha(G)}\ge\frac m2>\kappa(G)+1\ge\mu(G)+1\ge h(G),@@
故分数 Colin de Verdière 染色界与 Reed–Seymour 的分数 Hadwiger 弱化一并失效；结合姊妹篇的 @@M@@\chi_{\mathrm{list}}(G)\le Ch(G)@@ 还得到 @@M@@\chi_{\mathrm{list}}(G)\le C(\mu(G)+1)@@。
构造分两大块。第一大块是基础图（base graph），沿用姊妹篇的帧/洞机器：顶点是二元域 @@M@@\mathbb F_2@@ 上的单射帧，洞（hole）由共享张量加两条相容的仿射梯度方程加一个奇偶条件认证，沿三角形对方程求和即得矛盾，故洞关系无三角形、补图独立数至多 2。相对姊妹篇的新概率部件是信道稀疏化（channel thinning）：把原始律 @@M@@\rawlaw@@ 的条件信道律换成稀疏律 @@M@@\pi@@，精确保持原帧边际，同时惩罚信道组合的指定非零平移，把困难的相位二择一转化为具有固定正测度相容点对的情形。由此得到区分颜色的冲突超饱和：定理（基础图）之 (G1) 说，大小至少 @@M@@m/20@@ 的匹配分成大小至多 @@M@@am@@ 的类后，不同类中必有冲突边对；(G2) 是非对称的边–点版本，@@M@@\beta m@@ 规模的匹配与 @@M@@\beta m@@ 规模的点集之间必存在冲突的边–点对；(G3) 说任意两个 @@M@@\beta m@@ 点集之间必有交叉洞。把两个分布测试经熵指纹论证（Kleitman–Winston 程序、以 Csiszár 约束熵最小为势能、能量增量弱正则化）搬到有限样本，即得基础图，图阶 @@M@@m=2^{C_0gN}@@。
第二大块是团膨胀（clique blow-up）@@M@@H[s]@@ 上的矩阵判据：把 @@M@@H@@ 的每个点换成 @@M@@s@@ 点团，独立数至多 2 保持，@@M@@\chi\ge ms/2@@。关键在于先固定基础图、再让 @@M@@s\to\infty@@。矩阵论证用超平坦面的有限树表示找到可同时规范化的大块族：第一次谱规范化产生坐标的近似完美匹配，第二次规范化从选出的配对块中提取额外的正方向，由此得到的秩增益与”核约占总维数一半”矛盾，于是性质 (G1)–(G3) 迫使 @@M@@H[s]@@ 上任何良符号单负矩阵的秩大于 @@M@@ms/2+1@@。该判据只依赖所列图性质，可独立于张量构造使用；其内部谱规范化计算技术性较强，此处从略。最后由秩–零化度关系得 @@M@@\mu(G)+1<ms/2\le\chi(G)@@。
主结果暂无 Lean 形式化证明；OpenAI 官方声明”未经形式化的结果可能有问题”，请以社区核验为准。本文与 Hadwiger 反例篇共享帧/洞与矩构造，但矩阵秩障碍是直接证明的，并不由团子式障碍推出；列表染色篇从正面补上线性界。三篇合观：@@M@@\chi\le h\le\mu+1@@ 的系数 1 断言失败，而线性松弛 @@M@@\chi_{\mathrm{list}}\le Ch\le C(\mu+1)@@ 成立。
问 1：证明里最关键也最脆弱的一步是什么？
（答：团膨胀上的矩阵判据。用超平坦面的有限树表示找出可同时规范化的大块族，第一次谱规范化把坐标配成近似完美匹配，第二次从配对块榨出额外正方向，秩增益与”核约占总维数一半”矛盾。两次规范化的容差与块族选取互相咬合，且判据须在 s→∞ 极限下成立——全文技术密度最高处。）
问 2：为什么可以不用强 Arnold 性质就证更强的秩障碍？这不是白送的好处吗？
（答：既是策略也是必要。秩障碍对更大的矩阵类（不要求 SAP）成立，自动同时压住 μ 与 Lovász–Schrijver 的 κ，说明失败不是横截性条件的伪影、也扛得住分数染色的放松；但代价是证明必须直接控制所有良符号单负矩阵的核，比只对付 SAP 矩阵更难。论文未讨论若只用 SAP 能否绕开团膨胀。）
问 3：为什么必须”先固定基础图、再让膨胀参数 s→∞”？
（答：矩阵判据的常数依赖基础图的冲突参数（a、β、m 充分大）；若 s 与基础图同时变，谱规范化的容差就没有一致的落脚点。次序错排正是 AI 长证明里典型的量词错位风险——论文在引言特意强调”注意次序”，属于自觉的风险标注。）
问 4：与姊妹篇 Hadwiger 反例相比，这篇的独立价值在哪里？
（答：三重。其一，h≤μ+1 使 Hadwiger 猜想蕴含 CDV 染色猜想，本文反例因此同时违反 Hadwiger 不等式；其二，矩阵秩障碍系直接证明，并非由团子式障碍推出，是独立第二路线；其三，相对姊妹篇新增”信道稀疏化”部件与区分颜色、边–点非对称两组冲突超饱和。）
问 5：α≤2 但为什么”控制连通匹配”在这里不够用？
（答：矩阵论证需要更强的冲突结构：不仅大匹配内部要有冲突对，还需匹配与独立点集间的冲突（G2）、两个大点集间的交叉洞（G3）——边–点冲突只涉及两条交叉洞，姊妹篇的分布测试不覆盖，必须新做非对称版本，故不能直接复用。）
问 6：AI 生成证明在这篇的典型风险模式是什么？
（答：一是与 Hadwiger 篇共享帧/洞与矩构造，可靠性绑定，一处出错双双坍塌；二是参数繁多易混——图阈值 β 与选择子长度 b 是不同量，M₀ 先于极限固定等次序约束散布全文；三是谱规范化计算未形式化，”近似完美匹配”背后的定量陈述需逐条核对。）
问 7：谁会用到它？
（答：谱图论与图子式结构理论：μ 的几何小值刻画（外可平面、可平面、无链嵌入）不受影响，但”μ 控制染色”的纲领改判；后续问题变成最优常数——姊妹篇的 χ_list≤C(μ+1) 补上线性版，失效的最小 μ 值成为新焦点。）
总评
用矩阵秩障碍直接击穿一个悬置三十余年的谱染色猜想，并与姊妹篇合成”系数 1 失败、线性松弛成立”的完整图景，构思极具野心；但两篇共享的未形式化重型机器与严苛的参数次序，使它成为必须逐行核验才能采信的高风险高回报之作。