MathLabs

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

第 2/8 步:完整证明之前五十年的部分进展
通俗地说

早在有人证明出精确的 nn 色界之前,数学家们就已逐步逼近若干较弱的版本:先证明大约 1.5n1.5n 种颜色总是足够,再通过一种强大的随机“蚕食”技术,证明当 nn 增大时,nn 种颜色在一个消失的误差范围内已经足够。从“接近 nn”到“恰好 nn”,竟然需要全新的思路,因为那个小误差项恰好隐藏了那些(如极端例子那样)每种颜色都必须毫无冗余地被用到的情形。

χ′(H)≤n+o(n)\chi'(\mathcal{H}) \le n + o(n)
详细分析

Kang、Kelly、Kühn、Methuku 与 Osthus(2023年,1.1节)综述了此前的进展。西摩(证明了该猜想的一个推论)证明每个 nn 顶点线性超图都有大小至少为 e(H)/ne(\mathcal{H})/n 的匹配。张与劳勒(1988年)直接证明了界 χ′(H)≤⌈3n/2−2⌉\chi'(\mathcal{H}) \le \lceil 3n/2-2\rceil。真正的突破来自卡恩(1992年),他运用罗德尔蚕食法——最初由罗德尔为证明关于组合设计的埃尔德什–哈纳尼猜想而开发的迭代随机匹配构造——证明了渐近界 χ′(H)≤n+o(n)\chi'(\mathcal{H}) \le n + o(n);这建立在密切相关的皮彭杰–斯宾塞定理之上,该定理表明任意最大度数为 DD 且共度较小的超图色指数满足 χ′(H)≤D+o(D)\chi'(\mathcal{H}) \le D + o(D)。法伯与哈里斯(2020年)另外证明了边大小均介于 33 与 cn1/2cn^{1/2} 之间(某个小常数 c>0c>0)的超图的精确界。

本步骤中的术语
罗德尔蚕食法
一种迭代式概率技巧,通过反复取出一小口随机的边并将其移除,再对剩下的部分重复此过程来构建一个大匹配(或染色),使结构在可控的情况下逐步积累。
共度
对两个顶点 u,vu,v 而言,同时包含它们的超边数目;“共度小”意味着任意两个顶点共享的边不会太多,这是蚕食类论证所需的技术性条件。
本步骤用到的知识