simple_graph_normalized_cycle_factor_two_word
Every individual disjoint cycle factor of a normalized allowed permutation can be isolated as a product of two actual hops. The intermediate baseline moves all vertices, so this does not assume idle moves in the original graph.
Statement
theorem simple_graph_normalized_cycle_factor_two_word {V : Type*} [Fintype V] [DecidableEq V] (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 : q ∈ p.cycleFactorsFinset) : ∃ w : List (Equiv.Perm V), (∀ h ∈ w, simple_graph_is_hop G h) ∧ w.length = 2 ∧ w.prod = q
- Source
- Routine word-metric/cycle-factor assembly for IN-262 / OP-543, using the verified baseline normalization. The remaining quadratic diameter theorem is conjectural; no diameter assumption is silently discharged and no research advance is claimed.
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- simple_graph_normalized_hop_recombineIf 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…
- simple_graph_normalized_hop_two_wordEvery normalized allowed permutation is the product of exactly two actual hops on an undirected graph. No vertex is allowed to wait during…
- 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.
- 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…
The proof, explained
To isolate any disjoint cycle factor q of a normalized hop p as a product of two hops, we first show that q agrees with p on its support and acts as the identity elsewhere. A recombination lemma then implies that q inherits the property of being a normalized hop with respect to the base hop h₀. The result follows by applying the two-word decomposition theorem for normalized hops to q.
For every vertex v, either q v = p v or q v = v.
We distinguish whether v lies in the support of q. If v ∈ supp(q), then because q is a cycle factor of p, q(v) = p(v) by Equiv.Perm.mem_cycleFactorsFinset_iff.mp. Otherwise, v ∉ supp(q), so q fixes v by Equiv.Perm.notMem_support.mp.
uses
Equiv.Perm.mem_cycleFactorsFinset_iff.mp,Equiv.Perm.notMem_support.mphave hq_agree : ∀ v : V, q v = p v ∨ q v = v := by intro v by_cases hv : v ∈ q.support · left exact (Equiv.Perm.mem_cycleFactorsFinset_iff.mp hq).2 v hv · right exact Equiv.Perm.notMem_support.mp hv
The cycle factor q is a normalized hop with respect to h₀.
Since h₀ is a hop, p is a normalized hop with respect to h₀, and q agrees with p or fixes every vertex, simple_graph_normalized_hop_recombine implies that q is also a normalized hop.
uses
simple_graph_normalized_hop_recombinehave hq_norm : simple_graph_normalized_hop G h₀ q := simple_graph_normalized_hop_recombine G h₀ p q hh₀ hp hq_agreeThere exists a list of two hops in G whose product equals q.
Applying simple_graph_normalized_hop_two_word to the normalized hop q produces a list of two actual hops whose product is q.
uses
simple_graph_normalized_hop_two_wordexact simple_graph_normalized_hop_two_word G h₀ q hh₀ hq_norm
Equiv.Perm.mem_cycleFactorsFinset_iff.mp- If a permutation q belongs to the cycle factors of p, then q is a cycle and q a = p a for every element a in the support of q.
Equiv.Perm.notMem_support.mp- If an element is not in the support of a permutation, the permutation fixes that element.
simple_graph_normalized_hop_recombine- If h₀ is a hop, p is a normalized hop with respect to h₀, and q agrees with p or fixes every vertex, then q is also a normalized hop with respect to h₀.
simple_graph_normalized_hop_two_word- Any normalized hop with respect to a base hop h₀ can be factored into a word of length 2 whose elements are hops.
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_cycle_factor_two_word {V : Type*} [Fintype V] [DecidableEq V] (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 : q ∈ p.cycleFactorsFinset) : ∃ w : List (Equiv.Perm V), (∀ h ∈ w, simple_graph_is_hop G h) ∧ w.length = 2 ∧ w.prod = q := by have hq_agree : ∀ v : V, q v = p v ∨ q v = v := by intro v by_cases hv : v ∈ q.support · left exact (Equiv.Perm.mem_cycleFactorsFinset_iff.mp hq).2 v hv · right exact Equiv.Perm.notMem_support.mp hv have hq_norm : simple_graph_normalized_hop G h₀ q := simple_graph_normalized_hop_recombine G h₀ p q hh₀ hp hq_agree exact simple_graph_normalized_hop_two_word G h₀ q hh₀ hq_norm