MathLabs

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

第 4/8 步:削去多出的 +1+1:处理接近完全图的情形
通俗地说

要想把热身界从 n+1n+1 降到 nn,交给维京定理的剩余图的最大度数必须再小1——只有当几乎每个顶点在大小为 22 的边中都达到满度 n−1n-1(即超图 H\mathcal{H} 看起来几乎就是完全图 KnK_n)时,这一点才会失效。

因此作者分成两种情形:若 H\mathcal{H} 不接近 KnK_n,可以把蚕食加吸收的论证收紧,省下这1个度数;若 H\mathcal{H} 接近 KnK_n,则改用专门针对近完全图的深刻 11-因子化定理。

Δ(H∖H′)≤n−1−∣C∣\Delta(\mathcal{H}\setminus\mathcal{H}') \le n - 1 - |C|
详细分析

Kang、Kelly、Kühn、Methuku 与 Osthus(2023年,2.1节,定义2.2)用 (ρ,ε)-full(\rho,\varepsilon)\text{-full} 超图的概念将“接近 KnK_n”形式化:几乎所有顶点的大小 22 边度数都至少为 (1−ε)n(1-\varepsilon)n,且有相当比例的顶点达到最大可能度数 n−1n-1。

当 H\mathcal{H} 不是 (ρ,ε)-full(\rho,\varepsilon)\text{-full} 时,可以改进蚕食与吸收构造,使匹配未覆盖的任何“缺陷”顶点都落在 S:={u∈U:dG(u)<n−1}S := \{u \in U : d_G(u) < n-1\} 内,从而把剩余度数界降低1变为 Δ(H∖H′)≤n−1−∣C∣\Delta(\mathcal{H}\setminus\mathcal{H}') \le n - 1 - |C|,再由维京定理直接给出 χ′(H)≤n\chi'(\mathcal{H}) \le n。当 H\mathcal{H} 是 (ρ,ε)-full(\rho,\varepsilon)\text{-full} 时,作者转而应用 Csaba、Kühn、Lo、Osthus 与 Treglown 发展的过满子图与 11-因子化工具,直接分解稠密的大小为 22 的核心部分。

本步骤中的术语
(ρ,ε)-full(\rho,\varepsilon)\text{-full} 超图
仅靠大小为 22 的边就使其看起来几乎像 KnK_n 的 nn 顶点线性超图:至少 (1−10ε)n(1-10\varepsilon)n 个顶点的大小 22 边度数至少为 (1−ε)n(1-\varepsilon)n,且至少 (ρ−15ε)n(\rho-15\varepsilon)n 个顶点达到满度 n−1n-1。
本步骤用到的知识