Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Reachability transports along an injective relabelling

Proved
BunkbedAux.reach_image_map

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

bunkbedcombinatoricsgraph-theorypercolation

Relabelling the vertices of a graph by an injective map should not change which pairs of vertices are connected. This theorem is that statement for the edge-set presentation used here: for injective fff and any finite set SSS of edges,

f(u)↔f(v)  in  ofEdges(Sym2(f)[S])  ⟺  u↔v  in  ofEdges(S).f(u) \leftrightarrow f(v) \ \text{ in } \ \mathrm{ofEdges}\bigl(\mathrm{Sym}^2(f)[S]\bigr) \iff u \leftrightarrow v \ \text{ in } \ \mathrm{ofEdges}(S).f(u)↔f(v)  in  ofEdges(Sym2(f)[S])⟺u↔v  in  ofEdges(S).

The implication from right to left is the easy one: Sym2(f)\mathrm{Sym}^2(f)Sym2(f) carries each edge of SSS to an edge of the image, so fff is a graph homomorphism and homomorphisms preserve reachability.

The converse needs injectivity, and a little care: a walk in the image graph must be pulled back. Every edge of the image has both endpoints in the range of fff, so a walk starting at f(u)f(u)f(u) never leaves the range, and applying a left inverse of fff to it yields a walk in the original graph. Without injectivity the statement is false — a non-injective relabelling can merge two vertices and create connections that were not there.

Mathematical role. This is what allows a copy of a gadget, embedded in a larger graph, to be analysed as the gadget itself. In the counterexample graph of Theorem 1.2 each of the six gadget copies is an injective image of G1204G_{1204}G1204​ under a vertex map that sends the gadget's apex and path ends to the corresponding hyperedge vertices and its interior into a private block. This theorem says the copy's connectivity behaviour is that of the gadget, and hence — the weight function at P=1/2P = 1/2P=1/2 being constant, so that weights transport trivially — that the copy's five partition probabilities are the gadget's.

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

/-- **Reachability transports along an injective relabelling.** Relabelling the vertices by an
injective map carries the percolation configuration to its image and preserves connectivity. -/
theorem reach_image_map {V W : Type*} [Fintype V] [DecidableEq V] [Fintype W] [DecidableEq W]
    (f : V → W) (hf : Function.Injective f) (S : Finset (Sym2 V)) (u v : V) :
    (ofEdges (S.image (Sym2.map f))).Reachable (f u) (f v) ↔ (ofEdges S).Reachable 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 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