MathDB

The bunkbed conjecture for finite graphs

About 4 years old · traced to

Let G=(V,E)G=(V,E) be a simple, undirected finite graph. Its bunkbed graph is

G±=(V±,E±),V±:=V×{+,−},G^{\pm}=(V^{\pm},E^{\pm}),\qquad V^{\pm}:=V\times\{+,-\},

with

E±:={u+v+,u−v−:uv∈E}∪{u+u−:u∈V}.E^{\pm}:=\{u_+v_+,u_-v_-:uv\in E\}\cup\{u_+u_-:u\in V\}.

For edge probabilities pG=(px)x∈E∪V∈[0,1]E∪Vp_G=(p_x)_{x\in E\cup V}\in[0,1]^{E\cup V}, assign probability pu+v+=pu−v−:=puvp_{u_+v_+}=p_{u_-v_-}:=p_{uv} to horizontal edges and pu+u−:=pup_{u_+u_-}:=p_u to vertical edges; write PpG\mathbb{P}_{p_G} for the resulting independent bond-percolation measure. In the special cases, let Pp,H\mathbb{P}_{p,H} denote puv=pp_{uv}=p, pu=1p_u=1 for u∈Hu\in H and pu=0p_u=0 otherwise, and let Pp\mathbb{P}_p denote puv=pu=pp_{uv}=p_u=p.

The bunkbed conjecture. For every such GG, the following three inequalities hold:

∀ pG∈[0,1]E∪V, v,w∈V:PpG(v−↔w−)≥PpG(v−↔w+),\forall\,p_G\in[0,1]^{E\cup V},\ v,w\in V:\quad \mathbb{P}_{p_G}(v_-\leftrightarrow w_-) \ge \mathbb{P}_{p_G}(v_-\leftrightarrow w_+),

and, in the two special cases,

∀ p∈[0,1], H⊂V, v,w∈V:Pp,H(v−↔w−)≥Pp,H(v−↔w+),\forall\,p\in[0,1],\ H\subset V,\ v,w\in V:\quad \mathbb{P}_{p,H}(v_-\leftrightarrow w_-) \ge \mathbb{P}_{p,H}(v_-\leftrightarrow w_+), ∀ p∈[0,1], v,w∈V:Pp(v−↔w−)≥Pp(v−↔w+).\forall\,p\in[0,1],\ v,w\in V:\quad \mathbb{P}_{p}(v_-\leftrightarrow w_-) \ge \mathbb{P}_{p}(v_-\leftrightarrow w_+).

The conjecture concerns whether two vertices on the same layer are at least as likely to be connected as vertices on opposite layers. It is attributed in the source to Kasteleyn (1985); the supplied material gives no resolution, so its status is open.

Equivalent formulations 1Other wordings

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

  1. The bunkbed conjecture for finite graphs

    Let G=(V,E)G=(V,E) be a connected graph, let T⊆VT\subseteq V, and let 0<p<10<p<1. In the bunkbed percolation model, write Ppbb[u↔v]\mathbb{P}^{\text{bb}}_p[u\leftrightarrow v] for the probability that uu and vv are connected, with all posts between corresponding vertices of TT retained. For all u,v∈Vu,v\in V, the bunkbed conjecture.

    Ppbb[u↔v]≥Ppbb[u↔v′].\mathbb{P}^{\text{bb}}_p[u\leftrightarrow v]\geq\mathbb{P}^{\text{bb}}_p[u\leftrightarrow v'].

    The conjecture asks whether two vertices are at least as likely to be connected within the same layer as across the two layers. The paper disproves this claim by a formal counterexample; although a version in the p↑1p\uparrow 1 limit was recently proved, the general conjecture is refuted.

    source: Nikita Gladkov, Igor Pak and Aleksandr Zimin, “The bunkbed conjecture is false”, arXiv:2410.02545 (2024).

References

Primary source

Thomas Richthammer, “Bunkbed conjecture for complete bipartite graphs and related classes of graphs”, arXiv:2204.12931 (2025).

bunkbed-conjecturebunkbed-graphsgraph-theorypercolation
Posted

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.