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

連結グラフ $G = (V, E)$ と、選ばれた横断頂点の部分集合 $T \subseteq V$ に対して、二段ベッドグラフ $\overline{G}$ は二つのコピー $G$ と $G'$(階 $0$ と階 $1$)、および各 $w \in T$ について $w$ と $w'$ を結ぶ支柱の辺からなる。二段ベッド浸透では、$G$ と $G'$ の各辺は独立に確率 $p \in (0,1)$ で保持され、すべての支柱は常に保持される。カステレインの1985年の二段ベッド予想(Gladkov, Pak & Zimin 2024年、予想1.1、van den Berg & Kesten 2001年、注5を通じてカステレインに帰される)は、このようなすべての $G$、$T$、$p$、および頂点の任意の組 $u, v \in V$ について、$\Pr^{\text{bb}}_p[u \leftrightarrow v] \ge \Pr^{\text{bb}}_p[u \leftrightarrow v']$ が成り立つと主張する——$v$ 自身の階への連結は、$v$ の別の階のコピーへの連結と少なくとも同じくらい確率が高い。

最もよく引用される特殊な場合は $T = V$(すべての頂点に支柱がある)を取るが、Gladkov、Pak、Ziminが実際に扱うのは任意の横断集合 $T$ を持つ一般的な主張であり、彼らの反例が反証するのもこのバージョンである。この予想は、車輪グラフ、完全グラフ、完全二部グラフ、$u$ と $v$ を入れ替える自己同型を持つグラフ、そして横断頂点が一つまたは二つの場合について、そして注目すべきことに極限 $p \to 1$ において、いくつかの特殊な場合で検証されていたが、完全に一般的な証明または反証は、それが提起されてからのほぼ四十年間、確率論者たちの手をすり抜け続けてきた。

この証明の残りの部分では、$p = \tfrac12$ において不等式が破綻するような明示的なグラフ、横断集合、および頂点の組を構成し、一般の場合において予想を反証する。