Hop-Closed and Leap-Closed Edge Subsets Do Not Form the Flats of a Matroid
low tier2026-10-26OP-302reviewed by Codex中文版
Abstract
Question 5.9 of arXiv:2610.18463 asks whether the collection of hop-closed (hop-maximal) edge subsets, or the collection of leap-closed (leap-maximal) edge subsets, of a finite simple graph forms the set of flats of a matroid on its edge set. For a spanning subgraph $H = G[F]$, hop-maximality requires that the addition of any edge from $E(G) \setminus F$ strictly increases the number of hops of the subgraph, while leap-maximality requires that adding any edge from $E(G) \setminus F$ strictly enlarges its leap group $\Lambda_1(H)$. We show that the answer is negative for both notions: neither the family of hop-closed edge subsets nor the family of leap-closed edge subsets forms the set of flats of a matroid for every finite simple graph. The refutation proceeds by demonstrating that on the complete graph $K_3$ on three vertices, neither collection is closed under intersection. Specifically, there exist pairs of hop-closed (respectively, leap-closed) edge subsets whose intersection fails to be hop-closed (respectively, leap-closed). Because the collection of flats of any matroid is necessarily closed under intersection, this failure of intersection closure proves that no matroid on the edge set of $K_3$ can have either of these collections as its flats. All definitions, lemmas, and the main refutation theorem have been formalized and verified in the Lean 4 proof assistant.
1. Introduction
In arXiv:2610.18463, titled "The group generated by a graph's derangements", Question 5.9 examines the combinatorial and matroidal properties of subgraph families defined by permutation group actions associated with finite graphs. Let $G = (V, E)$ be a finite simple graph. For any subset of edges $F \subseteq E$, the spanning subgraph $G[F] = (V, F)$ has vertex set $V$ and edge set $F$. In that paper, an edge subset $F \subseteq E$ is defined to be hop-maximal (or hop-closed) in $G$ if for every edge $e \in E \setminus F$, the spanning subgraph $G[F \cup \{e\}]$ has strictly more hops than $G[F]$. Similarly, $F$ is defined to be leap-maximal (or leap-closed) in $G$ if for every edge $e \in E \setminus F$, the leap group $\Lambda_1(G[F \cup \{e\}])$ strictly contains $\Lambda_1(G[F])$. Posing Question 5.9, the paper asks:
"Do either of these notions give flats of a matroid?"
In matroid theory, given a finite ground set $E$, a collection $\mathcal{F} \subseteq \mathcal{P}(E)$ constitutes the set of flats (or closed sets) of a matroid $M = (E, \mathcal{I})$ if and only if it satisfies the classical flat axioms: the ground set $E$ is in $\mathcal{F}$, the intersection of any two members of $\mathcal{F}$ is in $\mathcal{F}$, and the collection satisfies the covering property. In particular, a flat $F \in \mathcal{F}$ has the property that for every element $e \in E \setminus F$, the rank strictly increases, $r_M(F \cup \{e\}) > r_M(F)$. The question in arXiv:2610.18463 asks whether, for every finite simple graph $G = (V, E)$, the hop-closed edge subsets (or the leap-closed edge subsets) arise as the flats of some matroid $M$ whose ground set is $E$.
Question 5.9 asks whether these graph-defined families satisfy the axioms characterizing the flats of a matroid. We use the spanning-subgraph interpretation: all vertices of the ambient graph are retained when edges are removed. In matroid theory, closure under intersection is an unconditional necessity: in any matroid $M$, if $F_1$ and $F_2$ are flats, then their intersection $F_1 \cap F_2$ is also a flat. If a proposed family of subsets fails to be closed under intersection on even a single graph $G$, it cannot form the collection of flats of any matroid on the edge set of $G$.
This post presents the formal refutation of Question 5.9 through the theorem simple_graph_hop_or_leap_maximal_not_matroid_flats, which is formalized and verified in Lean 4. The theorem proves that neither the hop-closed edge subsets nor the leap-closed edge subsets form the flats of a matroid for every finite simple graph.
The proof establishes that the complete graph $K_3$ on three vertices serves as a counterexample for both properties. Specifically:
- The lemma
simple_graph_completeGraph_three_hop_closed_not_intersection_closedproves that the collection of hop-closed edge subsets of $K_3$ is not closed under intersection. - The lemma
simple_graph_completeGraph_three_leap_closed_not_intersection_closedproves that the collection of leap-closed edge subsets of $K_3$ is not closed under intersection.
Together with the general matroid-theoretic lemma matroid_isFlat_inter, which states that the intersection of two flats is always a flat, these counterexamples rule out the existence of a matroid whose flats are the hop-closed or leap-closed edge sets of $K_3$, settling both parts of Question 5.9 in the negative.
2. Preliminaries
We work in the setting of finite simple graphs and matroids. Let $V$ be a type, and let $G$ be a simple graph on $V$, represented in Lean by a term of type $\text{SimpleGraph } V$. The edge set of $G$, denoted $G.\text{edgeSet}$, is a subset of the symmetric square $\text{Sym2 } V$, which represents the collection of unordered pairs of elements of $V$. Given an edge subset $F \subseteq E(G)$, the spanning subgraph of $G$ with edge set $F$ is denoted by $G[F] = (V, F)$, which corresponds in Lean to $\text{SimpleGraph.fromEdgeSet } F$.
A hop of a graph $H$ is a permutation $h$ of its entire vertex set such that $v$ and $h(v)$ are adjacent for every vertex $v$. Since our graphs have no loops, every hop has no fixed points. In particular, an isolated vertex rules out all hops. The leap group $\Lambda_1(H)$ is the subgroup of the permutation group generated by these hops. If there are no hops, this generated subgroup is the trivial group, which still contains the identity. The distinction between an empty set of hops and a trivial leap group is used throughout the counterexample.
Definition 1 (simple_graph_is_hop_closed). Let $V$ be a finite type, and let $G$ be a simple graph on $V$ with edge set $E(G) = G.\text{edgeSet} \subseteq \text{Sym2 } V$. A subset of edges $F \subseteq \text{Sym2 } V$ is hop-closed (or hop-maximal) in $G$, denoted by simple_graph_is_hop_closed, if $F \subseteq E(G)$ and for every edge $e \in E(G) \setminus F$, the number of hops of the spanning subgraph $G[F \cup \{e\}]$ is strictly greater than the number of hops of $G[F]$: $$F \subseteq G.\text{edgeSet} \wedge \forall e \in G.\text{edgeSet} \setminus F, \; \text{Nat.card} \{ h : \text{Equiv.Perm } V \mid \text{simple\_graph\_is\_hop } (G[F]) \; h \} < \text{Nat.card} \{ h : \text{Equiv.Perm } V \mid \text{simple\_graph\_is\_hop } (G[F \cup \{e\}]) \; h \},$$ where $G[F] = \text{SimpleGraph.fromEdgeSet } F$ and $G[F \cup \{e\}] = \text{SimpleGraph.fromEdgeSet } (\text{insert } e \; F)$.
*Remark 1.* In Definition 1, the inequality comparing the counts of hops is strict ($<$): the addition of any edge outside $F$ must strictly increase the cardinality of the subtype of permutations that are hops. The vertex type $V$ is equipped with a $\text{Fintype } V$ instance, ensuring that the group of permutations $\text{Equiv.Perm } V$ is finite and the counts are well-defined natural numbers. The vertex set $V$ is fixed throughout, while the edge set varies by adjoining a single edge $e \in G.\text{edgeSet} \setminus F$.
Definition 2 (simple_graph_is_leap_closed). Let $V$ be a type, and let $G$ be a simple graph on $V$ with edge set $E(G) = G.\text{edgeSet} \subseteq \text{Sym2 } V$. A subset of edges $F \subseteq \text{Sym2 } V$ is leap-closed (or leap-maximal) in $G$, denoted by simple_graph_is_leap_closed, if $F \subseteq E(G)$ and for every edge $e \in E(G) \setminus F$, the leap group of the spanning subgraph $G[F]$ is strictly contained in the leap group of the spanning subgraph $G[F \cup \{e\}]$: $$F \subseteq G.\text{edgeSet} \wedge \forall e \in G.\text{edgeSet} \setminus F, \; \text{simple\_graph\_leap\_group } (G[F]) < \text{simple\_graph\_leap\_group } (G[F \cup \{e\}]),$$ where $<$ denotes strict inclusion in the complete lattice of subgroups of $\text{Equiv.Perm } V$, with $G[F] = \text{SimpleGraph.fromEdgeSet } F$ and $G[F \cup \{e\}] = \text{SimpleGraph.fromEdgeSet } (\text{insert } e \; F)$.
*Remark 2.* In Definition 2, the order relation is strict inequality ($<$) in the lattice of subgroups of permutations, meaning that $\text{simple\_graph\_leap\_group } (G[F])$ is a proper subgroup of $\text{simple\_graph\_leap\_group } (G[F \cup \{e\}])$. In Lean, the definition does not require $\text{Fintype } V$ in its signature, since subgroup inclusion is defined for arbitrary types. For the application to finite graphs in Question 5.9, $V$ is a finite type.
Definition 3 (Matroid Flats and Intersection Closure). Let $\alpha$ be a finite type, and let $M$ be a matroid on ground set $M.E \subseteq \alpha$. A subset $F \subseteq \alpha$ is a flat of $M$, denoted in Lean by $M.\text{IsFlat } F$, if $F \subseteq M.E$ and the matroid closure of $F$ satisfies $\text{cl}_M(F) = F$. Equivalently, $F$ is a flat if for every element $x \in M.E \setminus F$, the rank of $F \cup \{x\}$ strictly exceeds the rank of $F$. The lemma matroid_isFlat_inter establishes that the collection of flats of any matroid is closed under binary intersection: $$\forall (F_1 \, F_2 : \text{Set } \alpha), \; M.\text{IsFlat } F_1 \to M.\text{IsFlat } F_2 \to M.\text{IsFlat } (F_1 \cap F_2).$$
*Remark 3.* In the setting of graphs, the ambient type is $\alpha = \text{Sym2 } V$, and the ground set of the matroid is fixed to the edge set of $G$, namely $M.E = G.\text{edgeSet}$. In Lean's Mathlib matroid library, $M.\text{IsFlat } F$ implies $F \subseteq M.E$, aligning with the requirement $F \subseteq G.\text{edgeSet}$ in Definitions 1 and 2. Closure under intersection is an unconditional theorem of matroid theory holding for all matroids.
3. Main result
The main result settled in Lean 4 is the refutation of Question 5.9 of arXiv:2610.18463 for both hop-closed and leap-closed edge subsets.
Theorem (simple_graph_hop_or_leap_maximal_not_matroid_flats). Neither the collection of hop-closed edge subsets nor the collection of leap-closed edge subsets forms the set of flats of a matroid for every finite simple graph $G$. Explicitly, both of the following universal statements are false:
1. It is false that for every finite type $V$ with decidable equality and every simple graph $G$ on $V$, there exists a matroid $M$ on $\text{Sym2 } V$ with ground set $M.E = G.\text{edgeSet}$ whose flats are precisely the hop-closed edge subsets of $G$: $$\neg \left( \forall \{V : \text{Type}\} \; [\text{Fintype } V] \; [\text{DecidableEq } V] \; (G : \text{SimpleGraph } V), \; \exists (M : \text{Matroid } (\text{Sym2 } V)), \; M.E = G.\text{edgeSet} \wedge \forall F, M.\text{IsFlat } F \leftrightarrow \text{simple\_graph\_is\_hop\_closed } G \; F \right).$$ 2. It is false that for every finite type $V$ with decidable equality and every simple graph $G$ on $V$, there exists a matroid $M$ on $\text{Sym2 } V$ with ground set $M.E = G.\text{edgeSet}$ whose flats are precisely the leap-closed edge subsets of $G$: $$\neg \left( \forall \{V : \text{Type}\} \; [\text{Fintype } V] \; [\text{DecidableEq } V] \; (G : \text{SimpleGraph } V), \; \exists (M : \text{Matroid } (\text{Sym2 } V)), \; M.E = G.\text{edgeSet} \wedge \forall F, M.\text{IsFlat } F \leftrightarrow \text{simple\_graph\_is\_leap\_closed } G \; F \right).$$
In the Lean statement, the theorem is structured as a conjunction of two propositions, each stating that there cannot exist a matroid $M$ on ambient type $\text{Sym2 } V$ with $M.E = G.\text{edgeSet}$ whose flats coincide with simple_graph_is_hop_closed applied to $G$ (in the first conjunct) or simple_graph_is_leap_closed applied to $G$ (in the second conjunct) across all finite vertex types $V$ with decidable equality and all simple graphs $G$ on $V$.
Each auxiliary result in the formalization contributes a necessary component to the refutation:
simple_graph_completeGraph_three_hop_closed_not_intersection_closedproves that the collection of hop-closed edge subsets of the complete graph $K_3 = (\top : \text{SimpleGraph } (\text{Fin } 3))$ on three vertices is not closed under intersection, yielding edge subsets $F_1, F_2 \subseteq E(K_3)$ that are hop-closed while their intersection $F_1 \cap F_2$ is not.simple_graph_completeGraph_three_leap_closed_not_intersection_closedproves that the collection of leap-closed edge subsets of the complete graph $K_3 = (\top : \text{SimpleGraph } (\text{Fin } 3))$ on three vertices is not closed under intersection, yielding edge subsets $F_1, F_2 \subseteq E(K_3)$ that are leap-closed while their intersection $F_1 \cap F_2$ is not.matroid_isFlat_intersupplies the matroid-theoretic property that the intersection of any two flats in a matroid is a flat, converting the failure of intersection closure on $K_3$ into the disproof of the existence of any such matroid.
theorem simple_graph_hop_or_leap_maximal_not_matroid_flats : (¬ ∀ {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V), ∃ (M : Matroid (Sym2 V)), M.E = G.edgeSet ∧ ∀ F, M.IsFlat F ↔ simple_graph_is_hop_closed G F) ∧ (¬ ∀ {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V), ∃ (M : Matroid (Sym2 V)), M.E = G.edgeSet ∧ ∀ F, M.IsFlat F ↔ simple_graph_is_leap_closed G F)
4. Proof
The counterexample is the triangle on the fixed vertex set $V=\{0,1,2\}$. Write $e_{ij}$ for the unordered edge joining $i$ to $j$. Its three edges are $e_{01},e_{02},e_{12}$. We first compute the hops of its relevant spanning subgraphs, then use the necessary intersection axiom for matroid flats. The argument needs only paths with two edges and a graph with one edge; no search over larger graphs or verification of the matroid exchange axiom is required.
Hops on a three-vertex path. Consider the path with edge set $\{e_{01},e_{12}\}$. Both vertices $0$ and $2$ have $1$ as their only neighbor. A hop would therefore satisfy $h(0)=h(2)=1$, contradicting injectivity. Thus this path has no hops. The same argument applies to each two-edge spanning subgraph of the triangle: its two leaves would both have to map to its middle vertex. A single-edge spanning subgraph also has no hops, because its third vertex is isolated. These conclusions refer to permutations of all three vertices, including the isolated vertex when it is present.
Hops on the triangle. A hop on the complete graph $K_3$ is precisely a permutation of the three vertices without a fixed point. There are exactly two such permutations, the cycles $(0\;1\;2)$ and $(0\;2\;1)$. Each sends every vertex to a different vertex, hence to a neighbor. Every other permutation has a fixed point and cannot be a hop. Consequently the hop count increases from zero to two when the missing edge of any two-edge path is inserted. Each path has just one missing edge relative to $K_3$, so this verifies every insertion required for that path to be hop-closed.
The hop-closed witnesses. The formal hop lemma uses $$F_1=\{e_{01},e_{12}\},\qquad F_2=\{e_{12},e_{02}\}.$$ Each is a path, so each is hop-closed in $K_3$ by the preceding count. Their intersection is $S=\{e_{12}\}$. Insert the missing edge $e_{01}$ into $S$. Both $G[S]$ and $G[S\cup\{e_{01}\}]$ have zero hops: the former has an isolated vertex and the latter is a path. The strict inequality required for hop-closedness would therefore be $0<0$. This is false, and $S$ is not hop-closed. One failed insertion suffices to refute a condition that demands a strict increase for every missing edge.
This is the content of simple_graph_completeGraph_three_hop_closed_not_intersection_closed. Its Lean proof names the three edges and two finite edge sets, verifies that each witness is contained in the triangle's edge set, and identifies the unique missing edge of each path. The hop counts zero and two are then checked by finite computation over permutations of Fin 3. For the intersection, the same computation gives zero before and after inserting the selected edge. The proof uses kernel-checked finite decisions for these small counts.
The leap-closed witnesses. The leap lemma uses a relabelled pair of paths, $$L_1=\{e_{01},e_{02}\},\qquad L_2=\{e_{01},e_{12}\},\qquad L_1\cap L_2=\{e_{01}\}.$$ Both paths have no hops, so their leap groups are trivial. The leap group of $K_3$ is nontrivial: the permutation $0\mapsto1\mapsto2\mapsto0$ is a hop, hence belongs to the subgroup generated by hops, and it is different from the identity. Therefore inserting the unique missing edge of either path strictly enlarges its leap group from the trivial group to a nontrivial group. This proves that $L_1$ and $L_2$ are leap-closed.
Their intersection is not leap-closed. The single-edge spanning graph with edge $e_{01}$ has an isolated vertex and hence trivial leap group. Inserting $e_{02}$ gives the path $L_1$, whose leap group is again trivial. There is no strict subgroup inclusion between these two equal groups. This violates the defining condition at that missing edge.
The Lean proof of simple_graph_completeGraph_three_leap_closed_not_intersection_closed follows this argument directly. It proves that the two paths have no hops by using injectivity of a permutation at their leaves, and that the single-edge graph has no hop by looking at its isolated vertex. It then proves that the subgroup generated by an empty set of hops is the bottom subgroup. For the complete graph it exhibits the rotation permutation as a nonidentity member of the leap group. Only nontriviality is needed here; the formal proof does not enumerate the subgroups of the symmetric group or require an exact description of the triangle's leap group.
The matroid obstruction. If $A$ and $B$ are flats of a matroid $M$, their intersection is a flat. One way to see this is to write flats as fixed points of the matroid closure operator. Monotonicity gives $$\operatorname{cl}_M(A\cap B)\subseteq\operatorname{cl}_M(A)\cap\operatorname{cl}_M(B)=A\cap B.$$ Since $A\cap B$ lies in the ground set, extensivity gives the reverse inclusion. Thus $\operatorname{cl}_M(A\cap B)=A\cap B$. The formal lemma matroid_isFlat_inter obtains this property from the library theorem for intersections of families of flats, applied to a family indexed by two elements.
Suppose now that a matroid on the triangle's edge set had exactly the hop-closed subsets as its flats. Both $F_1$ and $F_2$ would be flats, so $F_1\cap F_2$ would be a flat. By the assumed equality of families, their intersection would be hop-closed, contradicting the witness above. The argument with $L_1,L_2$ gives the same contradiction for leap-closed subsets.
Finally, a universal assertion that such a matroid exists for every finite simple graph would apply to $K_3$. The two contradictions therefore refute the two universal assertions separately. The theorem simple_graph_hop_or_leap_maximal_not_matroid_flats packages these refutations as a conjunction. Its Lean proof specializes each proposed universal assertion to the complete graph on Fin 3, transfers closedness of the two witnesses to flatness, applies matroid_isFlat_inter, and transfers flatness of the intersection back to obtain the contradiction. The ground set is the triangle's edge set; the ambient type Sym2 (Fin 3) is only the representation of unordered vertex pairs.
5. Discussion
The result answers both alternatives of Question 5.9 of arXiv:2610.18463 in the negative under the spanning-subgraph interpretation used here. The obstruction is already present on three vertices: two paths can each require every missing edge to create a hop or enlarge the leap group, while their common single edge does not have this property.
This behavior also explains why the word "closed" in the graph definitions does not by itself supply a closure operator. A condition that tests every single-edge extension need not be preserved by intersection. Here, two edges together are just short of supporting a hop, whereas a single edge is further from doing so. Both paths pass the extension test and their intersection fails it. The leap-group version has the same obstruction because all the proper spanning subgraphs used in the proof have trivial leap group.
The theorem refutes the assertion for all finite simple graphs. It does not classify which particular graphs admit a matroid with either prescribed family of flats. Nor does it claim that failure of intersection closure occurs in every graph. Any proposed restriction on the ambient graph requires a separate argument. Similarly, variants that change the vertex set when removing edges, or permit generators to fix vertices, use different definitions and are not covered by this formalization.
There is no need to test the remaining matroid flat axioms for the triangle: the failure of one necessary axiom already rules out both proposed families. In fact, the same failure rules out their being the fixed-point sets of any ordinary closure operator on the edge set, since such fixed-point sets must also be closed under intersection.
Why it is research-level
- refutes OP-302 (Matroid flats from hop-maximal and leap-maximal subgraphs)
Lean declarations
- 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.
- 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.
- matroid_isFlat_interIn any matroid M, if F₁ and F₂ are flats of M, then their intersection F₁ ∩ F₂ is also a flat of M.
- 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)…
- simple_graph_is_leap_closedAn edge subset F of a simple graph G is leap-closed (leap-maximal) if F is a subset of the edge set of G and for every edge e in E(G) \ F,…
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
References
- arXiv:2610.18463 — The group generated by a graph's derangements
Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Codex. Only the Lean is verified; the prose is a reading of it.