MathLabs

解法:用彩虹树证明林格尔猜想(2020年)

第 4/8 步:方法M1:随机嵌入树的绝大部分
通俗地说

作者并非试图一次性放置整棵树 TT,而是先放置一个稍小的版本 T′T'(仅缺少情形划分中挑出的特殊叶子或裸路径末端),将其作为从许多合法放置方式中随机选出的彩虹副本。随机性正是关键技巧:作者不需要精确追踪哪些顶点和颜色最终未被使用,只需知道会剩下一个庞大且性质良好的随机顶点与颜色集合,随时准备吸收缺失的部分。

(1−ϵ)n(1-\epsilon)n
详细分析

蒙哥马利、波克罗夫斯基与苏达科夫(2021年,第2.1节,基于他们先前的论文[蒙哥马利-波克罗夫斯基-苏达科夫,前期工作])证明了定理2.2:对 K2n+1K_{2n+1} 的一个 22-因子化ND染色和 (1−ϵ)n(1-\epsilon)n 个顶点的森林 T′T',存在 T′T' 的一个随机化彩虹副本 T^′\hat{T}',以及随机子集 V⊆V(K2n+1)∖V(T^′), C⊆C(K2n+1)∖C(T^′)V \subseteq V(K_{2n+1})\setminus V(\hat{T}'), \ C \subseteq C(K_{2n+1})\setminus C(\hat{T}'),使得 T^′\hat{T}' 以高概率是彩虹的,且 VV 与 CC 都可以证明是“良好随机的”(每个元素以固定概率独立出现)。这使得论证不必精确追踪剩余的顶点和颜色,而是可以利用它们的统计分布来处理。

本步骤中的术语
2因子化染色
K2n+1K_{2n+1} 的一种边染色,其中每个顶点恰好与每种颜色的 22 条边相邻;ND染色具有此性质。
q-随机集合
基础集合的一个随机子集,其中每个元素以相同的固定概率 qq 独立出现,使其统计行为易于控制。
本步骤用到的知识