Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Adjacency in the Wierman--Ziff bunkbed graph

Proved
BunkbedAux.wzGraph_adj_iff

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

bunkbedcombinatoricsgraph-theorypercolationprobability

The graph realised by a Wierman--Ziff configuration ψ\psiψ on a bunkbed hypergraph is defined as the graph whose edge set is a union: over all pairs (hyperedge, level), the edges that the state at that pair contributes inside its triple, together with the vertical posts over the transversal set TTT. This lemma unfolds that definition into a usable adjacency criterion.

For vertices u,vu, vu,v of the bunkbed V×{0,1}V \times \{0,1\}V×{0,1},

u∼v  ⟺  (∃ (i,l), {u,v}∈edges(ψ(i,l), ti, l))  or  (u1=v1 ∧ u1∈T ∧ u2≠v2),u \sim v \iff \Bigl(\exists\, (i, l),\ \{u,v\} \in \mathrm{edges}\bigl(\psi(i,l),\, t_i,\, l\bigr)\Bigr) \ \text{ or } \ \bigl(u_1 = v_1 \ \wedge\ u_1 \in T \ \wedge\ u_2 \ne v_2\bigr),u∼v⟺(∃(i,l), {u,v}∈edges(ψ(i,l),ti​,l))  or  (u1​=v1​ ∧ u1​∈T ∧ u2​=v2​),

together with u≠vu \ne vu=v.

The second disjunct describes the posts: two vertices are joined by a post exactly when they share their underlying vertex, that vertex is transversal, and they sit on opposite levels. The first disjunct is deliberately left in terms of the state's edge set rather than expanded state by state, so that the criterion is uniform in the five Wierman--Ziff states.

The condition u≠vu \ne vu=v is retained because the construction passes through fromEdgeSet, which discards diagonal pairs; it cannot be dropped in general, since a hyperedge whose triple has a repeated vertex would otherwise contribute a loop.

Mathematical role. This is the basic tool for any argument that manipulates paths in the Wierman--Ziff bunkbed graph. In particular the involution argument for the robustness lemma proceeds by taking a path realising one connection event and transforming it into a path realising the other, reflecting the levels of the vertices lying beyond a distinguished hyperedge; checking that the transformed sequence is still a path is exactly a case analysis over this criterion, one case per edge type — post, hyperedge before the distinguished one, hyperedge after it, and the distinguished hyperedge itself.

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

/-- **Adjacency in the Wierman-Ziff bunkbed graph.** Two vertices are adjacent exactly when some
hyperedge, on some level, contributes the edge joining them, or they are the two ends of a post
over the transversal set. -/
theorem wzGraph_adj_iff {V : Type*} [Fintype V] [DecidableEq V]
    {ι : Type*} [Fintype ι] [DecidableEq ι]
    (t : ι → (V × V × V)) (T : Finset V) (ψ : ι × Fin 2 → WZ) (u v : V × Fin 2) :
    (wzGraph t T ψ).Adj u v ↔
      ((∃ p : ι × Fin 2, s(u, v) ∈ (ψ p).edges (t p.1) p.2)
        ∨ (u.1 = v.1 ∧ u.1 ∈ T ∧ u.2 ≠ v.2)) ∧ u ≠ v := 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, Section 3.2 (p. 3), where the Wierman-Ziff bunkbed hypergraph percolation model is defined.

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