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彩色における虹色コピーを与える。