解法:用彩虹树证明林格尔猜想(2020年)
通俗地说
作者并非试图一次性放置整棵树 ,而是先放置一个稍小的版本 (仅缺少情形划分中挑出的特殊叶子或裸路径末端),将其作为从许多合法放置方式中随机选出的彩虹副本。随机性正是关键技巧:作者不需要精确追踪哪些顶点和颜色最终未被使用,只需知道会剩下一个庞大且性质良好的随机顶点与颜色集合,随时准备吸收缺失的部分。
详细分析
蒙哥马利、波克罗夫斯基与苏达科夫(2021年,第2.1节,基于他们先前的论文[蒙哥马利-波克罗夫斯基-苏达科夫,前期工作])证明了定理2.2:对 的一个 -因子化ND染色和 个顶点的森林 ,存在 的一个随机化彩虹副本 ,以及随机子集 ,使得 以高概率是彩虹的,且 与 都可以证明是“良好随机的”(每个元素以固定概率独立出现)。这使得论证不必精确追踪剩余的顶点和颜色,而是可以利用它们的统计分布来处理。
- 2因子化染色
- 的一种边染色,其中每个顶点恰好与每种颜色的 条边相邻;ND染色具有此性质。
- q-随机集合
- 基础集合的一个随机子集,其中每个元素以相同的固定概率 独立出现,使其统计行为易于控制。