MathLabs

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

第 6/8 步：方法M3:情形C的完全确定性嵌入
上一步下一步
通俗地说

情形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}
详细分析

蒙哥马利、波克罗夫斯基与苏达科夫(2021年)第7节处理情形C的树,即那些去掉与度数至少为 δ−4\delta^{-4} 的顶点相邻的叶子后,最多剩下 n/100n/100 个顶点的树,这意味着该树本质上是一个小核心加上若干巨大的星形结构。对于这类树,作者放弃随机化,转而完全确定性地构造彩虹嵌入,精心选取显式的顶点顺序与颜色分配,用作者自己的话说,这“非常接近 TT 的一个优美标号”;这一方法本质上独立于情形A和B所用的随机技巧(M1、M2)。

本步骤中的术语
优美标号
树的顶点上的一个双射标号 f:V(T)→{0,…,n}f: V(T) \to \{0,\ldots,n\},使得所有边差 ∣f(x)−f(y)∣|f(x)-f(y)| 互不相同;罗萨猜想每棵树都有这样的标号,它可直接给出ND染色中的一个彩虹副本。