Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Bernoulli bond percolation, the bunkbed graph, and the bunkbed conjecture

Definition
BunkbedPercolation

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

combinatoricsgraph-theorypercolationprobability

Mathlib contains no percolation theory of any kind, so this file supplies the objects needed to state the bunkbed conjecture and its refutation.

Let GGG be a finite graph presented by an explicit edge set EEE, and let w:E→Qw : E \to \mathbb{Q}w:E→Q assign to each edge its retention probability. A configuration is a subset S⊆ES \subseteq ES⊆E of open edges, and it occurs with weight

P(S)  =  ∏e∈Sw(e)  ∏e∈E∖S(1−w(e)).\mathbb{P}(S) \;=\; \prod_{e \in S} w(e) \; \prod_{e \in E \setminus S} \bigl(1 - w(e)\bigr).P(S)=e∈S∏​w(e)e∈E∖S∏​(1−w(e)).

The connection probability P[u↔v]\mathbb{P}[u \leftrightarrow v]P[u↔v] is the total weight of the configurations in which uuu and vvv lie in the same connected component. The file provides this for general per-edge weights and for the uniform case w≡pw \equiv pw≡p.

Given a set TTT of transversal vertices, the bunkbed graph has vertex set V×{0,1}V \times \{0,1\}V×{0,1}: a copy of GGG in each level, together with a post joining (t,0)(t,0)(t,0) to (t,1)(t,1)(t,1) for each t∈Tt \in Tt∈T. 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 GGG, every TTT, every 0<p<10 < p < 10<p<1 and all u,vu,vu,v,

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

where v′v'v′ is the counterpart of vvv in the other level.

The file also defines the five partition probabilities of a distinguished triple a,b,ca,b,ca,b,c — 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 GnG_nGn​ of Fig. 2: vertices a,v1,…,vna, v_1, \dots, v_na,v1​,…,vn​, with spokes aaa–viv_ivi​ retained with probability 1−P1-P1−P and path edges viv_ivi​–vi+1v_{i+1}vi+1​ retained with probability PPP.

Formalization Note Everything is finite and Q\mathbb{Q}Q-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 n=3n=3n=3, P=1/3P=1/3P=1/3 they return 182/243182/243182/243, 1/2431/2431/243 and 46/8146/8146/81, matching the paper exactly.

Definition code
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 Bunkbed
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 - Sections 1 and 2 (percolation, bunkbed graph, Conjecture 1.1) and Section 4.1 / Fig. 2 (the gadget graph G_n).
Read-back

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

Read-back — Bunkbed namespace (14 declarations)

Throughout, VVV is a type carrying a Fintype instance (finitely many vertices) and decidable equality; Sym2(V)\mathrm{Sym2}(V)Sym2(V) is the type of unordered pairs s(u,v)s(u,v)s(u,v) of elements of VVV, including the diagonal pairs s(x,x)s(x,x)s(x,x). All probabilities are elements of Q\mathbb{Q}Q, not of [0,1][0,1][0,1] — no declaration in the file carries a hypothesis that a weight lies in [0,1][0,1][0,1].


fromFinsetAdj (instance)

For every finite vertex type VVV with decidable equality and every finite set SSS of unordered pairs, this provides a decision procedure for the adjacency relation of the simple graph fromEdgeSet(S)\mathrm{fromEdgeSet}(S)fromEdgeSet(S), obtained by transporting the decidability of the predicate "s(u,v)∈Ss(u,v)\in Ss(u,v)∈S and u≠vu\neq vu=v" along Mathlib's characterisation fromEdgeSet(S).Adj u v  ⟺  s(u,v)∈S∧u≠v\mathrm{fromEdgeSet}(S).\mathrm{Adj}\,u\,v \iff s(u,v)\in S \wedge u\neq vfromEdgeSet(S).Adjuv⟺s(u,v)∈S∧u=v. 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 SSS a finite set of unordered pairs, GS:=ofEdges(S)G_S := \mathrm{ofEdges}(S)GS​:=ofEdges(S) is the simple graph on the whole vertex type VVV whose adjacency is

u∼GSv  ⟺  s(u,v)∈S  and  u≠v.u \sim_{G_S} v \iff s(u,v) \in S \ \text{ and }\ u \neq v .u∼GS​​v⟺s(u,v)∈S  and  u=v.

Every element of VVV is a vertex of GSG_SGS​, including elements occurring in no pair of SSS; such vertices are isolated. Any diagonal pair s(x,x)∈Ss(x,x)\in Ss(x,x)∈S 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 EEE of unordered pairs (the "edge universe"), a weight function w:Sym2(V)→Qw : \mathrm{Sym2}(V)\to\mathbb{Q}w:Sym2(V)→Q, and a finite set SSS of unordered pairs, this is the rational number

wtE,w(S)  =  (∏e∈Swe)⋅(∏e∈E∖S(1−we)).\mathrm{wt}_{E,w}(S) \;=\; \Big(\prod_{e\in S} w_e\Big)\cdot\Big(\prod_{e\in E\setminus S} (1-w_e)\Big).wtE,w​(S)=(e∈S∏​we​)⋅(e∈E∖S∏​(1−we​)).

Both products are ordinary finite products over Finsets, with the empty product equal to 111. There is no hypothesis that S⊆ES\subseteq ES⊆E: the function is total, and for S⊈ES\not\subseteq ES⊆E it multiplies wew_ewe​ over all of SSS (including pairs outside EEE) against (1−we)(1-w_e)(1−we​) over E∖SE\setminus SE∖S only. E.g. with E=∅E=\varnothingE=∅ and S={s(0,1)}S=\{s(0,1)\}S={s(0,1)} it returns ws(0,1)w_{s(0,1)}ws(0,1)​, not 000. There is also no hypothesis 0≤we≤10\le w_e\le 10≤we​≤1, so wt\mathrm{wt}wt may be negative or exceed 111.

probOf

Given EEE, www, and a predicate ev\mathrm{ev}ev on finite sets of unordered pairs that is assumed decidable (a DecidablePred instance argument),

PE,w[ev]  =  ∑S⊆E[ev(S)]⋅wtE,w(S),\mathbb{P}_{E,w}[\mathrm{ev}] \;=\; \sum_{S \subseteq E} \big[\mathrm{ev}(S)\big]\cdot \mathrm{wt}_{E,w}(S),PE,w​[ev]=S⊆E∑​[ev(S)]⋅wtE,w​(S),

the sum ranging over all 2∣E∣2^{|E|}2∣E∣ subsets of EEE (the powerset of EEE), with [⋅][\cdot][⋅] the indicator (wt\mathrm{wt}wt if ev(S)\mathrm{ev}(S)ev(S) holds, 000 otherwise). On this index set S⊆ES\subseteq ES⊆E always holds, so wtE,w\mathrm{wt}_{E,w}wtE,w​ is the genuine product measure that opens each e∈Ee\in Ee∈E independently with weight wew_ewe​ and closes it with weight 1−we1-w_e1−we​; the total mass is ∑S⊆EwtE,w(S)=∏e∈E(we+(1−we))=1\sum_{S\subseteq E}\mathrm{wt}_{E,w}(S)=\prod_{e\in E}\big(w_e+(1-w_e)\big)=1∑S⊆E​wtE,w​(S)=∏e∈E​(we​+(1−we​))=1 for every www, including www outside [0,1][0,1][0,1]. This normalisation was confirmed by evaluation: 111 for a single edge at w≡1/3w\equiv 1/3w≡1/3, for a 222-edge path and a triangle at w≡1/2w\equiv 1/2w≡1/2, and also for w≡2w\equiv 2w≡2. Note that diagonal pairs s(x,x)s(x,x)s(x,x) lying in EEE still contribute their wew_ewe​ / (1−we)(1-w_e)(1−we​) factors even though they produce no adjacency; the mass still normalises to 111 and the marginal law of the genuine edges is unaffected (checked: with E={s(0,0),s(0,1)}E=\{s(0,0),s(0,1)\}E={s(0,0),s(0,1)}, w≡1/3w\equiv1/3w≡1/3, the mass is 111 and the 0 ⁣− ⁣10\!-\!10−1 connection probability is 1/31/31/3).

connProb

connE,w(u,v)  =  PE,w[ S↦u and v lie in the same connected component of GS ],\mathrm{conn}_{E,w}(u,v) \;=\; \mathbb{P}_{E,w}\big[\,S \mapsto u \text{ and } v \text{ lie in the same connected component of } G_S\,\big],connE,w​(u,v)=PE,w​[S↦u and v lie in the same connected component of GS​],

i.e. the total weight of those S⊆ES\subseteq ES⊆E for which SimpleGraph.Reachable holds between uuu and vvv in the graph GS=ofEdges(S)G_S=\mathrm{ofEdges}(S)GS​=ofEdges(S). Reachability here is the reflexive–transitive closure of adjacency, so it is reflexive: connE,w(u,u)=1\mathrm{conn}_{E,w}(u,u)=1connE,w​(u,u)=1 for every uuu and every EEE, including E=∅E=\varnothingE=∅ and uuu isolated. There is no hypothesis u≠vu\neq vu=v. Evaluated values match the expected Bernoulli-percolation quantities: single edge at p=1/3p=1/3p=1/3 gives 1/31/31/3; path 0 ⁣− ⁣1 ⁣− ⁣20\!-\!1\!-\!20−1−2 at p=1/2p=1/2p=1/2 gives 1/41/41/4 for conn(0,2)\mathrm{conn}(0,2)conn(0,2) and 1/21/21/2 for conn(0,1)\mathrm{conn}(0,1)conn(0,1); the triangle at p=1/2p=1/2p=1/2 gives 5/85/85/8 for conn(0,2)\mathrm{conn}(0,2)conn(0,2); and with non-uniform weights ws(0,1)=1/3w_{s(0,1)}=1/3ws(0,1)​=1/3, ws(1,2)=1/5w_{s(1,2)}=1/5ws(1,2)​=1/5 the path gives 1/151/151/15, confirming the product (independent-edge) structure.

connProbU (abbreviation)

connE,punif(u,v):=connE, w≡p(u,v)\mathrm{conn}_{E,p}^{\mathrm{unif}}(u,v) := \mathrm{conn}_{E,\,w\equiv p}(u,v)connE,punif​(u,v):=connE,w≡p​(u,v), i.e. connProb specialised to the constant weight function e↦pe\mapsto pe↦p. It is declared but used nowhere else in the file.

liftLvl

For i∈{0,1}i\in\{0,1\}i∈{0,1} (an element of Fin 2) and an unordered pair eee of vertices, liftLvli(e)\mathrm{liftLvl}_i(e)liftLvli​(e) is the image of eee under x↦(x,i)x\mapsto (x,i)x↦(x,i), i.e.

liftLvli(s(u,v))=s((u,i),(v,i)),\mathrm{liftLvl}_i\big(s(u,v)\big) = s\big((u,i),(v,i)\big),liftLvli​(s(u,v))=s((u,i),(v,i)),

an unordered pair in V×{0,1}V\times\{0,1\}V×{0,1} lying entirely inside level iii. The map x↦(x,i)x\mapsto(x,i)x↦(x,i) is injective, so distinct pairs lift to distinct pairs; a diagonal pair s(x,x)s(x,x)s(x,x) lifts to a diagonal pair.

bbGraph (abbreviation)

For TTT a finite set of vertices and S0,S1S_0, S_1S0​,S1​ finite sets of unordered pairs, BB(T,S0,S1)\mathrm{BB}(T,S_0,S_1)BB(T,S0​,S1​) is the simple graph on the vertex type V×{0,1}V\times\{0,1\}V×{0,1} (both full copies of VVV) given by ofEdges\mathrm{ofEdges}ofEdges applied to the union of three finite sets of pairs:

{ s((u,0),(v,0)):s(u,v)∈S0 }⏟level 0 horizontal  ∪  { s((u,1),(v,1)):s(u,v)∈S1 }⏟level 1 horizontal  ∪  { s((x,0),(x,1)):x∈T }⏟vertical posts.\underbrace{\{\,s((u,0),(v,0)) : s(u,v)\in S_0\,\}}_{\text{level }0\text{ horizontal}} \;\cup\; \underbrace{\{\,s((u,1),(v,1)) : s(u,v)\in S_1\,\}}_{\text{level }1\text{ horizontal}} \;\cup\; \underbrace{\{\,s((x,0),(x,1)) : x\in T\,\}}_{\text{vertical posts}} .level 0 horizontal{s((u,0),(v,0)):s(u,v)∈S0​}​​∪level 1 horizontal{s((u,1),(v,1)):s(u,v)∈S1​}​​∪vertical posts{s((x,0),(x,1)):x∈T}​​.

Thus level 000 carries exactly the (lifted) pairs of S0S_0S0​, level 111 exactly those of S1S_1S1​, and a vertical post joins (x,0)(x,0)(x,0) to (x,1)(x,1)(x,1) for exactly those x∈Tx\in Tx∈T, present unconditionally — the posts do not depend on S0S_0S0​, S1S_1S1​, or any weight. Vertices outside TTT have no post. Post pairs are never diagonal, so none is discarded. Verified by inspecting the resulting edge set: BB({0},{s(0,1)},∅)\mathrm{BB}(\{0\}, \{s(0,1)\}, \varnothing)BB({0},{s(0,1)},∅) has edge set {s((0,0),(1,0)), s((0,0),(0,1))}\{s((0,0),(1,0)),\,s((0,0),(0,1))\}{s((0,0),(1,0)),s((0,0),(0,1))}, and BB(∅,{s(0,1)},{s(0,1)})\mathrm{BB}(\varnothing, \{s(0,1)\}, \{s(0,1)\})BB(∅,{s(0,1)},{s(0,1)}) has edge set {s((0,0),(1,0)), s((0,1),(1,1))}\{s((0,0),(1,0)),\,s((0,1),(1,1))\}{s((0,0),(1,0)),s((0,1),(1,1))}.

bbProb

For EEE, www, TTT and two vertices x,yx,yx,y of the doubled vertex set V×{0,1}V\times\{0,1\}V×{0,1},

bbE,w,T(x,y)  =  ∑S0⊆E ∑S1⊆E[ x↔y in BB(T,S0,S1) ]⋅wtE,w(S0)⋅wtE,w(S1),\mathrm{bb}_{E,w,T}(x,y) \;=\; \sum_{S_0\subseteq E}\ \sum_{S_1\subseteq E} \big[\,x \leftrightarrow y \text{ in } \mathrm{BB}(T,S_0,S_1)\,\big]\cdot \mathrm{wt}_{E,w}(S_0)\cdot \mathrm{wt}_{E,w}(S_1),bbE,w,T​(x,y)=S0​⊆E∑​ S1​⊆E∑​[x↔y in BB(T,S0​,S1​)]⋅wtE,w​(S0​)⋅wtE,w​(S1​),

a double sum over the powerset of EEE 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 e∈Ee\in Ee∈E is open on level 000 with weight wew_ewe​ and, independently, open on level 111 with weight wew_ewe​); the two levels are not coupled to a common configuration. The posts at TTT are deterministic. Total mass is 111 (=1×1=1\times 1=1×1). Independence and unconditional posts were confirmed numerically with E={s(0,1)}E=\{s(0,1)\}E={s(0,1)} on two vertices and w≡1/3w\equiv 1/3w≡1/3:

  • T=∅T=\varnothingT=∅: bb((0,0),(0,1))=0\mathrm{bb}((0,0),(0,1))=0bb((0,0),(0,1))=0 and bb((0,0),(1,0))=1/3\mathrm{bb}((0,0),(1,0))=1/3bb((0,0),(1,0))=1/3;
  • T={0}T=\{0\}T={0}: bb((0,0),(0,1))=1\mathrm{bb}((0,0),(0,1))=1bb((0,0),(0,1))=1 exactly (post deterministic), and bb((0,0),(1,1))=1/3\mathrm{bb}((0,0),(1,1))=1/3bb((0,0),(1,1))=1/3;
  • T={0,1}T=\{0,1\}T={0,1}: bb((0,0),(1,1))=bb((0,0),(1,0))=5/9=1−(1−13)2\mathrm{bb}((0,0),(1,1))=\mathrm{bb}((0,0),(1,0))=5/9=1-(1-\tfrac13)^2bb((0,0),(1,1))=bb((0,0),(1,0))=5/9=1−(1−31​)2, which is the value for two independent level-copies of the edge (a common-configuration coupling would have given 1/31/31/3).

BunkbedConjecture

This is a def producing a Prop — a named statement, not a proved theorem. It asserts: for every type VVV in the lowest universe Type 0, every Fintype and DecidableEq instance on VVV, every finite set EEE of unordered pairs of vertices, every finite set T⊆VT\subseteq VT⊆V of post locations, and every rational ppp with

0<pandp<10 < p \quad\text{and}\quad p < 10<pandp<1

(both strict), if the graph ofEdges(E)\mathrm{ofEdges}(E)ofEdges(E) is Connected (Mathlib's Connected = preconnected and nonempty, so V≠∅V\neq\varnothingV=∅ is forced), then

∀ u,v∈V:bbE, w≡p, T((u,0),(v,0))  ≥  bbE, w≡p, T((u,0),(v,1)).\forall\, u, v \in V:\qquad \mathrm{bb}_{E,\,w\equiv p,\,T}\big((u,0),(v,0)\big) \;\ge\; \mathrm{bb}_{E,\,w\equiv p,\,T}\big((u,0),(v,1)\big).∀u,v∈V:bbE,w≡p,T​((u,0),(v,0))≥bbE,w≡p,T​((u,0),(v,1)).

That is: with both levels percolated independently at the same constant edge-probability ppp and posts present deterministically at exactly the vertices of TTT, the probability that uuu on level 000 reaches vvv on the same level is at least the probability that it reaches vvv 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 000; there is no hypothesis u≠vu\neq vu=v, no hypothesis on TTT (it may be empty, a singleton, or all of VVV), and no hypothesis that EEE avoids diagonal pairs. Connectedness is required of the full graph ofEdges(E)\mathrm{ofEdges}(E)ofEdges(E), not of any percolated configuration.

Pabc

Pabc  =  PE,w[ a↔b ∧ b↔c  in GS ]P_{abc} \;=\; \mathbb{P}_{E,w}\big[\,a \leftrightarrow b \ \wedge\ b \leftrightarrow c \ \text{ in } G_S\,\big]Pabc​=PE,w​[a↔b ∧ b↔c  in GS​]

for vertices a,b,c∈Va,b,c\in Va,b,c∈V (not assumed distinct). Literally only the two reachabilities a↔ba\leftrightarrow ba↔b and b↔cb\leftrightarrow cb↔c are required; a↔ca\leftrightarrow ca↔c follows by transitivity of reachability, so this is the event that a,b,ca,b,ca,b,c all lie in one component.

Pa_bc

Pa∣bc  =  PE,w[ b↔c ∧ ¬(a↔b) ].P_{a|bc} \;=\; \mathbb{P}_{E,w}\big[\,b \leftrightarrow c \ \wedge\ \neg(a \leftrightarrow b)\,\big].Pa∣bc​=PE,w​[b↔c ∧ ¬(a↔b)].

Note the literal form: the positive clause is b↔cb\leftrightarrow cb↔c and the negated clause is a↔ba\leftrightarrow ba↔b (not a↔ca\leftrightarrow ca↔c).

Pab_c

Pab∣c  =  PE,w[ a↔b ∧ ¬(a↔c) ].P_{ab|c} \;=\; \mathbb{P}_{E,w}\big[\,a \leftrightarrow b \ \wedge\ \neg(a \leftrightarrow c)\,\big].Pab∣c​=PE,w​[a↔b ∧ ¬(a↔c)].

Literal form: positive clause a↔ba\leftrightarrow ba↔b, negated clause a↔ca\leftrightarrow ca↔c (not b↔cb\leftrightarrow cb↔c).

Pac_b

Pac∣b  =  PE,w[ a↔c ∧ ¬(a↔b) ].P_{ac|b} \;=\; \mathbb{P}_{E,w}\big[\,a \leftrightarrow c \ \wedge\ \neg(a \leftrightarrow b)\,\big].Pac∣b​=PE,w​[a↔c ∧ ¬(a↔b)].

Pa_b_c

Pa∣b∣c  =  PE,w[ ¬(a↔b) ∧ ¬(b↔c) ∧ ¬(a↔c) ],P_{a|b|c} \;=\; \mathbb{P}_{E,w}\big[\,\neg(a\leftrightarrow b) \ \wedge\ \neg(b\leftrightarrow c) \ \wedge\ \neg(a\leftrightarrow c)\,\big],Pa∣b∣c​=PE,w​[¬(a↔b) ∧ ¬(b↔c) ∧ ¬(a↔c)],

all three reachabilities negated.

Joint behaviour of the five

Because Reachable is an equivalence relation on the vertices of GSG_SGS​, the only possible truth patterns of (a ⁣↔ ⁣b, b ⁣↔ ⁣c, a ⁣↔ ⁣c)\big(a\!\leftrightarrow\! b,\ b\!\leftrightarrow\! c,\ a\!\leftrightarrow\! c\big)(a↔b, b↔c, a↔c) are (T,T,T)(T,T,T)(T,T,T), (T,F,F)(T,F,F)(T,F,F), (F,T,F)(F,T,F)(F,T,F), (F,F,T)(F,F,T)(F,F,T), (F,F,F)(F,F,F)(F,F,F). These are matched bijectively by PabcP_{abc}Pabc​, Pab∣cP_{ab|c}Pab∣c​, Pa∣bcP_{a|bc}Pa∣bc​, Pac∣bP_{ac|b}Pac∣b​, Pa∣b∣cP_{a|b|c}Pa∣b∣c​ respectively, so the five events are pairwise disjoint and exhaustive and the five quantities sum to the total mass 111. Confirmed by evaluation: for the path 0 ⁣− ⁣1 ⁣− ⁣20\!-\!1\!-\!20−1−2 at p=1/2p=1/2p=1/2 with (a,b,c)=(0,1,2)(a,b,c)=(0,1,2)(a,b,c)=(0,1,2) the values are (1/4, 1/4, 1/4, 0, 1/4)(1/4,\,1/4,\,1/4,\,0,\,1/4)(1/4,1/4,1/4,0,1/4), summing to 111; with (a,b,c)=(0,2,1)(a,b,c)=(0,2,1)(a,b,c)=(0,2,1), (1/4, 1/4, 0, 1/4, 1/4)(1/4,\,1/4,\,0,\,1/4,\,1/4)(1/4,1/4,0,1/4,1/4); for the triangle at p=1/3p=1/3p=1/3, (7/27, 4/27, 4/27, 4/27, 8/27)(7/27,\,4/27,\,4/27,\,4/27,\,8/27)(7/27,4/27,4/27,4/27,8/27); for E=∅E=\varnothingE=∅, (0,0,0,0,1)(0,0,0,0,1)(0,0,0,0,1); for the path with non-uniform weights 1/3,1/51/3,1/51/3,1/5, (1/15, 2/15, 4/15, 0, 8/15)(1/15,\,2/15,\,4/15,\,0,\,8/15)(1/15,2/15,4/15,0,8/15); and in the degenerate case a=b=0a=b=0a=b=0, c=2c=2c=2, (1/4, 0, 3/4, 0, 0)(1/4,\,0,\,3/4,\,0,\,0)(1/4,0,3/4,0,0) — each summing to 111.

gadgetE

For n∈Nn\in\mathbb{N}n∈N, a finite set of unordered pairs of Fin(n+1)={0,1,…,n}\mathrm{Fin}(n+1)=\{0,1,\dots,n\}Fin(n+1)={0,1,…,n}, obtained by filtering all ordered pairs (p1,p2)(p_1,p_2)(p1​,p2​) with

(p1=0 ∧ p2≠0)or(1≤p1 ∧ p2=p1+1 as naturals)\big(p_1 = 0 \ \wedge\ p_2 \neq 0\big)\quad\text{or}\quad\big(1 \le p_1 \ \wedge\ p_2 = p_1 + 1 \text{ as naturals}\big)(p1​=0 ∧ p2​=0)or(1≤p1​ ∧ p2​=p1​+1 as naturals)

and taking the image under (p1,p2)↦s(p1,p2)(p_1,p_2)\mapsto s(p_1,p_2)(p1​,p2​)↦s(p1​,p2​). Concretely this is the fan graph: all nnn spokes {0,j}\{0,j\}{0,j} for 1≤j≤n1\le j\le n1≤j≤n, together with the path edges {i,i+1}\{i,i+1\}{i,i+1} for 1≤i≤n−11\le i\le n-11≤i≤n−1 (the constraint p2∈Fin(n+1)p_2\in\mathrm{Fin}(n+1)p2​∈Fin(n+1) forces p1+1≤np_1+1\le np1​+1≤n). It contains no diagonal pair, and the rim edge {n,1}\{n,1\}{n,1} that would make it a wheel is absent. Evaluated: gadgetE(0)=∅\mathrm{gadgetE}(0)=\varnothinggadgetE(0)=∅; gadgetE(1)={s(0,1)}\mathrm{gadgetE}(1)=\{s(0,1)\}gadgetE(1)={s(0,1)}; gadgetE(2)={s(0,1),s(0,2),s(1,2)}\mathrm{gadgetE}(2)=\{s(0,1),s(0,2),s(1,2)\}gadgetE(2)={s(0,1),s(0,2),s(1,2)} (a triangle); gadgetE(3)={s(0,1),s(0,2),s(0,3),s(1,2),s(2,3)}\mathrm{gadgetE}(3)=\{s(0,1),s(0,2),s(0,3),s(1,2),s(2,3)\}gadgetE(3)={s(0,1),s(0,2),s(0,3),s(1,2),s(2,3)}; gadgetE(5)\mathrm{gadgetE}(5)gadgetE(5) has the 999 edges s(0,1),…,s(0,5),s(1,2),s(2,3),s(3,4),s(4,5)s(0,1),\dots,s(0,5),s(1,2),s(2,3),s(3,4),s(4,5)s(0,1),…,s(0,5),s(1,2),s(2,3),s(3,4),s(4,5). In general ∣gadgetE(n)∣=2n−1|\mathrm{gadgetE}(n)| = 2n-1∣gadgetE(n)∣=2n−1 for n≥1n\ge1n≥1. The graph ofEdges(gadgetE(n))\mathrm{ofEdges}(\mathrm{gadgetE}(n))ofEdges(gadgetE(n)) is Connected for all nnn tested, including n=0n=0n=0 (one vertex, no edges).

gadgetW

For n∈Nn\in\mathbb{N}n∈N, a rational parameter PPP, and any unordered pair eee of elements of Fin(n+1)\mathrm{Fin}(n+1)Fin(n+1),

gadgetWn(P)(e)={1−Pif 0∈e,Potherwise.\mathrm{gadgetW}_n(P)(e) = \begin{cases} 1-P & \text{if } 0 \in e,\\[2pt] P & \text{otherwise.}\end{cases}gadgetWn​(P)(e)={1−PP​if 0∈e,otherwise.​

So every pair incident to the hub 000 receives weight 1−P1-P1−P and every other pair receives weight PPP — note the inversion: the spokes get 1−P1-P1−P, the rim/path edges get PPP. The function is total on all of Sym2(Fin(n+1))\mathrm{Sym2}(\mathrm{Fin}(n+1))Sym2(Fin(n+1)), so it assigns values to pairs not in gadgetE(n)\mathrm{gadgetE}(n)gadgetE(n) as well (e.g. gadgetW3(1/4)(s(1,3))=1/4\mathrm{gadgetW}_3(1/4)(s(1,3))=1/4gadgetW3​(1/4)(s(1,3))=1/4, gadgetW3(1/4)(s(0,0))=3/4\mathrm{gadgetW}_3(1/4)(s(0,0))=3/4gadgetW3​(1/4)(s(0,0))=3/4); only its values on EEE matter inside PE,w\mathbb{P}_{E,w}PE,w​. The argument nnn plays no role beyond fixing the type, and there is no constraint 0≤P≤10\le P\le 10≤P≤1. Checked: on gadgetE(3)\mathrm{gadgetE}(3)gadgetE(3) with P=1/4P=1/4P=1/4, the pairs receiving 3/43/43/4 are exactly {s(0,1),s(0,2),s(0,3)}\{s(0,1),s(0,2),s(0,3)\}{s(0,1),s(0,2),s(0,3)} and those receiving 1/41/41/4 are exactly {s(1,2),s(2,3)}\{s(1,2),s(2,3)\}{s(1,2),s(2,3)}.


Observations for the human auditor

These are factual flags about the code as written, not judgments of intent.

  1. weight is a correct product measure only on the index set actually used. On S⊆ES\subseteq ES⊆E it is exactly ∏e∈Swe∏e∈E∖S(1−we)\prod_{e\in S}w_e\prod_{e\in E\setminus S}(1-w_e)∏e∈S​we​∏e∈E∖S​(1−we​), and probOf / bbProb only ever evaluate it there, so the measures normalise to 111 (verified). But weight itself is total and returns non-probabilistic junk for S⊈ES\not\subseteq ES⊆E; any downstream lemma stated about weight without the hypothesis S⊆ES\subseteq ES⊆E inherits that junk.

  2. No weight is constrained to [0,1][0,1][0,1] anywhere. probOf, connProb, Pabc, …, bbProb are signed rational sums. They still total 111, but individual "probabilities" can be negative or exceed 111: e.g. conn(0,2)=4\mathrm{conn}(0,2)=4conn(0,2)=4 on the 222-path at w≡2w\equiv 2w≡2, and conn(0,1)=−1\mathrm{conn}(0,1)=-1conn(0,1)=−1 at w≡−1w\equiv -1w≡−1. Only BunkbedConjecture imposes 0<p<10<p<10<p<1, and only for the constant weight. Any theorem about these quantities that does not itself hypothesise we∈[0,1]w_e\in[0,1]we​∈[0,1] will be a statement about signed measures.

  3. connProb, Pabc, Pa_bc, Pab_c, Pac_b, Pa_b_c, connProbU, gadgetE, gadgetW are all orphans. None of them appears in BunkbedConjecture, which uses only bbProb. The conjecture is self-contained; the triple-partition family and the gadget are unused scaffolding within this file.

  4. The two-level construction does percolate the levels independently and does retain posts unconditionally. Both were confirmed numerically, not just read off the syntax: bb((0,0),(1,1))=5/9=1−(1−p)2\mathrm{bb}((0,0),(1,1))=5/9=1-(1-p)^2bb((0,0),(1,1))=5/9=1−(1−p)2 at p=1/3p=1/3p=1/3 on a single edge with both posts (a same-configuration coupling would give 1/31/31/3), and bb((0,0),(0,1))=1\mathrm{bb}((0,0),(0,1))=1bb((0,0),(0,1))=1 exactly when 0∈T0\in T0∈T.

  5. Posts sit at exactly TTT, and TTT is completely unconstrained in the conjecture. In particular T=∅T=\varnothingT=∅ is allowed, which makes the right-hand side identically 000 and the inequality trivially true; and T=VT=VT=V is allowed, which makes the two events identical (since v0↔v1v_0\leftrightarrow v_1v0​↔v1​ always), so the inequality holds with equality. More generally the inequality is an equality whenever u∈Tu\in Tu∈T or v∈Tv\in Tv∈T. Confirmed: path with T={0,1,2}T=\{0,1,2\}T={0,1,2} gives 9/169/169/16 vs 9/169/169/16; triangle with T={0,1,2}T=\{0,1,2\}T={0,1,2} gives 505/729505/729505/729 vs 505/729505/729505/729; triangle with T={0}T=\{0\}T={0}, u=0u=0u=0, gives 11/2711/2711/27 vs 11/2711/2711/27. The statement is nevertheless not vacuous or trivial: on gadgetE(3)\mathrm{gadgetE}(3)gadgetE(3) with T={0}T=\{0\}T={0}, u=1u=1u=1, v=3v=3v=3, p=1/2p=1/2p=1/2 the two sides are 1/21/21/2 and 441/1024441/1024441/1024, a strict inequality in the stated direction.

  6. The five triple-partition events are genuinely a partition (disjoint and exhaustive, summing to 111), as argued from transitivity of reachability and confirmed on six examples. Their defining clauses are, however, asymmetrically phrased: Pab_c negates a↔ca\leftrightarrow ca↔c while Pa_bc and Pac_b both negate a↔ba\leftrightarrow ba↔b, and Pabc omits the (derivable) clause a↔ca\leftrightarrow ca↔c. 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.

  7. Degenerate instances silently included. u=vu=vu=v (then conn=1\mathrm{conn}=1conn=1 and the conjecture's two sides are 111 and [u∈T][u\in T][u∈T]); aaa, bbb, ccc not assumed distinct; E=∅E=\varnothingE=∅; EEE containing diagonal pairs s(x,x)s(x,x)s(x,x), which consume weight factors but create no edges; n=0n=0n=0 in gadgetE, giving the empty edge set on a one-vertex type; the single-vertex graph V≅Fin 1V\cong\mathrm{Fin}\,1V≅Fin1, E=∅E=\varnothingE=∅, which satisfies Connected.

  8. Universe restriction in the conjecture. BunkbedConjecture quantifies over (V : Type), i.e. Type 0 only, not Type*. Every finite graph has a Type 0 model, so this is not a loss of generality, but a proof of the conjecture as stated establishes it only for Type 0 vertex types and would need transport to apply to a Fintype in a higher universe.

  9. Naming. gadgetE / gadgetW do not name what they build; the object is the fan graph on {0,…,n}\{0,\dots,n\}{0,…,n} (hub-plus-path, without the closing rim edge {n,1}\{n,1\}{n,1} that would make it a wheel), with hub-incident edges weighted 1−P1-P1−P and path edges weighted PPP. bbGraph's TTT argument is the post set, not a spanning-tree or terminal set. Pab_c and friends do not literally state "the component structure is {a,b}∣{c}\{a,b\}\mid\{c\}{a,b}∣{c}"; they state the two-clause conditions transcribed above. BunkbedConjecture is a Prop-valued definition, so nothing in this file asserts or proves it.

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