simple_graph_is_hop
def
A 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.
Statement
def simple_graph_is_hop {V : Type*} (G : SimpleGraph V) (h : Equiv.Perm V) : Prop
- Defined in
- arXiv:2610.18463 (The group generated by a graph's derangements), Sec. 1 (definition of a hop; called a graph derangement in earlier work).
- Verified
- 15 Oct 2026
- Axioms
- none listed
- Used by 39
- kayak_paddle_three_three_one_leap_group_eq_topThe kayak paddle graph KP(3, 3, 1) (two triangles joined by an edge, 6 vertices) has full leap group S_6.
- simple_graph_is_hop_top_iffIn a complete graph, the hops are exactly the derangements (fixed-point-free permutations).
- simple_graph_two_le_card_of_connected_hopEvery connected simple graph on a finite vertex set that admits a hop has at least two vertices.
- op_300_prism_three_leap_group_eq_topFor n = 3, the triangular prism graph P₁ □ C₃ on 6 vertices has full leap group S₆.
- 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_completeGraph_three_leap_closed_not_intersection_closedThe collection of leap-closed edge subsets of the complete graph K₃ on 3 vertices is not closed under intersection.
- simple_graph_is_hop_invThe inverse of a hop is a hop (the graph is undirected).
- kayak_paddle_leap_group_ne_of_even_cycleIf one of the two cycles of the kayak paddle graph KP(k, m, l) has even length, its leap group is neither the symmetric nor the…
- simple_graph_leap_groupThe leap group Λ₁(G) of a graph G: the subgroup of the symmetric group on the vertices generated by the hops of G.
- op_543_completeGraph_three_hop_word_length_le_oneFor the complete graph K₃ on 3 vertices, every element of its leap group is the product of at most 1 hop.
- 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…
- kayak_paddle_hop_maps_second_cycleIn KP(k, m, l) with m even, every hop maps the vertex set of the second cycle (the m-cycle) into itself.
- simple_graph_leap_group_bipartite_ne_topLet G be a bipartite simple graph on a finite vertex set with at least 4 vertices. Then its leap group Λ₁(G) is not the full symmetric…
- simple_graph_normalized_hop_group_conjugate_invConjugation by the inverse baseline also preserves the normalized subgroup.
- simple_graph_normalized_hop_conjugate_memConjugating one normalized allowed permutation by the baseline yields an element of the normalized SUBGROUP, without claiming it stays in…
- simple_graph_normalized_hop_oneThe identity is allowed relative to any baseline hop.
- simple_graph_normalized_hop_group_square_invThe inverse square of a baseline hop belongs to the normalized subgroup.
- simple_graph_is_reclusiveA simple graph G is reclusive if it admits a hop and the identity permutation on its vertex set can be written as a product of an odd…
- op_300_hypercube_two_leap_group_cardThe 2-dimensional hypercube graph Q₂ (the 4-cycle C₄) has leap group of cardinality 8.
- simple_graph_is_hop_closedAn edge subset F of a finite simple graph G is hop-closed (hop-maximal) if F is a subset of the edge set of G and for every edge e in E(G)…
- op_543_completeGraph_two_hop_word_length_le_oneFor the complete graph K₂ on 2 vertices, every element of its leap group is the product of at most 1 hop.
- simple_graph_hop_word_length_zeroThe identity permutation on the vertices of a simple graph G is the product of the empty list of hops of G.
- simple_graph_hop_word_length_oneEvery hop of a simple graph G is the product of a one-element list of hops of G.
- kayak_paddle_hop_maps_first_cycleIn KP(k, m, l) with k even, every hop maps the vertex set of the first cycle (the k-cycle) into itself.
- simple_graph_normalized_hop_group_squareThe square of a baseline hop belongs to the normalized subgroup.
- simple_graph_is_hop_mem_leap_groupEvery hop lies in the leap group.
- kayak_paddle_leap_group_ne_of_even_secondIf the second cycle of KP(k, m, l) has even length m, its leap group is neither the symmetric nor the alternating group.
- simple_graph_normalized_hop_inverse_two_wordThe inverse of a normalized allowed permutation also has a two-hop realization, although it need not itself be normalized allowed.
- simple_graph_normalized_hop_group_conjugateConjugation by the baseline preserves the normalized subgroup.
- simple_graph_completeGraph_three_hop_closed_not_intersection_closedThe collection of hop-closed edge subsets of the complete graph K₃ on 3 vertices is not closed under intersection.
- simple_graph_leap_group_normalized_cosetsEvery leap lies in the normalized subgroup or in its left coset by the baseline hop. Together with containment, this gives index at most…
- simple_graph_leap_word_bound_of_normalizedA signed normalized-word diameter bound D implies an actual hop-word diameter bound 2D+1. The normalized diameter bound remains an…
- 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_group_leFor a fixed baseline hop, its normalized subgroup is contained in the original leap group.
- op_300_hypercube_one_leap_group_cardThe hypercube graph Q₁ (the path K₂) has leap group of cardinality 2.
- kayak_paddle_leap_group_ne_of_even_firstIf the first cycle of KP(k, m, l) has even length k, its leap group is neither the symmetric nor the alternating group.
- 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…
- kayak_paddle_leap_group_not_eq_top_or_alternatingNo: KP(3, 4, 1) (a triangle and a 4-cycle joined by an edge, 7 vertices) admits a hop, but its leap group is neither S_7 nor A_7. Every…
- simple_graph_normalized_word_to_hop_wordEvery signed normalized word lifts to an actual hop word with exactly twice its length and the same product.
Lean source view module on GitHub
/-- A hop of `G`: a permutation sending every vertex to one of its neighbours. -/ def simple_graph_is_hop {V : Type*} (G : SimpleGraph V) (h : Equiv.Perm V) : Prop := ∀ v, G.Adj v (h v)