Bunkbed conjecture

Disproved, 2024Combinatorics and discrete mathematicsProbability and statistics

Statement

Let $G = (V, E)$ be a finite graph, and let its bunkbed graph be the Cartesian product $G \,\square\, K_2$ consisting of two identical copies $G_0, G_1$ of $G$ joined by vertical edges $(v, 0)(v, 1)$ for vertices $v \in T \subseteq V$ . Under independent bond percolation on $G_0$ and $G_1$ with retention probability $p \in (0, 1)$ , the conjecture asserted that for every $u, v \in V$ , the probability that $(u, 0)$ is connected to $(v, 0)$ in the same layer is at least the probability that $(u, 0)$ is connected to $(v, 1)$ in the opposite layer.

In October 2024, Nikita Gladkov, Igor Pak, and Aleksandr Zimin disproved the bunkbed conjecture (`arXiv:2410.02545`, published in PNAS in 2025) by constructing an explicit planar counterexample graph with $7,222$ vertices and $14,442$ edges, building on Lawrence Hollom's 2024 counterexample for hypergraph percolation (`arXiv:2406.01790`). Their proof is purely analytical and does not rely on brute-force computer verification.

The failure of the bunkbed conjecture is a striking warning that plausible monotonicity statements in percolation and random-cluster models can fail in high-complexity finite graphs, echoing the failure of several correlation inequalities for effective resistance and random walks. Open questions now focus on determining the smallest vertex count of a counterexample and whether the conjecture still holds in the limit $p \to 1$ or for vertex-transitive graphs.

References

Nikita Gladkov, Igor Pak, Aleksandr Zimin (2025). The bunkbed conjecture is false · DOI:10.1073/pnas.2420725122 · arXiv:2410.02545
Jacob van den Berg, Jeff Kahn (2001). A remark on the Bunkbed Conjecture · DOI:10.1017/S096354830100482X

History of the problem

1985Dutch physicist Piet Kasteleyn formulates the bunkbed conjecture as an intuitive correlation inequality in percolation theory.
2001Jacob van den Berg and Jeff Kahn publish the first paper studying the conjecture in the mathematical literature and note its connections to random cluster models.
2009Madeleine Leander's thesis proves the bunkbed conjecture for wheel graphs, and Svante Linusson's follow-up paper (2011) claims a proof for outerplanar graphs — a claim Linusson retracts in a 2019 erratum after finding a flaw in the argument; the conjecture is separately confirmed for complete graphs by Paul de Buyer (2016-2018) and Peter van Hintum and Piet Lammers (2019).
2024Lawrence Hollom disproves the hypergraph generalization of the bunkbed conjecture; months later, Nikita Gladkov, Igor Pak, and Aleksandr Zimin amplify Hollom's gadget using massive vertex clusters to construct a $7,222$ -vertex planar graph that disproves the original conjecture.