Reachability transports along an injective relabelling
ProvedBunkbedAux.reach_image_mapRelabelling 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 and any finite set of edges,
The implication from right to left is the easy one: carries each edge of to an edge of the image, so 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 , so a walk starting at never leaves the range, and applying a left inverse of 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 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 being constant, so that weights transport trivially — that the copy's five partition probabilities are the gadget's.
import Definitions.Def_BunkbedPercolation open Bunkbed Finset SimpleGraph
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