Hypergraph percolation, Hollom's hypergraph, and the Wierman-Ziff model
DefinitionBunkbedHypergraphThis file supplies the hypergraph side of the argument: hypergraph percolation, Hollom's example, and the Wierman–Ziff model.
A hypergraph is a finite family of hyperedges, each a set of vertices. As with graphs one forms the bunkbed hypergraph over a transversal set , with two levels and posts above .
In the alternative bunkbed hypergraph percolation, each hyperedge is retained on exactly one of the two levels and deleted on the other, the choice being a fair coin, independently across hyperedges. For a hypergraph with hyperedges there are therefore equally likely configurations. Two vertices are connected when a path joins them, where all vertices of a retained hyperedge are mutually connected and posts may be used freely.
Hollom's hypergraph is the -uniform hypergraph on with the six hyperedges
with transversal set . Each hyperedge contains exactly one transversal vertex, which is listed first.
The Wierman–Ziff model refines hyperedge percolation. Rather than being simply present or absent, a hyperedge takes one of five states — it connects all three vertices, exactly one of the three pairs, or none — with prescribed probabilities summing to , independently across hyperedges. Ordinary hypergraph percolation is the special case in which only the all-three and none states occur. This extra freedom is what lets a hyperedge be approximated by a gadget graph, which is the crux of the whole argument, since a hyperedge cannot be simulated exactly.
Formalization Note Hyperedges are ordered triples, so that the distinguished transversal vertex is the first coordinate, matching the ordering the source fixes along its path . The five WZ states are an inductive type with a Fintype instance, and a state determines which pairs of its hyperedge's vertices are linked at a given level. Hollom's hypergraph and the alternative-model probabilities were validated by direct computation: they reproduce and , exactly the values of Lemma 3.1.
import Definitions.Def_BunkbedPercolation
/-!
# Hypergraph percolation, Hollom's example, and the Wierman–Ziff model
Section 3 of Gladkov–Pak–Zimin, *The bunkbed conjecture is false*, PNAS 122 (2025) e2420725122.
-/
namespace Bunkbed.Hyper
open Bunkbed SimpleGraph Finset
variable {V : Type*} [Fintype V] [DecidableEq V]
/-- The underlying vertex set of an ordered hyperedge `(a,b,c)`. -/
def tripleSet (t : V × V × V) : Finset V := {t.1, t.2.1, t.2.2}
/-- All edges of the clique on `s`, placed at level `l` of the bunkbed. -/
def cliqueAt (s : Finset V) (l : Fin 2) : Finset (Sym2 (V × Fin 2)) :=
((s ×ˢ s).filter (fun p => p.1 ≠ p.2)).image (fun p => s((p.1, l), (p.2, l)))
/-- The vertical posts over the transversal set `T`; these are always retained. -/
def posts (T : Finset V) : Finset (Sym2 (V × Fin 2)) := T.image (fun t => s((t, 0), (t, 1)))
/-! ## Alternative bunkbed hypergraph percolation -/
/-- In the **alternative** model each hyperedge `i` is retained on exactly one of the two
levels — `σ i` — and deleted on the other. Posts over `T` are always present. -/
abbrev altBBGraph {ι : Type*} [Fintype ι] (e : ι → Finset V) (T : Finset V) (σ : ι → Fin 2) :
SimpleGraph (V × Fin 2) :=
ofEdges ((Finset.univ.biUnion (fun i => cliqueAt (e i) (σ i))) ∪ posts T)
/-- `ℙᵃˡᵗ[x ↔ y]`: all `2^{|ι|}` level-assignments are equally likely. -/
def altProb {ι : Type*} [Fintype ι] [DecidableEq ι] (e : ι → Finset V) (T : Finset V)
(x y : V × Fin 2) : ℚ :=
(∑ σ : ι → Fin 2, if (altBBGraph e T σ).Reachable x y then (1 : ℚ) else 0)
/ 2 ^ Fintype.card ι
/-! ## Hollom's 3-uniform hypergraph (Fig. 1)
Ordered as in the path `ρ` of Eq. [5], so that in each hyperedge `(a,b,c)` the first vertex
`a` is the transversal one. Vertices `uᵢ ↦ i-1`, so `u₁ = 0`, …, `u₁₀ = 9`. -/
def hollomTriple : Fin 6 → (Fin 10 × Fin 10 × Fin 10) :=
![(1, 0, 2), (8, 2, 5), (6, 5, 4), (1, 4, 3), (6, 3, 7), (8, 7, 9)]
/-- The six hyperedges of Hollom's hypergraph, as vertex sets. -/
def hollomE (i : Fin 6) : Finset (Fin 10) := tripleSet (hollomTriple i)
/-- Hollom's transversal set `T = {u₂, u₇, u₉}`. -/
def hollomT : Finset (Fin 10) := {1, 6, 8}
/-! ## The Wierman–Ziff five-state model -/
/-- The five states of a hyperedge `(a,b,c)` in the WZ model: which of its vertices the
hyperedge connects. -/
inductive WZ | abc | ab_c | ac_b | a_bc | a_b_c
deriving DecidableEq, Repr
instance : Fintype WZ := ⟨{.abc, .ab_c, .ac_b, .a_bc, .a_b_c}, by intro x; cases x <;> decide⟩
/-- The pairs of vertices that state `s` links, for the hyperedge `t = (a,b,c)` at level `l`. -/
def WZ.edges (s : WZ) (t : V × V × V) (l : Fin 2) : Finset (Sym2 (V × Fin 2)) :=
let a : V × Fin 2 := (t.1, l)
let b : V × Fin 2 := (t.2.1, l)
let c : V × Fin 2 := (t.2.2, l)
match s with
| .abc => {s(a, b), s(b, c), s(a, c)}
| .ab_c => {s(a, b)}
| .ac_b => {s(a, c)}
| .a_bc => {s(b, c)}
| .a_b_c => ∅
/-- The graph realised by a WZ configuration `ψ`, which assigns a state to each hyperedge on
each of the two levels. Posts over `T` are always present. -/
abbrev wzGraph {ι : Type*} [Fintype ι] [DecidableEq ι] (t : ι → (V × V × V)) (T : Finset V)
(ψ : ι × Fin 2 → WZ) : SimpleGraph (V × Fin 2) :=
ofEdges ((Finset.univ.biUnion (fun p : ι × Fin 2 => (ψ p).edges (t p.1) p.2)) ∪ posts T)
/-- `ℙʷᶻ[x ↔ y]`, where each hyperedge on each level independently takes state `s` with
probability `P s`.
⚠️ This carries **no internal normalisation**: `P` is an arbitrary `WZ → ℚ`, so the total mass
is `(∑ s, P s) ^ (2 * |ι|)`. Comparing two values of `wzProb` is only meaningful when the caller
supplies a genuine distribution, i.e. `0 ≤ P s` for every `s` and `∑ s, P s = 1`. (Contrast
`altProb`, which normalises internally and always lands in `[0,1]`.) -/
def wzProb {ι : Type*} [Fintype ι] [DecidableEq ι] (t : ι → (V × V × V)) (T : Finset V)
(P : WZ → ℚ) (x y : V × Fin 2) : ℚ :=
∑ ψ : ι × Fin 2 → WZ,
(if (wzGraph t T ψ).Reachable x y then (1 : ℚ) else 0) * ∏ p : ι × Fin 2, P (ψ p)
end Bunkbed.HyperRead-back
What the Lean code literally says, in plain math · claude-opus-5
Read-back — Bunkbed.Hyper (file building on Bunkbed)
All declarations live in namespace Bunkbed.Hyper and import the companion file Def_BunkbedPercolation.lean. Throughout, is an arbitrary finite type with decidable equality, and the ambient vertex set of every graph constructed here is the two-level set (levels written , i.e. Fin 2). Two pieces of imported vocabulary are used constantly and are unfolded here once:
- , for a finite set of unordered pairs (
Sym2) of vertices, is the simple graph whose adjacency is " and ". It is Mathlib'sfromEdgeSet, so any self-loop listed in is silently discarded, and the graph is automatically symmetric. Reachableis ordinary graph connectivity (existence of a walk), and is reflexive: every vertex is reachable from itself, even in the empty graph.
1. tripleSet
Given an ordered triple , is the finite set .
This is a set literal, so duplicates collapse: the ordering of the three coordinates is discarded, and if two or three coordinates coincide the result has cardinality or rather than . Nothing in the definition requires the three coordinates to be distinct.
2. cliqueAt
For a finite set and a level ,
i.e. the edge set of the complete graph on the copies of sitting at level , and nothing else. Concretely it is formed by taking the ordered pairs with and mapping each to the unordered pair ; the two orderings of a pair give the same unordered pair, so the result has exactly elements.
Every edge produced has both endpoints at the same level : no cross-level (post-like) edge and no edge at the opposite level is created. Verified by computation: for a -element one gets exactly edges, all at level ; for a -element , edges. Degenerate cases: if (in particular ) the result is the empty edge set.
3. posts
For ,
the set of vertical "post" edges joining each vertex of to its own copy on the other level. Vertices outside get no post.
4. altBBGraph — the level-assignment two-level graph
Parameters: a finite index type , a family of finite subsets of (nothing forces them to have size , to be distinct, or to be non-empty), a set , and a function . Then
Literally: for each index , the vertices of are made into a clique at the single level , and no edge whatsoever is contributed by at the other level — the counterpart clique is absent, not merely optional. Cliques of different indices are unioned, so indices whose sets share a vertex and are assigned the same level have their cliques merged; a shared vertex assigned to different levels contributes no connection between the two copies except through posts. The posts over are present deterministically, in every configuration , and are the only cross-level edges in the graph. This is an abbrev (reducible), so decidability instances fire through it.
5. altProb — uniform average over level assignments
For , as above and two two-level vertices ,
The sum ranges over all functions and the denominator is exactly , so this is the uniform (unweighted) probability that and are connected when each index is placed independently at level or level with probability . There is no free parameter : the model has no edge-percolation at all; the only randomness is the choice of level per index. The quantity therefore always lies in , and equals whenever (confirmed by evaluation). If is empty the denominator is and the single graph is .
6. hollomTriple, hollomE, hollomT — the concrete instance
is the explicit list of ordered triples
on the -element vertex type , and is the corresponding unordered -element set. The distinguished set is .
Computed facts (all checked by evaluation):
- Each of the six sets has cardinality exactly ; as sets they are , and all six are pairwise distinct.
- Their union is all ten vertices .
- Each hyperedge meets in exactly one vertex: , , , , , .
- In every one of the six ordered triples the first coordinate (the one that
WZ.edgescalls ) is precisely the -vertex, and the second and third coordinates ( and ) are never in . - Each element of lies in exactly two hyperedges (; ; ). Vertex-degrees (number of hyperedges containing a vertex) are for vertices and for vertices and .
- Pairwise intersections: for the consecutive pairs (shared vertices respectively) and for the pairs (shared -vertices ); all six remaining pairs are disjoint. In particular , so the "consecutive" chain is a path of six hyperedges, not a closed cycle, with the degree-one vertices and at the two ends; the closure into a cycle is provided only by the three -vertices.
discards the ordering of each triple, so the alternative model of §4–§5 cannot see which vertex is ; only the model of §8–§10, which consumes directly, can.
7. WZ and its Fintype instance
WZ is an inductive type with exactly five constructors, named abc, ab_c, ac_b, a_bc, a_b_c, with decidable equality and a printable representation. The supplied finiteness instance lists these five as the element set and proves by case analysis that every term appears. Evaluation confirms , so the list has no omission and no duplicate.
8. WZ.edges — the edge set a state contributes
Given a state , an ordered triple and a level , write , , — all three at the same level . Then
Verified by evaluation on a triple of distinct vertices: abc contributes all three pairs (cardinality ); ab_c contributes only; ac_b contributes only; a_bc contributes only; a_b_c contributes nothing; and no state ever contributes an edge at the level . Thus, read as partitions of induced by the contributed edges in isolation, the five states realise , , , , — the five set partitions of a -element set, each exactly once, matching the naming convention of the companion file's .
Caveat on the general (non-hollom) case: the definition places no distinctness hypothesis on . If, say, , then ab_c contributes only the self-loop , which ofEdges deletes, making ab_c behave identically to a_b_c; and abc degenerates to a -element edge set. Note also that the induced partition is only "as named" in isolation: once the union with other triples' edges and with the posts is taken, , , may well end up connected through other parts of the graph even in state a_b_c.
9. wzGraph — the state-assignment two-level graph
Parameters: a finite index type with decidable equality, a family of ordered triples , a set , and an assignment . Then
Note the shape of the index: a state is drawn for every pair (index, level) — that is, states in all — so in this model each triple receives a state at level and an independent state at level . Nothing ties the two levels of a given together, and nothing deletes either copy; this differs from altBBGraph, where each index lives at exactly one level. The posts over are again present deterministically in every configuration and are the only cross-level edges.
10. wzProb — weighted sum over state assignments
For , as above, an arbitrary function , and ,
a sum over all state assignments, each weighted by the product of the single-state weights — i.e. the states are weighted as if independent across both indices and levels.
There is no hypothesis anywhere that is a probability distribution: is an arbitrary rational-valued function, not required to be non-negative and not required to satisfy , and there is no normalising denominator. Consequently need not lie in and need not be monotone in the event. Confirmed by evaluation on a two-triple example: with (which does sum to ) one gets as expected, whereas with one gets . The total mass of the measure is , so any downstream statement comparing two wzProb values silently depends on the caller supplying a with and ; otherwise the "probabilities" are arbitrary rationals. By contrast, altProb carries its normalisation internally and is always a genuine probability.
11. Cross-cutting remarks
- Neither
altBBGraph/altProbnorwzGraph/wzProbcontains any Bernoulli edge-percolation: the importedweight,probOf,connProb,bbProbmachinery of the companion file, and its retention parameter , are not used by any declaration in this file. The only randomness is, respectively, the level assignment and the state assignment . - In both models the posts over are present with probability and are the only edges joining level to level ; hence and (for a probability vector ) are between the two copies of any vertex that is not reachable to some -vertex within a level (evaluation confirms in a small example where ).
- No hypothesis anywhere requires the index families or to be injective, to have -element images, or to be non-degenerate; no hypothesis requires to be a transversal of the family, to be non-empty, or to be disjoint from anything. All such properties hold for the concrete
hollomdata (as tabulated in §6) but are not part of any definition's signature. hollomTriple,hollomE,hollomTare bare data declarations: they assert nothing and are consistent by construction. They become mathematically meaningful only when fed to the models above, and note thathollomE(unordered) andhollomTriple(ordered) feed different models.
Confirmed by the mission captain (proposal self-audit).