Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Path surgery: the involution turns a same-level connection into a cross-level one

Proved
BunkbedAux.involution_crosses

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

bunkbedcombinatoricsgraph-theorypercolationprobability

This is the combinatorial heart of the involution argument by which Gladkov--Pak--Zimin prove their robustness lemma.

Work with the Wierman--Ziff model on Hollom's hypergraph, in the refined pair state space, and let Ψ\PsiΨ be a refined configuration. Fix a hyperedge eee whose refined state lies in Λ+2\Lambda^2_+Λ+2​, and let ϕ=phiExt e\phi = \texttt{phiExt}\,eϕ=phiExte be the involution that leaves the hyperedges before eee along the path ρ\rhoρ untouched, applies the half-reflection η\etaη at eee, and applies the level swap ρ\rhoρ to every hyperedge after eee. Then

u1↔u10  in Ψ⟹u1↔u10′  in ϕ(Ψ).u_1 \leftrightarrow u_{10} \ \text{ in } \Psi \qquad \Longrightarrow \qquad u_1 \leftrightarrow u_{10}' \ \text{ in } \phi(\Psi).u1​↔u10​  in Ψ⟹u1​↔u10′​  in ϕ(Ψ).

That is, ϕ\phiϕ turns a same-level connection between the two endpoints into a cross-level one. Since ϕ\phiϕ is a weight-preserving involution, the configurations in which some hyperedge lies in Λ+2\Lambda^2_+Λ+2​ therefore contribute equally to the two connection events, and cancel from their difference — which reduces the robustness lemma to the configurations avoiding Λ+2\Lambda^2_+Λ+2​, where the model degenerates to the alternative bunkbed hypergraph model and Hollom's computation applies.

How the connection is transported. The proof exhibits a map on vertices, reflecting the level of every non-transversal vertex lying strictly beyond eee along ρ\rhoρ and fixing everything else. The source u1u_1u1​ sits at the start of ρ\rhoρ and is fixed; the target u10u_{10}u10​ sits at the end and is always reflected, which is exactly why a same-level connection becomes a cross-level one. The work is in checking that the image of a path is still a path, which is a case analysis over the four kinds of edge: a post, an edge of a hyperedge before eee, an edge of a hyperedge after eee, and an edge of eee itself. The last case is where Proposition 3.7 is used.

Formalization note. The vertex map is not a graph homomorphism, and the argument as printed in the source is slightly loose on this point. Transversal vertices cannot be reflected — each serves one hyperedge before eee and one after — so an edge joining a transversal vertex to a non-transversal one has exactly one endpoint moved, and its image is not an edge. What is true, and what is proved here, is that adjacency is carried to reachability: the mismatch is repaired using the post over the transversal vertex, which is present in every configuration. Reachability then transports along a walk by induction.

Preamble
import Definitions.Def_BunkbedWZSurgery
open Bunkbed Bunkbed.Hyper Finset SimpleGraph
Formal statement
namespace BunkbedAux

/-- **Lemma 3.8 of Gladkov-Pak-Zimin** (path surgery). If the state of hyperedge `e` lies in
`Λ²₊`, then the involution `phiExt e` carries a same-level connection `u₁ ↔ u₁₀` to a
cross-level connection `u₁ ↔ u₁₀'`. -/
theorem involution_crosses (e : Fin 6) (Ψ : Fin 6 → WZExt)
    (he : WZExt.inLamSq (Ψ e) = true)
    (hr : (wzGraph hollomTriple hollomT (wzOfExt Ψ)).Reachable
      ((0 : Fin 10), (0 : Fin 2)) ((9 : Fin 10), (0 : Fin 2))) :
    (wzGraph hollomTriple hollomT (wzOfExt (phiExt e Ψ))).Reachable
      ((0 : Fin 10), (0 : Fin 2)) ((9 : Fin 10), (1 : Fin 2)) := by
  sorry

end BunkbedAux
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, Lemma 3.8 (p. 5-6) with its proof.

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