解法: グラドコフ=パク=ジミンによる二段ベッド予想の明示的反例(2024年)

Gladkov、Pak、Zimin(2024年、注記4.2)は、ハロムのハイパーグラフにガジェット $G_{1204}$ の六つのコピーを代入する際に関わる複数層の条件付けのために、彼らの$7{,}222$頂点の反例における実際の差 $\Pr[u_1 \leftrightarrow u_{10}'] - \Pr[u_1 \leftrightarrow u_{10}]$ が $10^{-4331}$ より小さいことを指摘している——これは計算によって検出するには小さすぎ、この反証がなぜ実験的にではなく純粋に解析的でなければならず、実際にそうであるのかを鮮やかに示す例である。

この現象を実験的に見えるようにするため、著者らは(論文の第7節で)別途計算を行い、より小さいガジェットのパラメータ $n = 14$ を用いると、わずか$82$頂点のグラフで計算により検出可能な $10^{-47}$ 程度の差が得られることを示した。密接に関連する重み付き二段ベッド予想(辺ごとに異なる確率を許す同値な定式化)をさらに最適化された小さなガジェット($n = 5$、$p \approx 0.0349$)とともに用いると、$28$頂点のグラフで $10^{-78}$ 程度の差が得られる。これらの実験は計算機で実行され相互検証されたものであり、定理1.2の解析的証明に取って代わるものではないが、人間に理解可能な規模でその定性的な仕組みを裏付け、この現象のより小さな事例を探索し検証するために用いられた。

この組み合わせ——大きく明示的な反例に対する無条件の解析的証明を、直感を養い、反例が最終的にどれほど小さくなり得るかを探るための、より小さな近縁種に対する狙いを定めた計算機実験で補うこと——は、現代の組合せ論においてますます一般的になっている証明のスタイルを反映している。ただし(四色定理や非周期単一タイルの結果とは異なり)ここでの核心的な証明のどのステップも、実際には計算機検証に依存していない。