Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The bunkbed conjecture is false

Proved
BunkbedFalse.bunkbed_conjecture_false

by burkh4rt · Sep 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsgraph-theorypercolationprobability

The bunkbed conjecture is false.

Kasteleyn's bunkbed conjecture (1985) asserts that for every finite connected graph G=(V,E)G = (V,E)G=(V,E), every set T⊆VT \subseteq VT⊆V of transversal vertices, every retention probability 0<p<10 < p < 10<p<1 and all u,v∈Vu, v \in Vu,v∈V,

Ppbb[u↔v]  ≥  Ppbb[u↔v′],\mathbb{P}^{\mathrm{bb}}_p\bigl[u \leftrightarrow v\bigr] \;\ge\; \mathbb{P}^{\mathrm{bb}}_p\bigl[u \leftrightarrow v'\bigr],Ppbb​[u↔v]≥Ppbb​[u↔v′],

where percolation is performed independently on the two levels of the bunkbed graph, all posts above TTT are retained, and v′v'v′ denotes the counterpart of vvv in the opposite level. In words: staying on your own level is at least as good as crossing over.

The goal of this mission is to prove that this is not true — the negation of the statement above, which is exactly the "In particular, the BBC is false" of Theorem 1.2 of Gladkov, Pak and Zimin.

A counterexample must be exhibited; the conjecture holds in many special cases (wheels, complete graphs, complete bipartite graphs, graphs with an automorphism exchanging uuu and vvv, at most two transversal vertices, and in the p↑1p \uparrow 1p↑1 limit), so no general argument can work. The route laid out by the milestones follows the source: Hollom's hypergraph violates the analogous inequality; a robust version of that violation survives in the Wierman–Ziff model; a gadget graph simulates a hyperedge well enough to inherit it; and substituting the gadget into Hollom's hypergraph produces an explicit finite graph.

Formalization Note The conjecture is stated as a Prop quantifying over all finite vertex types, edge sets, transversal sets and rational 0<p<10 < p < 10<p<1, and the goal is its negation. Proving it requires only exhibiting one counterexample, so the goal follows immediately from the explicit-counterexample milestone; the mathematical work lies entirely in the milestones.

On the rational parameter. The conjecture is stated here for rational ppp with 0<p<10 < p < 10<p<1. This makes the refutation no weaker than the real-parameter version: the real-parameter conjecture implies the rational one, so negating the rational one implies negating the real one. The counterexample occurs at p=1/2p = 1/2p=1/2, which is rational, so nothing is lost. Likewise the restriction of the vertex type to Type costs nothing, since every finite type is equivalent to one there.

Preamble
import Definitions.Def_BunkbedHypergraph
open Bunkbed Bunkbed.Hyper SimpleGraph Finset
Formal statement
namespace BunkbedFalse

/-- **The bunkbed conjecture is false** — the goal of this mission, and the "In particular"
of Theorem 1.2 of Gladkov–Pak–Zimin. -/
theorem bunkbed_conjecture_false : ¬ BunkbedConjecture := by sorry

end BunkbedFalse
Source
N. Gladkov, I. Pak, A. Zimin, "The bunkbed conjecture is false", Proc. Natl. Acad. Sci. USA 122 (2025), no. 24, e2420725122, https://doi.org/10.1073/pnas.2420725122 - p. 2, the "In particular, the BBC is false." of Theorem 1.2; Conjecture 1.1 is on p. 1.
Read-back

What the Lean code literally says, in plain math · claude-opus-5

Read-back: BunkbedFalse.bunkbed_conjecture_false

The statement

theorem bunkbed_conjecture_false : ¬ BunkbedConjecture

It asserts the logical negation of the single proposition Bunkbed.BunkbedConjecture. Fully unfolded, BunkbedConjecture is the closed proposition:

∀ V∈Type0, ∀ (instances) Fintype(V), DecidableEq(V), ∀ E⊆finSym2(V), ∀ T⊆finV, ∀ p∈Q,\forall\, V \in \mathbf{Type}_0,\ \forall\ \text{(instances) } \mathrm{Fintype}(V),\ \mathrm{DecidableEq}(V),\ \forall\, E \subseteq_{\mathrm{fin}} \mathrm{Sym}^2(V),\ \forall\, T \subseteq_{\mathrm{fin}} V,\ \forall\, p \in \mathbb{Q},∀V∈Type0​, ∀ (instances) Fintype(V), DecidableEq(V), ∀E⊆fin​Sym2(V), ∀T⊆fin​V, ∀p∈Q, (0<p)∧(p<1)∧(Connected(GE)) ⟹ ∀ u,v∈V,P[(u,0)↔(v,0)] ≥ P[(u,0)↔(v,1)].\Big(0 < p\Big) \wedge \Big(p < 1\Big) \wedge \Big(\mathrm{Connected}\big(G_E\big)\Big) \ \Longrightarrow\ \forall\, u, v \in V,\quad \mathbb{P}\big[(u,0) \leftrightarrow (v,0)\big] \ \ge\ \mathbb{P}\big[(u,0) \leftrightarrow (v,1)\big].(0<p)∧(p<1)∧(Connected(GE​)) ⟹ ∀u,v∈V,P[(u,0)↔(v,0)] ≥ P[(u,0)↔(v,1)].

So the theorem to be proved is: there exist a finite type VVV (with decidable equality), a finite edge multiset EEE, a subset TTT, and a rational ppp, satisfying all three hypotheses 0<p0<p0<p, p<1p<1p<1, and GEG_EGE​ connected, together with some pair u,v∈Vu,v \in Vu,v∈V, for which the inequality fails; since the quantities are rationals and ≥\ge≥ is a linear order, failure means the strict reverse inequality

P[(u,0)↔(v,0)] < P[(u,0)↔(v,1)].\mathbb{P}\big[(u,0) \leftrightarrow (v,0)\big] \ <\ \mathbb{P}\big[(u,0) \leftrightarrow (v,1)\big].P[(u,0)↔(v,0)] < P[(u,0)↔(v,1)].

Unfolding the objects

Base graph. Sym2(V)\mathrm{Sym}^2(V)Sym2(V) is the type of unordered pairs from VVV, including diagonal pairs {x,x}\{x,x\}{x,x}. For a finite set SSS of such pairs, GS:=ofEdges S=fromEdgeSet SG_S := \mathtt{ofEdges}\,S = \mathtt{fromEdgeSet}\,SGS​:=ofEdgesS=fromEdgeSetS is the simple graph on VVV with x∼yx \sim yx∼y iff {x,y}∈S\{x,y\} \in S{x,y}∈S and x≠yx \ne yx=y; diagonal elements of SSS are silently discarded as adjacencies.

Connectivity hypothesis. Connected(GE)\mathrm{Connected}(G_E)Connected(GE​) is Mathlib's notion: VVV is nonempty and every pair of vertices of VVV is joined by a walk in the deterministic graph GEG_EGE​. This is a condition on the full edge set EEE, not on any percolation realisation, and not on the bunkbed graph.

The bunkbed graph. For T⊆VT \subseteq VT⊆V and S0,S1⊆ES_0, S_1 \subseteq ES0​,S1​⊆E, the graph BB(T,S0,S1)\mathrm{BB}(T,S_0,S_1)BB(T,S0​,S1​) has vertex set V×{0,1}V \times \{0,1\}V×{0,1} and edge set

{ {(x,0),(y,0)}:{x,y}∈S0 } ∪ { {(x,1),(y,1)}:{x,y}∈S1 } ∪ { {(x,0),(x,1)}:x∈T }.\{\,\{(x,0),(y,0)\} : \{x,y\} \in S_0 \,\} \ \cup\ \{\,\{(x,1),(y,1)\} : \{x,y\} \in S_1 \,\} \ \cup\ \{\,\{(x,0),(x,1)\} : x \in T \,\}.{{(x,0),(y,0)}:{x,y}∈S0​} ∪ {{(x,1),(y,1)}:{x,y}∈S1​} ∪ {{(x,0),(x,1)}:x∈T}.

That is: the lower level carries the open edges S0S_0S0​, the upper level carries the open edges S1S_1S1​, and the posts {(x,0),(x,1)}\{(x,0),(x,1)\}{(x,0),(x,1)} over exactly the vertices of TTT are deterministically present (they are not percolated).

The measure. With uniform weight w≡pw \equiv pw≡p, the weight of a configuration S⊆ES \subseteq ES⊆E is

weight(E,p,S)  =  (∏e∈Sp)(∏e∈E∖S(1−p))  =  p∣S∣(1−p)∣E∣−∣S∣,\mathtt{weight}(E,p,S) \;=\; \Big(\prod_{e \in S} p\Big)\Big(\prod_{e \in E \setminus S} (1-p)\Big) \;=\; p^{|S|}(1-p)^{|E|-|S|},weight(E,p,S)=(e∈S∏​p)(e∈E∖S∏​(1−p))=p∣S∣(1−p)∣E∣−∣S∣,

i.e. each element of EEE is retained independently with probability ppp. The connection probability is the explicit double sum

P[x↔y]  :=  bbProb E p T x y  =  ∑S0⊆E ∑S1⊆E1[ x and y are reachable in BB(T,S0,S1) ]⋅weight(E,p,S0)⋅weight(E,p,S1),\mathbb{P}\big[x \leftrightarrow y\big] \;:=\; \mathtt{bbProb}\,E\,p\,T\,x\,y \;=\; \sum_{S_0 \subseteq E}\ \sum_{S_1 \subseteq E} \mathbf{1}\big[\,x \text{ and } y \text{ are reachable in } \mathrm{BB}(T,S_0,S_1)\,\big]\cdot \mathtt{weight}(E,p,S_0)\cdot \mathtt{weight}(E,p,S_1),P[x↔y]:=bbProbEpTxy=S0​⊆E∑​ S1​⊆E∑​1[x and y are reachable in BB(T,S0​,S1​)]⋅weight(E,p,S0​)⋅weight(E,p,S1​),

so the two levels are percolated independently with the same parameter ppp on the same edge set EEE. Reachability is Mathlib's Reachable (reflexive: x↔xx \leftrightarrow xx↔x always holds). All arithmetic is over Q\mathbb{Q}Q; everything is computable.

Direction of the claimed domination. The conjectured inequality has the same-level probability on the left and the cross-level probability on the right, with the source vertex pinned to the lower level in both:

P[(u,0)↔(v,0)] ≥ P[(u,0)↔(v,1)].\mathbb{P}\big[(u,0) \leftrightarrow (v,0)\big] \ \ge\ \mathbb{P}\big[(u,0) \leftrightarrow (v,1)\big].P[(u,0)↔(v,0)] ≥ P[(u,0)↔(v,1)].

This is the standard orientation (downstairs dominates upstairs). The negation therefore demands a configuration in which the cross-level connection is strictly more likely than the same-level one.

Exactly what a proof must exhibit

A witness tuple:

  1. a type VVV in universe Type0\mathbf{Type}_0Type0​ with Fintype and DecidableEq instances;
  2. a finite set EEE of unordered pairs on VVV;
  3. a finite set T⊆VT \subseteq VT⊆V of post locations;
  4. a rational ppp together with proofs 0<p0 < p0<p and p<1p < 1p<1 (both strict);
  5. a proof that GEG_EGE​ is connected (in particular V≠∅V \ne \emptysetV=∅);
  6. vertices u,v∈Vu, v \in Vu,v∈V;
  7. a proof that bbProb E p T (u,0) (v,0)<bbProb E p T (u,0) (v,1)\mathtt{bbProb}\,E\,p\,T\,(u,0)\,(v,0) < \mathtt{bbProb}\,E\,p\,T\,(u,0)\,(v,1)bbProbEpT(u,0)(v,0)<bbProbEpT(u,0)(v,1).

Because the definitions are computable, item 7 is in principle a finite rational computation over 22∣E∣2^{2|E|}22∣E∣ configuration pairs.

Degeneracy audit (checked, including by evaluation)

I checked each of the ways the negation could be trivially true. None of them work; the negation is not cheap.

  • u=vu = vu=v. Then (u,0)↔(u,0)(u,0) \leftrightarrow (u,0)(u,0)↔(u,0) holds in every configuration, so the left side is 111, while the right side is a probability ≤1\le 1≤1. Strict reverse inequality impossible. (Verified: left =1=1=1, right =1=1=1 on a path with u=v∈Tu=v\in Tu=v∈T.)
  • T=∅T = \emptysetT=∅ (empty transversal). With no posts, every edge of BB\mathrm{BB}BB preserves the level coordinate, so (u,0)(u,0)(u,0) and (v,1)(v,1)(v,1) are never reachable and the right side is identically 0≤0 \le0≤ left side. (Verified by evaluation: cross-level probability =0= 0=0.) So the "always-retained posts over TTT" clause is what makes the right-hand side nonzero at all, and a counterexample must take T≠∅T \ne \emptysetT=∅.
  • Empty / degenerate graph. Connected\mathrm{Connected}Connected forces VVV nonempty, so V=∅V = \emptysetV=∅ is excluded. E=∅E = \emptysetE=∅ is admissible only when ∣V∣=1|V| = 1∣V∣=1, which forces u=vu = vu=v and left side =1=1=1. (Verified.)
  • ppp at an endpoint. Excluded: both 0<p0 < p0<p and p<1p < 1p<1 are strict, so p∈{0,1}p \in \{0,1\}p∈{0,1} cannot be used. (Even if allowed, neither endpoint violates the inequality.)
  • Diagonal junk in EEE. EEE may legitimately contain self-pairs {x,x}\{x,x\}{x,x}; these consume a coin flip in weight but contribute no adjacency. Since the same EEE drives both levels, such dummy coins cancel and cannot be exploited. (Verified: adding s(0,0)s(0,0)s(0,0) to a path leaves both probabilities unchanged at 7/167/167/16.)
  • Hypotheses vacuous? No. The three hypotheses are jointly satisfiable in abundance (e.g. any connected EEE with p=1/2p = 1/2p=1/2), so this is not a vacuously-negatable statement; conversely the hypotheses are constraints on the witness, making the negation strictly harder, not easier.

Quantifier-breadth audit

The negated statement is quantified broadly on every axis that matters — all finite vertex types, all edge sets, all transversal subsets TTT, all interior probabilities, and all ordered pairs (u,v)(u,v)(u,v) — so refuting it requires only one witness. Two genuine narrowings are present and should be noted:

  • ppp ranges over Q\mathbb{Q}Q, not R\mathbb{R}R. The conjecture is asserted only at rational retention probabilities, so a witness must be a rational ppp with 0<p<10<p<10<p<1; a phenomenon occurring only at irrational ppp would not refute this statement.
  • VVV is restricted to universe Type0\mathbf{Type}_0Type0​ (written Type, not Type*), and carries Fintype — everything is finite and the state space is finite.

Neither narrowing makes the negation easier. The inequality direction, the pinning of the source to level 000, and the requirement of strict reversal are all as described above; I found no case where the direction or the range lets the negation fall out for free.

Scope note

The statement's ambient file imports Definitions.Def_BunkbedHypergraph and opens Bunkbed.Hyper, but none of the hypergraph machinery (altBBGraph, altProb, wzGraph, wzProb, hollomTriple, hollomE, hollomT, the WZ five-state type), and none of connProb, Pabc, Pa_bc, Pab_c, Pac_b, Pa_b_c, gadgetE, gadgetW, appears in BunkbedConjecture. The proposition depends only on ofEdges, liftLvl, bbGraph, weight, bbProb, and Mathlib's SimpleGraph.Connected / Reachable.

Human review
  • Endorsed by Shuze Chen · Sep 11, 2026

  • Endorsed by burkh4rt · Sep 11, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me