simple_graph_normalized_hop_one
The identity is allowed relative to any baseline hop.
Statement
theorem simple_graph_normalized_hop_one {V : Type*} (G : SimpleGraph V) (h₀ : Equiv.Perm V) (hh₀ : simple_graph_is_hop G h₀) : simple_graph_normalized_hop G h₀ 1
- 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
Classical.choiceQuot.soundpropext- 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.
The proof, explained
By definition, a permutation is a normalized hop relative to a baseline permutation $h₀$ if its composition with $h₀$ is a hop in the graph. For the identity permutation $1$, the composition $h₀ * 1$ is just $h₀$. The assertion therefore reduces immediately to the hypothesis that $h₀$ is already a hop.
The identity permutation $1$ is a normalized hop in $G$ relative to $h₀$. automation
By definition of `simple_graph_normalized_hop`, a permutation $p$ is a normalized hop relative to $h₀$ if $h₀ * p$ is a hop in $G$. For $p = 1$, the product $h₀ * 1$ simplifies to $h₀$. The goal thus reduces to showing that $h₀$ is a hop in $G$, which is precisely the hypothesis `hh₀`.
uses
simple_graph_normalized_hopsimpa [simple_graph_normalized_hop] using hh₀
simple_graph_normalized_hop- A permutation $p$ is a normalized hop relative to a baseline permutation $h₀$ on a graph $G$ if the composed permutation $h₀ * p$ is a hop in $G$ (that is, every vertex $v$ is adjacent to $(h₀ * p)(v)$).
- The simplifier automatically simplifies multiplication by the identity permutation ($h₀ * 1 = h₀$) using the standard group identity rule.
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_one {V : Type*} (G : SimpleGraph V) (h₀ : Equiv.Perm V) (hh₀ : simple_graph_is_hop G h₀) : simple_graph_normalized_hop G h₀ 1 := by simpa [simple_graph_normalized_hop] using hh₀