simple_graph_normalized_hop_recombine
If p is allowed relative to a baseline hop h0, and a PERMUTATION q chooses p(v) or v at each vertex, then q is also allowed relative to h0. The bijectivity of q remains an explicit hypothesis in its type.
Statement
theorem simple_graph_normalized_hop_recombine {V : Type*} (G : SimpleGraph V) (h₀ p q : Equiv.Perm V) (hh₀ : simple_graph_is_hop G h₀) (hp : simple_graph_normalized_hop G h₀ p) (hq : ∀ v, q v = p v ∨ q v = v) : simple_graph_normalized_hop G h₀ q
- Source
- Uniform structural helper for IN-262 / OP-543, using the hop and leap-group definitions of arXiv:2610.18463. The universal quadratic word bound is a question proposed here, not a theorem of that paper. No diameter estimate or research advance is claimed by this algebraic normalization.
- Verified
- 27 Oct 2026
- Axioms
Quot.sound- Built on 2
- simple_graph_normalized_hopA permutation p is allowed relative to baseline h0 when h0*p is an actual hop. Relative p may fix vertices; the resulting actual hop still…
- simple_graph_is_hopA hop (graph derangement) of a graph G is a permutation h of the vertices that sends every vertex v to a neighbour h(v) of v.
- Used by 1
- simple_graph_normalized_cycle_factor_two_wordEvery individual disjoint cycle factor of a normalized allowed permutation can be isolated as a product of two actual hops. The…
The proof, explained
To show that the permutation q is a normalized hop relative to the baseline hop h₀, we must verify that every vertex v is adjacent to h₀(q(v)). For any vertex v, the hypothesis provides that either q(v) = p(v) or q(v) = v. In the former case, the required adjacency holds because p is a normalized hop relative to h₀; in the latter case, it holds because h₀ is itself a hop.
To show that q is a normalized hop relative to h₀, it suffices to show that v is adjacent to h₀(q(v)) for an arbitrary vertex v.
By definition, q is a normalized hop relative to h₀ if the composition h₀ * q is a hop in G, which means that every vertex v is adjacent to (h₀ * q)(v) = h₀(q(v)). We fix an arbitrary vertex v and rewrite the goal into this explicit adjacency condition.
intro v change G.Adj v (h₀ (q v))
In the case where q(v) = p(v), the adjacency between v and h₀(q(v)) holds.
We split into cases using the hypothesis that q(v) = p(v) ∨ q(v) = v. In the first case, q(v) = p(v), substituting p(v) for q(v) yields the goal G.Adj v (h₀(p(v))), which holds directly by the assumption that p is a normalized hop relative to h₀.
rcases hq v with he | he · rw [he] exact hp v
In the case where q(v) = v, the adjacency between v and h₀(q(v)) holds.
In the second case, q(v) = v, substituting v for q(v) yields the goal G.Adj v (h₀(v)), which holds directly by the assumption that h₀ is a hop in G.
· rw [he] exact hh₀ v
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem simple_graph_normalized_hop_recombine {V : Type*} (G : SimpleGraph V) (h₀ p q : Equiv.Perm V) (hh₀ : simple_graph_is_hop G h₀) (hp : simple_graph_normalized_hop G h₀ p) (hq : ∀ v, q v = p v ∨ q v = v) : simple_graph_normalized_hop G h₀ q := by intro v change G.Adj v (h₀ (q v)) rcases hq v with he | he · rw [he] exact hp v · rw [he] exact hh₀ v