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

ステップ2のハロムのハイパーグラフ $H$ を取り、その六つの$3$-一様ハイパーエッジ $\{a,b,c\}$ それぞれについて、ステップ5の道のガジェット $G_n$($n = 1204$)の新しいコピーで置き換え、ガジェットの $a$ をハイパーエッジの横断頂点に、$b, c$ を他の二頂点に同一視する(Gladkov, Pak & Zimin 2024年, 第4.2節)。得られるグラフ $G$ は平面的であり($H$ が平面的に描かれ $G_n$ が平面的であるため)、$|V(G)| = 10 + 6 \times 1202 = 7{,}222$ 個の頂点と $|E(G)| = 6 \times 2407 = 14{,}442$ 本の辺を持ち、ハロムのハイパーグラフと同じ三つの横断頂点 $T = \{u_2, u_7, u_9\}$ を保持している。

ステップ5で $G_n$ の確率が頑健なハイパーエッジ補題の不等式を満たすことが確認され、ステップ4の補題自体により、$G$ 上の通常の $\tfrac12$-ボンド浸透は $\Pr[u_1 \leftrightarrow u_{10}] < \Pr[u_1 \leftrightarrow u_{10}']$ を満たす——これがGladkov, Pak & Zimin(2024年)の定理1.2である:$7{,}222$ 個の頂点と $14{,}442$ 本の辺を持つ連結な平面グラフ、サイズ $3$ の横断集合、そして二つの頂点 $u, v$ が存在し、$\Pr^{\text{bb}}_{1/2}[u \leftrightarrow v] < \Pr^{\text{bb}}_{1/2}[u \leftrightarrow v']$ を満たす——これは二段ベッド予想に対する明示的で完全に構成的な反例である。注目すべきは、この議論が(全グラフ上の浸透結果を総当たりで探索する計算機探索によってではなく——これは列挙するにはあまりにも大きすぎる——)これまでのステップで積み上げてきた補題の連鎖を通じて、解析的にこの不等式を確立している点である。

著者らは、三つの横断頂点はいかなる反例に対しても証明可能な意味で最小限であること(それより少なければ機能し得ない。これは横断頂点が一つまたは二つの場合の予想の既知の正しさによる——最後のステップを参照)を指摘する一方、総頂点数 $7{,}222$ が最適である可能性は非常に低く、より小さな反例がほぼ確実に存在するが、それはこの構成の目標ではなかったとも述べている。