解法: レインボー木によるリンゲル予想の証明(2020年)

モンゴメリー、ポクロフスキー、スダコフ(2021年、序論)は、リンゲルが1963年に予想1.1を提示したことを振り返る:$K_{2n+1}$ は $n$ 本の辺を持つ任意の木のコピーに分解できる。これはグラフ分解に関する最も古くよく知られた未解決問題の1つであり、以前は特別な木の形状(毛虫木、葉が最大 $4$ 枚の木、頂点が最大 $35$ 個の木、その他)や、近似的・次数有界の制限付き(Joos-Kim-Kuhn-Osthusは次数有界の木について証明し、Ferber-SamotijおよびAdamaszek-Allen-Grosu-Hladkyは最大次数 $O(n/\log n)$ について近似版を証明した)でしか検証されていなかった。この論文の主定理は、木の形や次数に関するあらゆる制限を取り除く:十分大きいすべての $n$ に対し、$K_{2n+1}$ は $n$ 本の辺を持つ任意の木 $T$ の $2n+1$ 個のコピーに分解できる(定理1.2)。