MathLabs

解法:康–凯利–库恩–梅苏库–奥斯图斯基于迭代吸收法的渐近证明(2021年)

第 7/8 步:卡恩的稳定性预测:远离极端构型则所需颜色更少
通俗地说

真正迫使使用全部 nn 种颜色的只有三种非常刚性的结构:奇数阶完全图 KnK_n(所有边大小为 22 且最大顶点度数为 n−1n-1)、有限射影平面(约 nn 条大小接近 n\sqrt{n} 的边)以及退化的近铅笔结构(有一个度数为 n−1n-1 的顶点或一条大小为 n−1n-1 的边)。

卡恩曾预测,任何既远离最大度数 nn 又远离射影平面边大小分布的线性超图 H\mathcal{H},所需颜色数都应严格少于 nn——作者的证明在推进过程中一并确立了这一稳定性定理。

Δ(H)≤(1−δ)n and ∣{e∈H:∣e∣=(1±δ)n}∣≤(1−3δ)n  ⟹  χ′(H)≤(1−σ)n\Delta(\mathcal{H}) \le (1-\delta)n \text{ and } |\{e \in \mathcal{H} : |e| = (1\pm\delta)\sqrt{n}\}| \le (1-3\delta)n \implies \chi'(\mathcal{H}) \le (1-\sigma)n
详细分析

Kang、Kelly、Kühn、Methuku 与 Osthus(2023年,1.2节,定理1.2与1.3)证明了一个定量的稳定性结果,证实了卡恩的预测。定理1.2指出:对任意 δ>0\delta > 0,存在 n0,σ>0n_0, \sigma > 0,使得当 n≥n0n \ge n_0 时,任意满足最大度数 Δ(H)≤(1−δ)n\Delta(\mathcal{H}) \le (1-\delta)n 且大小为 (1±δ)n(1\pm\delta)\sqrt{n} 的边数至多为 (1−3δ)n(1-3\delta)n 的 nn 顶点线性超图 H\mathcal{H},都满足 χ′(H)≤(1−σ)n\chi'(\mathcal{H}) \le (1-\sigma)n。

事实上,稳定性绝非仅仅是一个附带的推论:在主证明内部,每当 H\mathcal{H} 远离有限射影平面(第5节处理)且没有度数接近 nn 的顶点(第4节与第7节用吸收和 11-因子化处理)时,(1−σ)n(1-\sigma)n 的富余量恰好为蚕食法与局部稀疏染色步骤提供了充足的回旋余地,使其不会在完成前耗尽颜色。

本步骤中的术语
有限射影平面 (FPP)
在 n=k2+k+1n = k^2+k+1 个顶点上具有 nn 条大小为 k+1k+1 的边(直线)的线性超图,其中任意两点恰在一条直线上,任意两条直线恰交于一点,从而迫使 χ′(H)=n\chi'(\mathcal{H}) = n。
本步骤用到的知识