Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Bunkbed reachability depends only on the per-copy boundary partitions

Proved
BunkbedFalse.bb_boundary_reduce

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

bunkbedcombinatoricsgraph-theorypercolation

This is the geometric heart of the gadget substitution: it says that the 7,2227{,}2227,222-vertex substituted graph and the 101010-vertex Wierman--Ziff graph have the same bunkbed connectivity between hypergraph vertices, provided each gadget copy realises the partition its state prescribes.

Let Si0S^0_iSi0​ and Si1S^1_iSi1​ be the open edges of copy iii on levels 000 and 111, and let ψ\psiψ assign a Wierman--Ziff state to each (hyperedge, level) pair. Assume the matching hypothesis: for every copy iii and level lll, the three attachment vertices of copy iii are joined by the open edges of that copy at that level exactly as ψ(i,l)\psi(i,l)ψ(i,l) says — the apex to the first path end iff ψ(i,l)∈{abc,ab∣c}\psi(i,l) \in \{abc, ab|c\}ψ(i,l)∈{abc,ab∣c}, the two path ends to each other iff ψ(i,l)∈{abc,a∣bc}\psi(i,l) \in \{abc, a|bc\}ψ(i,l)∈{abc,a∣bc}, and the apex to the second path end iff ψ(i,l)∈{abc,ac∣b}\psi(i,l) \in \{abc, ac|b\}ψ(i,l)∈{abc,ac∣b}. Then for all hypergraph vertices x,yx, yx,y and every level lll,

(x,0)↔(y,l) in the bunkbed over the substituted graph  ⟺  (x,0)↔(y,l) in the Wierman–Ziff bunkbed.(x,0) \leftrightarrow (y,l) \text{ in the bunkbed over the substituted graph} \iff (x,0) \leftrightarrow (y,l) \text{ in the Wierman--Ziff bunkbed}.(x,0)↔(y,l) in the bunkbed over the substituted graph⟺(x,0)↔(y,l) in the Wierman–Ziff bunkbed.

Why it holds: both graphs are unions of parts meeting only along the lifted hypergraph vertices — on one side the six copies at each level plus the posts, on the other the canonical state edge sets plus the posts. A copy's interior vertices are private to it, and the canonical edge sets have no interior vertices at all. So connectivity between boundary vertices depends only on what each part does to the boundary, and the matching hypothesis says the corresponding parts do the same thing.

Note the hypothesis is satisfiable and the statement is not vacuous: with every gadget edge closed, each copy realises the state a∣b∣ca|b|ca∣b∣c on both levels.

Mathematical role. This is what collapses the substituted graph's enormous configuration space onto the hypergraph. Combined with the factorisation of percolation across the edge-disjoint copies and the identification of each copy's partition probabilities with the gadget's, it shows that bunkbed percolation on the counterexample graph is a Wierman--Ziff model on Hollom's hypergraph — which is what allows the robustness lemma to transfer Hollom's hypergraph counterexample to an honest graph.

Preamble
import Definitions.Def_BunkbedSubstituted
open Bunkbed Bunkbed.Hyper Finset SimpleGraph
Formal statement
namespace BunkbedFalse

/-- **Bunkbed reachability depends only on the per-copy boundary partitions.** If, for every copy
and every level, the open edges of that copy connect its three attachment vertices exactly as the
Wierman-Ziff state prescribes, then reachability between lifted hypergraph vertices in the bunkbed
graph over the substituted graph agrees with reachability in the Wierman-Ziff graph. -/
theorem bb_boundary_reduce (S₀ S₁ : Fin 6 → Finset (Sym2 (Fin 7222)))
    (hsub : ∀ i, S₀ i ⊆ (gadgetE 1204).image (Sym2.map (Bunkbed.Sub.emb i)))
    (hsub' : ∀ i, S₁ i ⊆ (gadgetE 1204).image (Sym2.map (Bunkbed.Sub.emb i)))
    (ψ : Fin 6 × Fin 2 → WZ)
    (hmatch : ∀ (i : Fin 6) (l : Fin 2),
        ((ofEdges (if l = 0 then S₀ i else S₁ i)).Reachable
              (Bunkbed.Sub.emb i 0) (Bunkbed.Sub.emb i 1)
            ↔ (ψ (i, l) = WZ.abc ∨ ψ (i, l) = WZ.ab_c))
      ∧ ((ofEdges (if l = 0 then S₀ i else S₁ i)).Reachable
              (Bunkbed.Sub.emb i 1) (Bunkbed.Sub.emb i 1204)
            ↔ (ψ (i, l) = WZ.abc ∨ ψ (i, l) = WZ.a_bc))
      ∧ ((ofEdges (if l = 0 then S₀ i else S₁ i)).Reachable
              (Bunkbed.Sub.emb i 0) (Bunkbed.Sub.emb i 1204)
            ↔ (ψ (i, l) = WZ.abc ∨ ψ (i, l) = WZ.ac_b)))
    (x y : Fin 10) (l : Fin 2) :
    (bbGraph Bunkbed.Sub.subT (Finset.univ.biUnion S₀) (Finset.univ.biUnion S₁)).Reachable
        (Bunkbed.Sub.iota x, 0) (Bunkbed.Sub.iota y, l)
      ↔ (wzGraph hollomTriple hollomT ψ).Reachable (x, 0) (y, l) := by
  sorry

end BunkbedFalse
Source
N. Gladkov, I. Pak, A. Zimin, The bunkbed conjecture is false, PNAS 122 (2025) no. 24, e2420725122, https://doi.org/10.1073/pnas.2420725122, Section 4 (pp. 6-7), gadget substitution.

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