MathLabs

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

第 3/8 步:热身:通过随机顶点吸收器达到 n+1n+1 种颜色
通俗地说

先关注更简单的情形,即每条超边大小都有界(比如至多 rr 个顶点),这使得 H\mathcal{H} 的大部分变成一个普通图 GG(边大小为 22)。思路是随机地把 GG 一半的边留作灵活的“储备”,用蚕食法高效地给其余部分染色,再用储备来修补少数(尤其是度数非常高、接近 nn 的)顶点,而这些顶点单靠蚕食法无法完美覆盖。

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

Kang、Kelly、Kühn、Methuku 与 Osthus(2023年,2.1节)概述了边大小有界 2≤∣e∣≤r2 \le |e| \le r 情形的论证。设 GG 为 H\mathcal{H} 中大小为 22 的边构成的图。以概率 1/21/2 独立地把 GG 的每条边放入随机储备 RR;高概率下每个顶点都满足 dR(v)=dG(v)/2±ξnd_R(v) = d_G(v)/2 \pm \xi n(某个小的 ξ\xi),从而 Δ(H∖R)≤(1/2+ξ)n\Delta(\mathcal{H}\setminus R) \le (1/2+\xi)n,由皮彭杰–斯宾塞定理得 χ′(H∖R)≤(1/2+γ)n\chi'(\mathcal{H}\setminus R) \le (1/2+\gamma)n。对 H∖R\mathcal{H}\setminus R 迭代应用罗德尔蚕食法,构造出“近乎完美地”覆盖近满度顶点集 UU 的大匹配,用 RR 中的边修补每个匹配遗漏的(至多一个)顶点;剩下极少数未染色的边,相对于目前已用颜色集 CC,最大度数至多为 n−∣C∣n-|C|,于是维京定理给出 χ′(H∖H′)≤Δ(H∖H′)+1\chi'(\mathcal{H}\setminus\mathcal{H}') \le \Delta(\mathcal{H}\setminus\mathcal{H}')+1,总计得到 χ′(H)≤n+1\chi'(\mathcal{H}) \le n+1。

本步骤中的术语
维京定理
对任意最大度数为 Δ\Delta 的普通图 GG,其色指数至多为 Δ+1\Delta+1;此处用作对剩余小图的廉价最终修补。
顶点吸收器
预先保留的一组随机边(此处为储备 RR),专门留待之后用来修正先前随机构造未能完美处理的少数顶点。
本步骤用到的知识