The bunkbed conjecture is false
ProvedBunkbedFalse.bunkbed_conjecture_falseThe bunkbed conjecture is false.
Kasteleyn's bunkbed conjecture (1985) asserts that for every finite connected graph , every set of transversal vertices, every retention probability and all ,
where percolation is performed independently on the two levels of the bunkbed graph, all posts above are retained, and denotes the counterpart of 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 and , at most two transversal vertices, and in the 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 , 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 with . 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 , 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.
import Definitions.Def_BunkbedHypergraph open Bunkbed Bunkbed.Hyper SimpleGraph Finset
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
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:
So the theorem to be proved is: there exist a finite type (with decidable equality), a finite edge multiset , a subset , and a rational , satisfying all three hypotheses , , and connected, together with some pair , for which the inequality fails; since the quantities are rationals and is a linear order, failure means the strict reverse inequality
Unfolding the objects
Base graph. is the type of unordered pairs from , including diagonal pairs . For a finite set of such pairs, is the simple graph on with iff and ; diagonal elements of are silently discarded as adjacencies.
Connectivity hypothesis. is Mathlib's notion: is nonempty and every pair of vertices of is joined by a walk in the deterministic graph . This is a condition on the full edge set , not on any percolation realisation, and not on the bunkbed graph.
The bunkbed graph. For and , the graph has vertex set and edge set
That is: the lower level carries the open edges , the upper level carries the open edges , and the posts over exactly the vertices of are deterministically present (they are not percolated).
The measure. With uniform weight , the weight of a configuration is
i.e. each element of is retained independently with probability . The connection probability is the explicit double sum
so the two levels are percolated independently with the same parameter on the same edge set . Reachability is Mathlib's Reachable (reflexive: always holds). All arithmetic is over ; 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:
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:
- a type in universe with
FintypeandDecidableEqinstances; - a finite set of unordered pairs on ;
- a finite set of post locations;
- a rational together with proofs and (both strict);
- a proof that is connected (in particular );
- vertices ;
- a proof that .
Because the definitions are computable, item 7 is in principle a finite rational computation over 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.
- . Then holds in every configuration, so the left side is , while the right side is a probability . Strict reverse inequality impossible. (Verified: left , right on a path with .)
- (empty transversal). With no posts, every edge of preserves the level coordinate, so and are never reachable and the right side is identically left side. (Verified by evaluation: cross-level probability .) So the "always-retained posts over " clause is what makes the right-hand side nonzero at all, and a counterexample must take .
- Empty / degenerate graph. forces nonempty, so is excluded. is admissible only when , which forces and left side . (Verified.)
- at an endpoint. Excluded: both and are strict, so cannot be used. (Even if allowed, neither endpoint violates the inequality.)
- Diagonal junk in . may legitimately contain self-pairs ; these consume a coin flip in
weightbut contribute no adjacency. Since the same drives both levels, such dummy coins cancel and cannot be exploited. (Verified: adding to a path leaves both probabilities unchanged at .) - Hypotheses vacuous? No. The three hypotheses are jointly satisfiable in abundance (e.g. any connected with ), 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 , all interior probabilities, and all ordered pairs — so refuting it requires only one witness. Two genuine narrowings are present and should be noted:
- ranges over , not . The conjecture is asserted only at rational retention probabilities, so a witness must be a rational with ; a phenomenon occurring only at irrational would not refute this statement.
- is restricted to universe (written
Type, notType*), and carriesFintype— 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 , 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.
Confirmed by the mission captain (proposal self-audit).