解法: 反復吸収法によるKang–Kelly–Kühn–Methuku–Osthusの漸近的証明(2021年)
ステップ 4/8: 余分な +1 を削る:ほぼ完全なグラフの扱い ざっくり言うとウォームアップの評価を n+1 から n に下げるには、ヴィジングの定理に渡される残りグラフの最大次数が1小さくなる必要がある——これが失敗するのは、ほぼすべての頂点がサイズ 2 の辺において全次数 n−1 を持つとき、すなわち超グラフ H が完全グラフ Kn にほぼ見えるときだけである。
そこで著者らは2つの場合に分ける:H が Kn に近くないなら、ニブルと吸収の議論を精密化してその1次数を節約できる。H が Kn に近いなら、ほぼ完全なグラフ向けに特化した深い 1 因子分解定理へと切り替える。
詳しい解説Kang、Kelly、Kühn、Methuku、Osthus(2023年、2.1節、定義2.2)は、「Kn に近い」ことを (ρ,ε)-full 超グラフの概念によって定式化する:ほぼすべての頂点がサイズ 2 の次数として少なくとも (1−ε)n を持ち、無視できない割合が最大可能次数 n−1 を持つものである。
H が (ρ,ε)-full でないとき、ニブルと吸収の構成を精密化して、マッチングで覆われない任意の「欠陥」頂点が S:={u∈U:dG(u)<n−1} 内に落ちるようにでき、これにより残りの次数評価が1下がって Δ(H∖H′)≤n−1−∣C∣ となり、ヴィジングの定理から直接 χ′(H)≤n が得られる。H が (ρ,ε)-full であるとき、著者らは代わりにCsaba、Kühn、Lo、Osthus、Treglownが開発した過密部分グラフおよび 1 因子分解の機構を適用して、密なサイズ 2 の核を直接分解する。
- (ρ,ε)-full 超グラフ
- サイズ 2 の辺だけでほぼ Kn のように見える n 頂点線形超グラフ:少なくとも (1−10ε)n 個の頂点がサイズ 2 の次数として少なくとも (1−ε)n を持ち、少なくとも (ρ−15ε)n 個の頂点が全次数 n−1 を持つ。
このステップで使う知識