MathLabs

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

第 3/8 步:把树分成三种形状分别攻克
通俗地说

树的形态可以千差万别——带 nn 片叶子的星形、又长又细的路径,或介于两者之间的形态——因此没有单一技巧能应付所有情形。作者证明,每棵足够大的树 TT 至少属于三种便于处理的形状之一:有大量可以修剪的分离叶子(情形A)、有大量可以利用的细长“裸露”路段(情形B),若两者皆无,则该树被少数几个高度数顶点主导,以至于修去它们的叶子后会坍缩成极小的树(情形C)。

T has at least δ6n non-neighbouring leavesT \text{ has at least } \delta^6 n \text{ non-neighbouring leaves}
详细分析

蒙哥马利、波克罗夫斯基与苏达科夫(2021年,第2节,引理3.5“情形划分”)证明,对某个小常数 δ>0\delta > 0,每棵足够大的 (n+1)(n+1) 顶点树都至少属于以下三种情形之一:情形A,T has at least δ6n non-neighbouring leavesT \text{ has at least } \delta^6 n \text{ non-neighbouring leaves}(若一片叶子不与另一片叶子相邻,则称其为非相邻叶子);情形B,T has at least δn/800 vertex-disjoint bare paths of length δ−1T \text{ has at least } \delta n/800 \text{ vertex-disjoint bare paths of length } \delta^{-1}(裸路径是指其内部顶点在 TT 中度数均为 22 的路径);情形C,removing leaves next to vertices of degree≥δ−4 leaves a tree with at most n/100 vertices\text{removing leaves next to vertices of degree} \ge \delta^{-4} \text{ leaves a tree with at most } n/100 \text{ vertices}。三种情形可能重叠,但论文只需把一棵树当作属于情形A或B(若满足),否则归入情形C来处理。

本步骤中的术语
叶子
树中度数为 11 的顶点。
裸路径
TT 内部的一条路径,其所有内部顶点在 TT 中的度数都恰为 22(因此路径不会被任何分叉打断)。
本步骤用到的知识