simple_graph_is_hop_closed
An 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) \ F, the spanning subgraph with edges F ∪ {e} has strictly more hops than the spanning subgraph with edges F.
Statement
def simple_graph_is_hop_closed {V : Type*} [Fintype V] (G : SimpleGraph V) (F : Set (Sym2 V)) : Prop
- Defined in
- arXiv:2610.18463 Question 5.9: The group generated by a graph's derangements
- Verified
- 25 Oct 2026
- Axioms
- none listed
- Built on 1
- 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 2
- simple_graph_hop_or_leap_maximal_not_matroid_flatsNeither the collection of hop-closed edge subsets nor the collection of leap-closed edge subsets forms the set of flats of a matroid for…
- 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.
Read back from the Lean
For a finite type V, a simple graph G on V, and a set of unordered pairs F : Set (Sym2 V), simple_graph_is_hop_closed G F asserts that:
1. F is a subset of the edge set of G (F ⊆ G.edgeSet), and
2. For every edge e in G.edgeSet \ F, the number of permutations h : Equiv.Perm V that are "hops" in SimpleGraph.fromEdgeSet F (meaning every vertex v is adjacent to h(v) in the graph whose edges are F) is strictly less than the number of permutations h : Equiv.Perm V that are "hops" in SimpleGraph.fromEdgeSet (insert e F).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- An edge subset of a finite simple graph is hop-closed (hop-maximal) if adding any edge strictly increases its number of hops. -/ def simple_graph_is_hop_closed {V : Type*} [Fintype V] (G : SimpleGraph V) (F : Set (Sym2 V)) : Prop := F ⊆ G.edgeSet ∧ ∀ e ∈ G.edgeSet \ F, Nat.card {h : Equiv.Perm V // simple_graph_is_hop (SimpleGraph.fromEdgeSet F) h} < Nat.card {h : Equiv.Perm V // simple_graph_is_hop (SimpleGraph.fromEdgeSet (insert e F)) h}