二段ベッド予想

有限グラフ $G = (V, E)$ に対し、$G$ の2つの同一コピー $G_0, G_1$ を頂点部分集合 $v \in T \subseteq V$ 上の垂直辺 $(v, 0)(v, 1)$ で結んだ直積グラフ $G \,\square\, K_2$ を二段ベッドグラフとする。保持確率 $p \in (0, 1)$ の独立なボンド・パーコレーションを $G_0$ と $G_1$ 上で考えたとき、任意の $u, v \in V$ について、$(u, 0)$ が同じ層の $(v, 0)$ と連結である確率は、$(u, 0)$ が反対の層の $(v, 1)$ と連結である確率以上であると予想されていた。

2024年10月、ニキータ・グラドコフ、イゴール・パク、アレクサンドル・ジミンは、ローレンス・ホロムによる2024年のハイパーグラフ・パーコレーションの反例（`arXiv:2406.01790`）を基に、$7,222$ 頂点と $14,442$ 辺をもつ平面グラフの明示的な反例を構成して二段ベッド予想を反証した（`arXiv:2410.02545`、2025年に PNAS に掲載）。彼らの証明は純粋に解析的であり、コンピュータによる力任せの検証には依存していない。