AFTD Auto-Formalizing Theoretical Domains

simple_graph_normalized_hop_recombine

theoremverified

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

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.

  1. 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.

    lines 6–7

      intro v
      change G.Adj v (h₀ (q v))
  2. 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₀.

    lines 8–10

      rcases hq v with he | he
      · rw [he]
        exact hp v
  3. 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.

    lines 11–12

      · 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

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
See it in the graphDiscuss this resultChallenge it