Bernoulli bond percolation, the bunkbed graph, and the bunkbed conjecture
DefinitionBunkbedPercolationMathlib contains no percolation theory of any kind, so this file supplies the objects needed to state the bunkbed conjecture and its refutation.
Let be a finite graph presented by an explicit edge set , and let assign to each edge its retention probability. A configuration is a subset of open edges, and it occurs with weight
The connection probability is the total weight of the configurations in which and lie in the same connected component. The file provides this for general per-edge weights and for the uniform case .
Given a set of transversal vertices, the bunkbed graph has vertex set : a copy of in each level, together with a post joining to for each . In bunkbed percolation the two levels are percolated independently while every post is retained unconditionally. The bunkbed conjecture of Kasteleyn is then recorded as a proposition: for every connected , every , every and all ,
where is the counterpart of in the other level.
The file also defines the five partition probabilities of a distinguished triple — the probabilities that the percolation joins all three, exactly one of the three pairs, or none — which is the data the hyperedge-simulation argument manipulates. Finally it defines the gadget graph of Fig. 2: vertices , with spokes – retained with probability and path edges – retained with probability .
Formalization Note Everything is finite and -valued, hence computable: connection probabilities evaluate under #eval. Graphs are realised by SimpleGraph.fromEdgeSet applied to an explicit Finset (Sym2 V), connectivity is Mathlib's SimpleGraph.Reachable, and probabilities are sums over Finset.powerset. Level 0 is the lower copy. The definitions were validated against the closed forms of Lemmas 5.1–5.3: at , they return , and , matching the paper exactly.
import Mathlib
/-!
# Bernoulli bond percolation and the bunkbed conjecture
Mathlib has no percolation theory of any kind, so this file supplies the objects needed to
state the bunkbed conjecture and its refutation, following
N. Gladkov, I. Pak, A. Zimin, *The bunkbed conjecture is false*,
Proc. Natl. Acad. Sci. USA **122** (2025), no. 24, e2420725122.
Everything is finite and rational-valued, hence **computable**: connection probabilities
evaluate by `#eval` and small instances close by `decide`.
-/
namespace Bunkbed
open SimpleGraph Finset
variable {V : Type*} [Fintype V] [DecidableEq V]
/-- Adjacency of a graph presented by an explicit edge `Finset` is decidable. -/
instance fromFinsetAdj (S : Finset (Sym2 V)) :
DecidableRel (fromEdgeSet (S : Set (Sym2 V))).Adj := fun _ _ =>
decidable_of_iff _ (fromEdgeSet_adj (s := (S : Set (Sym2 V)))).symm
/-- The graph on `V` whose edges are exactly `S`. Reducible, so decidability instances fire. -/
abbrev ofEdges (S : Finset (Sym2 V)) : SimpleGraph V :=
fromEdgeSet (S : Set (Sym2 V))
/-- The probability weight of the configuration in which exactly the edges of `S ⊆ E` are open,
each edge `e` being retained independently with probability `w e`. -/
def weight (E : Finset (Sym2 V)) (w : Sym2 V → ℚ) (S : Finset (Sym2 V)) : ℚ :=
(∏ e ∈ S, w e) * (∏ e ∈ E \ S, (1 - w e))
/-- The probability of an event described by a decidable predicate on the open edge-set. -/
def probOf (E : Finset (Sym2 V)) (w : Sym2 V → ℚ)
(ev : Finset (Sym2 V) → Prop) [DecidablePred ev] : ℚ :=
∑ S ∈ E.powerset, if ev S then weight E w S else 0
/-- `connProb E w u v` is the probability that `u` and `v` are connected in the weighted
Bernoulli bond percolation on the graph with edge set `E`. -/
def connProb (E : Finset (Sym2 V)) (w : Sym2 V → ℚ) (u v : V) : ℚ :=
probOf E w (fun S => (ofEdges S).Reachable u v)
/-- Uniform retention probability `p` on every edge. -/
abbrev connProbU (E : Finset (Sym2 V)) (p : ℚ) (u v : V) : ℚ :=
connProb E (fun _ => p) u v
/-! ## The bunkbed graph -/
/-- Lift an edge of the base graph into level `i ∈ {0,1}` of the bunkbed. -/
def liftLvl (i : Fin 2) (e : Sym2 V) : Sym2 (V × Fin 2) := e.map (fun x => (x, i))
/-- The bunkbed graph in which the open edges of the lower level are `S₀`, those of the upper
level are `S₁`, and the **posts** over the transversal set `T` are always present. -/
abbrev bbGraph (T : Finset V) (S₀ S₁ : Finset (Sym2 V)) :
SimpleGraph (V × Fin 2) :=
ofEdges (S₀.image (liftLvl 0) ∪ S₁.image (liftLvl 1) ∪ T.image (fun x => s((x,0),(x,1))))
/-- Bunkbed percolation: the two levels are percolated **independently** with edge weights `w`,
while every post over `T` is retained. `bbProb E w T x y` is the probability that `x` and `y`
are connected. -/
def bbProb (E : Finset (Sym2 V)) (w : Sym2 V → ℚ) (T : Finset V)
(x y : V × Fin 2) : ℚ :=
∑ S₀ ∈ E.powerset, ∑ S₁ ∈ E.powerset,
(if (bbGraph T S₀ S₁).Reachable x y then 1 else 0) * weight E w S₀ * weight E w S₁
/-- The **bunkbed conjecture** (Kasteleyn 1985; Conjecture 1.1 of the source): for a connected
graph, a transversal set `T`, and `0 < p < 1`, a vertex in the lower level is at least as likely
to be connected to `v` downstairs as to its counterpart `v'` upstairs. -/
def BunkbedConjecture : Prop :=
∀ (V : Type) [Fintype V] [DecidableEq V] (E : Finset (Sym2 V)) (T : Finset V) (p : ℚ),
0 < p → p < 1 → (ofEdges E).Connected → ∀ u v : V,
bbProb E (fun _ => p) T (u, 0) (v, 0) ≥ bbProb E (fun _ => p) T (u, 0) (v, 1)
/-! ## Partition probabilities of a triple
For the hyperedge-simulation gadget one needs the probabilities of the five ways the
percolation can partition a distinguished triple `a b c` into connected components. -/
/-- `a`, `b`, `c` all in one component. -/
def Pabc (E : Finset (Sym2 V)) (w : Sym2 V → ℚ) (a b c : V) : ℚ :=
probOf E w (fun S => (ofEdges S).Reachable a b ∧ (ofEdges S).Reachable b c)
/-- `b`, `c` together, `a` separate. -/
def Pa_bc (E : Finset (Sym2 V)) (w : Sym2 V → ℚ) (a b c : V) : ℚ :=
probOf E w (fun S => (ofEdges S).Reachable b c ∧ ¬ (ofEdges S).Reachable a b)
/-- `a`, `b` together, `c` separate. -/
def Pab_c (E : Finset (Sym2 V)) (w : Sym2 V → ℚ) (a b c : V) : ℚ :=
probOf E w (fun S => (ofEdges S).Reachable a b ∧ ¬ (ofEdges S).Reachable a c)
/-- `a`, `c` together, `b` separate. -/
def Pac_b (E : Finset (Sym2 V)) (w : Sym2 V → ℚ) (a b c : V) : ℚ :=
probOf E w (fun S => (ofEdges S).Reachable a c ∧ ¬ (ofEdges S).Reachable a b)
/-- `a`, `b`, `c` pairwise separated. -/
def Pa_b_c (E : Finset (Sym2 V)) (w : Sym2 V → ℚ) (a b c : V) : ℚ :=
probOf E w (fun S => ¬ (ofEdges S).Reachable a b ∧ ¬ (ofEdges S).Reachable b c ∧
¬ (ofEdges S).Reachable a c)
/-! ## The hyperedge-simulation gadget `Gₙ` (Fig. 2 of the source)
`Gₙ` has vertices `a = 0` and `v₁, …, vₙ = 1, …, n`. The **spokes** `a–vᵢ` are retained with
probability `1 - P`, and the **path** edges `vᵢ–vᵢ₊₁` with probability `P`. -/
/-- Edge set of the gadget graph `Gₙ`. -/
def gadgetE (n : ℕ) : Finset (Sym2 (Fin (n + 1))) :=
(Finset.univ.filter (fun p : Fin (n + 1) × Fin (n + 1) =>
(p.1 = 0 ∧ p.2 ≠ 0) ∨ (1 ≤ p.1.val ∧ p.2.val = p.1.val + 1))).image (fun p => s(p.1, p.2))
/-- Edge weights of `Gₙ`: spokes (those meeting `a = 0`) get `1 - P`, path edges get `P`. -/
def gadgetW (n : ℕ) (P : ℚ) (e : Sym2 (Fin (n + 1))) : ℚ :=
if (0 : Fin (n + 1)) ∈ e then 1 - P else P
end BunkbedRead-back
What the Lean code literally says, in plain math · claude-opus-5
Read-back — Bunkbed namespace (14 declarations)
Throughout, is a type carrying a Fintype instance (finitely many vertices) and decidable equality; is the type of unordered pairs of elements of , including the diagonal pairs . All probabilities are elements of , not of — no declaration in the file carries a hypothesis that a weight lies in .
fromFinsetAdj (instance)
For every finite vertex type with decidable equality and every finite set of unordered pairs, this provides a decision procedure for the adjacency relation of the simple graph , obtained by transporting the decidability of the predicate " and " along Mathlib's characterisation . It asserts no mathematical fact; its role is to make every subsequent definition computable (and it is what allows the #eval checks reported below).
ofEdges (abbreviation)
For a finite set of unordered pairs, is the simple graph on the whole vertex type whose adjacency is
Every element of is a vertex of , including elements occurring in no pair of ; such vertices are isolated. Any diagonal pair is silently discarded — it creates no adjacency, since fromEdgeSet removes loops. Being an abbrev, this unfolds reducibly to fromEdgeSet ↑S.
weight
For a finite set of unordered pairs (the "edge universe"), a weight function , and a finite set of unordered pairs, this is the rational number
Both products are ordinary finite products over Finsets, with the empty product equal to . There is no hypothesis that : the function is total, and for it multiplies over all of (including pairs outside ) against over only. E.g. with and it returns , not . There is also no hypothesis , so may be negative or exceed .
probOf
Given , , and a predicate on finite sets of unordered pairs that is assumed decidable (a DecidablePred instance argument),
the sum ranging over all subsets of (the powerset of ), with the indicator ( if holds, otherwise). On this index set always holds, so is the genuine product measure that opens each independently with weight and closes it with weight ; the total mass is for every , including outside . This normalisation was confirmed by evaluation: for a single edge at , for a -edge path and a triangle at , and also for . Note that diagonal pairs lying in still contribute their / factors even though they produce no adjacency; the mass still normalises to and the marginal law of the genuine edges is unaffected (checked: with , , the mass is and the connection probability is ).
connProb
i.e. the total weight of those for which SimpleGraph.Reachable holds between and in the graph . Reachability here is the reflexive–transitive closure of adjacency, so it is reflexive: for every and every , including and isolated. There is no hypothesis . Evaluated values match the expected Bernoulli-percolation quantities: single edge at gives ; path at gives for and for ; the triangle at gives for ; and with non-uniform weights , the path gives , confirming the product (independent-edge) structure.
connProbU (abbreviation)
, i.e. connProb specialised to the constant weight function . It is declared but used nowhere else in the file.
liftLvl
For (an element of Fin 2) and an unordered pair of vertices, is the image of under , i.e.
an unordered pair in lying entirely inside level . The map is injective, so distinct pairs lift to distinct pairs; a diagonal pair lifts to a diagonal pair.
bbGraph (abbreviation)
For a finite set of vertices and finite sets of unordered pairs, is the simple graph on the vertex type (both full copies of ) given by applied to the union of three finite sets of pairs:
Thus level carries exactly the (lifted) pairs of , level exactly those of , and a vertical post joins to for exactly those , present unconditionally — the posts do not depend on , , or any weight. Vertices outside have no post. Post pairs are never diagonal, so none is discarded. Verified by inspecting the resulting edge set: has edge set , and has edge set .
bbProb
For , , and two vertices of the doubled vertex set ,
a double sum over the powerset of twice, with the indicator of reachability multiplied by the product of the two independent configuration weights. The two levels therefore carry independent samples from the same law (each edge is open on level with weight and, independently, open on level with weight ); the two levels are not coupled to a common configuration. The posts at are deterministic. Total mass is (). Independence and unconditional posts were confirmed numerically with on two vertices and :
- : and ;
- : exactly (post deterministic), and ;
- : , which is the value for two independent level-copies of the edge (a common-configuration coupling would have given ).
BunkbedConjecture
This is a def producing a Prop — a named statement, not a proved theorem. It asserts: for every type in the lowest universe Type 0, every Fintype and DecidableEq instance on , every finite set of unordered pairs of vertices, every finite set of post locations, and every rational with
(both strict), if the graph is Connected (Mathlib's Connected = preconnected and nonempty, so is forced), then
That is: with both levels percolated independently at the same constant edge-probability and posts present deterministically at exactly the vertices of , the probability that on level reaches on the same level is at least the probability that it reaches on the other level. The inequality is non-strict and points from the same-level probability (left) down to the cross-level probability (right). The source vertex is always taken on level ; there is no hypothesis , no hypothesis on (it may be empty, a singleton, or all of ), and no hypothesis that avoids diagonal pairs. Connectedness is required of the full graph , not of any percolated configuration.
Pabc
for vertices (not assumed distinct). Literally only the two reachabilities and are required; follows by transitivity of reachability, so this is the event that all lie in one component.
Pa_bc
Note the literal form: the positive clause is and the negated clause is (not ).
Pab_c
Literal form: positive clause , negated clause (not ).
Pac_b
Pa_b_c
all three reachabilities negated.
Joint behaviour of the five
Because Reachable is an equivalence relation on the vertices of , the only possible truth patterns of are , , , , . These are matched bijectively by , , , , respectively, so the five events are pairwise disjoint and exhaustive and the five quantities sum to the total mass . Confirmed by evaluation: for the path at with the values are , summing to ; with , ; for the triangle at , ; for , ; for the path with non-uniform weights , ; and in the degenerate case , , — each summing to .
gadgetE
For , a finite set of unordered pairs of , obtained by filtering all ordered pairs with
and taking the image under . Concretely this is the fan graph: all spokes for , together with the path edges for (the constraint forces ). It contains no diagonal pair, and the rim edge that would make it a wheel is absent. Evaluated: ; ; (a triangle); ; has the edges . In general for . The graph is Connected for all tested, including (one vertex, no edges).
gadgetW
For , a rational parameter , and any unordered pair of elements of ,
So every pair incident to the hub receives weight and every other pair receives weight — note the inversion: the spokes get , the rim/path edges get . The function is total on all of , so it assigns values to pairs not in as well (e.g. , ); only its values on matter inside . The argument plays no role beyond fixing the type, and there is no constraint . Checked: on with , the pairs receiving are exactly and those receiving are exactly .
Observations for the human auditor
These are factual flags about the code as written, not judgments of intent.
-
weightis a correct product measure only on the index set actually used. On it is exactly , andprobOf/bbProbonly ever evaluate it there, so the measures normalise to (verified). Butweightitself is total and returns non-probabilistic junk for ; any downstream lemma stated aboutweightwithout the hypothesis inherits that junk. -
No weight is constrained to anywhere.
probOf,connProb,Pabc, …,bbProbare signed rational sums. They still total , but individual "probabilities" can be negative or exceed : e.g. on the -path at , and at . OnlyBunkbedConjectureimposes , and only for the constant weight. Any theorem about these quantities that does not itself hypothesise will be a statement about signed measures. -
connProb,Pabc,Pa_bc,Pab_c,Pac_b,Pa_b_c,connProbU,gadgetE,gadgetWare all orphans. None of them appears inBunkbedConjecture, which uses onlybbProb. The conjecture is self-contained; the triple-partition family and the gadget are unused scaffolding within this file. -
The two-level construction does percolate the levels independently and does retain posts unconditionally. Both were confirmed numerically, not just read off the syntax: at on a single edge with both posts (a same-configuration coupling would give ), and exactly when .
-
Posts sit at exactly , and is completely unconstrained in the conjecture. In particular is allowed, which makes the right-hand side identically and the inequality trivially true; and is allowed, which makes the two events identical (since always), so the inequality holds with equality. More generally the inequality is an equality whenever or . Confirmed: path with gives vs ; triangle with gives vs ; triangle with , , gives vs . The statement is nevertheless not vacuous or trivial: on with , , , the two sides are and , a strict inequality in the stated direction.
-
The five triple-partition events are genuinely a partition (disjoint and exhaustive, summing to ), as argued from transitivity of reachability and confirmed on six examples. Their defining clauses are, however, asymmetrically phrased:
Pab_cnegates whilePa_bcandPac_bboth negate , andPabcomits the (derivable) clause . These are equivalent to the symmetric phrasings only because reachability is an equivalence relation — a downstream proof that manipulates them purely syntactically must supply that fact. -
Degenerate instances silently included. (then and the conjecture's two sides are and ); , , not assumed distinct; ; containing diagonal pairs , which consume weight factors but create no edges; in
gadgetE, giving the empty edge set on a one-vertex type; the single-vertex graph , , which satisfiesConnected. -
Universe restriction in the conjecture.
BunkbedConjecturequantifies over(V : Type), i.e.Type 0only, notType*. Every finite graph has aType 0model, so this is not a loss of generality, but a proof of the conjecture as stated establishes it only forType 0vertex types and would need transport to apply to aFintypein a higher universe. -
Naming.
gadgetE/gadgetWdo not name what they build; the object is the fan graph on (hub-plus-path, without the closing rim edge that would make it a wheel), with hub-incident edges weighted and path edges weighted .bbGraph's argument is the post set, not a spanning-tree or terminal set.Pab_cand friends do not literally state "the component structure is "; they state the two-clause conditions transcribed above.BunkbedConjectureis aProp-valued definition, so nothing in this file asserts or proves it.
Confirmed by the mission captain (proposal self-audit).