解法:康–凯利–库恩–梅苏库–奥斯图斯基于迭代吸收法的渐近证明(2021年)
通俗地说
早在有人证明出精确的 色界之前,数学家们就已逐步逼近若干较弱的版本:先证明大约 种颜色总是足够,再通过一种强大的随机“蚕食”技术,证明当 增大时, 种颜色在一个消失的误差范围内已经足够。从“接近 ”到“恰好 ”,竟然需要全新的思路,因为那个小误差项恰好隐藏了那些(如极端例子那样)每种颜色都必须毫无冗余地被用到的情形。
详细分析
Kang、Kelly、Kühn、Methuku 与 Osthus(2023年,1.1节)综述了此前的进展。西摩(证明了该猜想的一个推论)证明每个 顶点线性超图都有大小至少为 的匹配。张与劳勒(1988年)直接证明了界 。真正的突破来自卡恩(1992年),他运用罗德尔蚕食法——最初由罗德尔为证明关于组合设计的埃尔德什–哈纳尼猜想而开发的迭代随机匹配构造——证明了渐近界 ;这建立在密切相关的皮彭杰–斯宾塞定理之上,该定理表明任意最大度数为 且共度较小的超图色指数满足 。法伯与哈里斯(2020年)另外证明了边大小均介于 与 之间(某个小常数 )的超图的精确界。
- 罗德尔蚕食法
- 一种迭代式概率技巧,通过反复取出一小口随机的边并将其移除,再对剩下的部分重复此过程来构建一个大匹配(或染色),使结构在可控的情况下逐步积累。
- 共度
- 对两个顶点 而言,同时包含它们的超边数目;“共度小”意味着任意两个顶点共享的边不会太多,这是蚕食类论证所需的技术性条件。