解法: 反復吸収法によるKang–Kelly–Kühn–Methuku–Osthusの漸近的証明(2021年)

Kang、Kelly、Kühn、Methuku、Osthus(2023年、第8節)は第5、6、7節の場合分けを組み合わせて定理1.1の証明を完成させる:ある $n_0$ が存在して、すべての $n \ge n_0$ に対し、$n$ 頂点上のすべての線形超グラフ $\mathcal{H}$ は彩色指数 $\chi'(\mathcal{H}) \le n$ を持つ。双対性により、これは1.1節の3つの同値な定式化すべてを同時に証明する:線形超グラフの辺彩色、対ごとに高々1頂点を共有するサイズ高々 $n$ の $n$ 個のクリークの和集合の頂点彩色、および対ごとの交わりが高々 $1$ であるサイズ $n$ の $n$ 個の集合の彩色である。

著者らが1.2節で述べているように、証明のすべての確率的ステップは、大きい $n$ に対する乱択多項式時間彩色アルゴリズムへと構成的に変換することもできる。