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

Kang, Kelly, Kühn, Methuku, Osthus(2023, 第1.1節)は、1972年にErdős, Faber, Lovászが予想した三つの定式化から出発する。論文全体で用いるのは超グラフ形である:$n$ 頂点の任意の線形超グラフ $\mathcal{H}$ — 相異なる任意の2辺について $|e \cap f| \le 1$ を満たすもの — の辺色彩数は $\chi'(\mathcal{H}) \le n$ を満たす。ここで $\chi'(\mathcal{H})$ は交差する辺が異なる色を持つように辺に色を付けるのに必要な色数である。第二の形は頂点彩色である:グラフ $G$ が $n$ 個のクリークの和であり、各クリークのサイズが高々 $n$ で、任意の2つが高々1頂点を共有するなら $\chi(G) \le n$。第三は元の集合版である:共通部分のサイズが高々 $1$ の $n$ 元集合 $n$ 個に対し、その要素を $n$ 色で塗り、各集合がレインボー(全要素が異なる色)になるようにできる。

等価性は純粋に双対性による。$\mathcal{H}$ の proper な辺彩色はそのライングラフ $L(\mathcal{H})$ の proper な頂点彩色であり、$\mathcal{H}$ の各頂点 $v$ は $v$ を含む辺の上にクリークを誘導し、線形性はまさに「高々1頂点を共有する」という仮定に対応する。集合の接続行列の転置は、集合版とクリーク版の読み方を入れ替える。したがって証明のすべての定量的議論は $\mathcal{H}$ 上で行われ、その次数とコ次数のデータがニブル機構を駆動する。

上界 $n$ は強制的であり、第1.1節で思い出される三つの本質的に異なる証人による:$n$ が奇数の完全グラフ $K_n$ でライングラフが $n$-彩色数を持つもの;ニア・ペンシル($n-1$ 頂点上の1辺と、その欠けた頂点を通る $n-1$ 辺);そして有限射影平面(サイズ約 $\sqrt{n}$ の互いに交差する約 $n$ 本の辺)である。これらの極値族は証明全体を通して、全く余裕のない場合として繰り返し現れる。