Theorem 1.2 — explicit counterexample on 7,222 vertices (planarity omitted)
ProvedBunkbedFalse.explicit_counterexampleThere exists a connected graph with vertices and edges, a transversal set with exactly three vertices, and vertices , such that in bunkbed percolation at ,
The graph is obtained by taking Hollom's hypergraph and substituting the gadget with for each of its six -hyperedges, placing the gadget so that its apex is the transversal vertex; this yields vertices and edges. Three is the smallest number of transversal vertices for which the conjecture can fail.
The probability gap is tiny — the source estimates it at less than — so no computational search could have detected it; the argument is entirely structural.
Formalization Note ⚠️ The published Theorem 1.2 also asserts that is planar, and that assertion is omitted here: Mathlib has no notion of a planar graph, so the property cannot currently be stated. The formalized statement is therefore strictly weaker than the published one. Adding planarity would be a welcome strengthening. The vertex count is carried by the carrier type Fin 7222.
Formalization Note (edge count). The edge count is stated as (ofEdges E).edgeFinset.card = 14442, i.e. the number of edges of the graph, rather than the cardinality of the defining Finset (Sym2 _). The two differ: Sym2 contains diagonal pairs , which fromEdgeSet silently discards, so constraining the raw Finset would have pinned the true edge count only to the range .
import Definitions.Def_BunkbedHypergraph open Bunkbed Bunkbed.Hyper SimpleGraph Finset
namespace BunkbedFalse
/-- **Theorem 1.2** (p. 1), with the planarity assertion omitted: Mathlib has no notion of a
planar graph. -/
theorem explicit_counterexample :
∃ (E : Finset (Sym2 (Fin 7222))) (T : Finset (Fin 7222)) (u v : Fin 7222),
(ofEdges E).edgeFinset.card = 14442 ∧ T.card = 3 ∧ (ofEdges E).Connected ∧
bbProb E (fun _ => (1 / 2 : ℚ)) T (u, 0) (v, 0)
< bbProb E (fun _ => (1 / 2 : ℚ)) T (u, 0) (v, 1) := by sorry
end BunkbedFalseRead-back
What the Lean code literally says, in plain math · claude-opus-5
Read-back — BunkbedFalse.explicit_counterexample
What is asserted
The declaration is a bare existential statement with no hypotheses and no parameters. It asserts that there exist
- a finite set of unordered pairs of elements of (the type ), i.e. is a finite set of symmetric pairs , possibly including diagonal pairs ;
- a subset ;
- two elements ;
such that all four of the following hold simultaneously.
Write for the simple graph on the vertex set (all elements) in which
(The construction is Mathlib's fromEdgeSet, so any diagonal pair present in is silently discarded and produces no loop.)
(1) Edge count.
This counts the edges of the graph , i.e. the number of off-diagonal pairs in . It is not : the cardinality of the data is left completely unconstrained above , because may additionally contain any of the diagonal pairs , so is permitted while the graph-edge count is pinned to exactly . (Verified by computation on a -cycle: adding two diagonal pairs to left the graph's edge count at while became , and left every probability below unchanged.)
(2) Post count. exactly.
(3) Connectivity. is connected in Mathlib's sense: is nonempty (automatic, ) and every ordered pair of vertices is joined by a walk. Because the vertex type is all of , connectivity is required on all vertices; no isolated or unused vertices are allowed, so the vertex count is genuinely pinned at by the type together with this condition.
(4) A strict reversal of the bunkbed inequality at .
Unfolding the probability
For a subset the configuration weight with the constant edge-weight function for every is
so (checked numerically, with and without diagonal pairs in ): this is honest Bernoulli() bond percolation on .
Given two open sets , the bunkbed graph is the simple graph on (so vertices) whose edges are exactly
the three vertical posts over being present with probability in every configuration. Then
where is reachability (reflexive: always). The two levels are percolated independently with the same law; both sides of (4) use the same , the same weight , the same , and the same source vertex .
Which side is smaller, and which levels are compared
- Left-hand side: and both in the bottom level — the same-level connection probability.
- Right-hand side: source in the bottom level, target in the top level — the opposite-level connection probability.
- The strict inequality makes the same-level probability the strictly smaller of the two. (The bunkbed conjecture as recorded in the same definition bundle asserts for all connected graphs, all and all ; the statement here asserts the opposite strict inequality for some explicit datum at , and does lie in .)
Numerical consistency of the stated counts
A connected simple graph on vertices needs at least edges and admits at most ; the required lies strictly between, so (1)+(3) are mutually satisfiable. The average degree is , i.e. just short of -regular (-regularity on vertices would require edges, so the graph cannot be -regular). The bunkbed graph then has vertices and at most edges. The percolation sum ranges over configuration pairs, so neither side can be evaluated directly; all claims below were settled on small analogues instead.
Degenerate routes are closed — what the existential cannot be met by
Each of the following would collapse (4), so the statement implicitly forces them to be avoided:
- is impossible. Reachability is reflexive, so the indicator on the left is in every configuration and the left side equals exactly , while the right side is at most ; a strict then fails. (Computed on the -cycle with : versus .) So is a consequence of (4).
- is impossible. The post is always open, so and lie in the same component in every configuration and the two sides are identically equal. (Computed: -cycle, , , gives on both sides.) So .
- is also impossible. Swapping the two levels is a weight-preserving involution of the configuration space, giving ; if then and are always in the same component, so the right side equals the left. (Computed: -cycle, , , gives on both sides.) So , and must be two distinct vertices among the outside .
- Both sides zero is impossible, since forces the right side to be strictly positive. The left side is automatically strictly positive: (3) makes connected, so the configuration (which carries weight ) already connects to ; hence and the assertion is that a strictly positive quantity is strictly exceeded.
- No empty or postless degeneracy. rules out (with the opposite-level probability is identically — computed as on the -cycle — so (4) would fail), and or any disconnected/spanning-deficient structure is ruled out by (1) and (3).
- Diagonal padding is inert, not exploitable. Adding pairs to enlarges the powerset sums but changes neither graph nor probabilities (computed: and before and after adding two diagonal pairs), so it can only slacken the reading of "", never the inequality (4).
- For reference, on the small analogues tested the inequality ran the other way (same-level versus opposite-level ), consistent with the reversal in (4) not being attainable by a small or generic structure.
Summary of every numeric constant appearing
Vertex type ( base vertices, bunkbed vertices); graph-edge count exactly ; exactly ; every edge open independently with probability exactly (the rational , on both levels, with the identical weight function on both sides); posts over open with probability ; levels indexed by (bottom) and (top); the compared pairs are and , with strict inequality (not , not ), and existence only (not uniqueness). No constraint is imposed on itself, on the degree sequence, on the girth, or on the identity of , , beyond .
Confirmed by the mission captain (proposal self-audit).