MathDB

The bunkbed conjecture for finite graphs

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 \mathbbmPpG\mathbbm{P}_{p_G} for the resulting independent bond-percolation measure. In the special cases, let \mathbbmPp,H\mathbbm{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 \mathbbmPp\mathbbm{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:\mathbbmPpG(v−↔w−)≥\mathbbmPpG(v−↔w+),\forall\,p_G\in[0,1]^{E\cup V},\ v,w\in V:\quad \mathbbm{P}_{p_G}(v_-\leftrightarrow w_-) \ge \mathbbm{P}_{p_G}(v_-\leftrightarrow w_+),

and, in the two special cases,

∀ p∈[0,1], H⊂V, v,w∈V:\mathbbmPp,H(v−↔w−)≥\mathbbmPp,H(v−↔w+),\forall\,p\in[0,1],\ H\subset V,\ v,w\in V:\quad \mathbbm{P}_{p,H}(v_-\leftrightarrow w_-) \ge \mathbbm{P}_{p,H}(v_-\leftrightarrow w_+), ∀ p∈[0,1], v,w∈V:\mathbbmPp(v−↔w−)≥\mathbbmPp(v−↔w+).\forall\,p\in[0,1],\ v,w\in V:\quad \mathbbm{P}_{p}(v_-\leftrightarrow w_-) \ge \mathbbm{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 1

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).

Sources & referencesView supporting material

Primary source

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

bunkbed-conjecturebunkbed-graphsgraph-theorypercolation

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.