解法: レインボー木によるリンゲル予想の証明(2020年)
ざっくり言うと
ステップ4の後、木の大部分は 内に虹色として配置されているが、ちょうど 色とそれに見合う数の頂点が未使用のまま残り、 の除去された小さな部分(場合Aでは刈り取られた葉、場合Bでは裸のパスの遠い端)は、まさにその残った色だけを使って取り付けられる必要がある——多くも少なくもなく。これは繊細なマッチング問題である:吸収は、残ったランダムな頂点の間に柔軟な構造を設計し、たまたま残った色が何であれ、まさにその未使用の色を使って埋め込みを完成できるようにする。
詳しい解説
モンゴメリー、ポクロフスキー、スダコフ(2021年)の第4節と第5節は、それぞれ場合Aと場合Bについて「仕上げの補題」を証明する(手法M2)。その考え方は、レードル、ルチンスキー、セメレディの一般的な吸収法を応用したもので、残ったランダムな頂点集合 の中に、 に具体的にどの色が入っていようとも、未使用の色集合 を正確に使って完成させられる吸収構造を設計することである。場合A(多くの分離した葉)と場合B(多くの長い裸のパス)は、欠けた部分の形が異なる(単一の垂れ下がった辺か長いパスか)ため、それぞれ独自に調整された吸収ガジェットを必要とするが、どちらも定理2.2(ステップ4)からの同じランダム性の保証に依拠している。
- 吸収法
- レードル、ルチンスキー、セメレディによって導入された手法で、まずほぼどんな残り物でも組み込める小さな柔軟な「吸収」構造を作り、次に目標構造の大部分を別に埋め込み、最後に吸収体を使って残ったものを片付ける。