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.
Statement
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)
- Related work
- arXiv:2610.18463 Question 5.9: The group generated by a graph's derangements
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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,…
- 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_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.
Read back from the Lean
The statement asserts the conjunction of two negative claims:
1. It is not the case that for every finite type V with decidable equality and every simple graph G on V, there exists a matroid M on Sym2 V with ground set M.E = G.edgeSet such that the flats of M are precisely the hop-closed subsets F of G.
2. It is not the case that for every finite type V with decidable equality and every simple graph G on V, there exists a matroid M on Sym2 V with ground set M.E = G.edgeSet such that the flats of M are precisely the leap-closed subsets F of G.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof proceeds by contradiction for both claims using the fundamental matroid property that the intersection of any two flats is a flat (`matroid_isFlat_inter`). If hop-closed (or leap-closed) edge sets formed the flats of a matroid for every finite simple graph, then these closed sets would necessarily be closed under intersection. However, the complete graph on three vertices, K₃, admits two hop-closed (respectively, leap-closed) edge sets whose intersection fails to be hop-closed (respectively, leap-closed), providing an explicit counterexample in both cases.
The goal splits into two independent refutations: one for hop-closed sets and one for leap-closed sets.
The statement is a conjunction asserting that neither hop-closed nor leap-closed edge sets universally form the flats of a matroid. Applying `constructor` reduces the problem to disproving each claim separately.
constructorAssuming hop-closed edge sets always form the flats of a matroid, there is a counterexample matroid on K₃ alongside two hop-closed edge sets whose intersection is not hop-closed.
Suppose for contradiction that every finite graph has a matroid whose flats are its hop-closed edge sets. By `simple_graph_completeGraph_three_hop_closed_not_intersection_closed`, the complete graph K₃ contains two hop-closed edge sets F₁ and F₂ whose intersection F₁ ∩ F₂ is not hop-closed. Specializing the assumed universal property to K₃ yields a matroid M on K₃ whose flats are precisely the hop-closed edge sets.
uses
simple_graph_completeGraph_three_hop_closed_not_intersection_closed· intro h rcases simple_graph_completeGraph_three_hop_closed_not_intersection_closed with ⟨F₁, F₂, h₁, h₂, hnot⟩ rcases h (⊤ : SimpleGraph (Fin 3)) with ⟨M, _hE, hflat⟩
A contradiction is reached, showing that hop-closed edge sets do not always form the flats of a matroid.
Because F₁ and F₂ are hop-closed, they are flats of M. By `matroid_isFlat_inter`, the intersection of any two flats in a matroid is a flat, so F₁ ∩ F₂ is a flat of M. But every flat of M is hop-closed, which directly contradicts the fact that F₁ ∩ F₂ is not hop-closed.
uses
matroid_isFlat_interhave hf₁ : M.IsFlat F₁ := (hflat F₁).2 h₁ have hf₂ : M.IsFlat F₂ := (hflat F₂).2 h₂ have hfint : M.IsFlat (F₁ ∩ F₂) := matroid_isFlat_inter M hf₁ hf₂ exact hnot ((hflat (F₁ ∩ F₂)).1 hfint)
Assuming leap-closed edge sets always form the flats of a matroid, there is a counterexample matroid on K₃ alongside two leap-closed edge sets whose intersection is not leap-closed.
Suppose for contradiction that every finite graph has a matroid whose flats are its leap-closed edge sets. By `simple_graph_completeGraph_three_leap_closed_not_intersection_closed`, K₃ contains two leap-closed edge sets F₁ and F₂ whose intersection F₁ ∩ F₂ is not leap-closed. Specializing the assumed universal property to K₃ yields a matroid M on K₃ whose flats are precisely the leap-closed edge sets.
uses
simple_graph_completeGraph_three_leap_closed_not_intersection_closed· intro h rcases simple_graph_completeGraph_three_leap_closed_not_intersection_closed with ⟨F₁, F₂, h₁, h₂, hnot⟩ rcases h (⊤ : SimpleGraph (Fin 3)) with ⟨M, _hE, hflat⟩
A contradiction is reached, showing that leap-closed edge sets do not always form the flats of a matroid.
Since F₁ and F₂ are leap-closed, they are flats of M. By `matroid_isFlat_inter`, their intersection F₁ ∩ F₂ must also be a flat of M, and therefore leap-closed. This contradicts the fact that F₁ ∩ F₂ is not leap-closed.
uses
matroid_isFlat_interhave hf₁ : M.IsFlat F₁ := (hflat F₁).2 h₁ have hf₂ : M.IsFlat F₂ := (hflat F₂).2 h₂ have hfint : M.IsFlat (F₁ ∩ F₂) := matroid_isFlat_inter M hf₁ hf₂ exact hnot ((hflat (F₁ ∩ F₂)).1 hfint)
simple_graph_completeGraph_three_hop_closed_not_intersection_closed- In the complete graph on three vertices, there exist two hop-closed edge subsets whose intersection is not hop-closed.
simple_graph_completeGraph_three_leap_closed_not_intersection_closed- In the complete graph on three vertices, there exist two leap-closed edge subsets whose intersection is not leap-closed.
matroid_isFlat_inter- In any matroid, the intersection of two flats is also a flat.
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.
/-- Refutation of OP-302: neither hop-maximal nor leap-maximal edge sets generally form the flats of a 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) := by constructor · intro h rcases simple_graph_completeGraph_three_hop_closed_not_intersection_closed with ⟨F₁, F₂, h₁, h₂, hnot⟩ rcases h (⊤ : SimpleGraph (Fin 3)) with ⟨M, _hE, hflat⟩ have hf₁ : M.IsFlat F₁ := (hflat F₁).2 h₁ have hf₂ : M.IsFlat F₂ := (hflat F₂).2 h₂ have hfint : M.IsFlat (F₁ ∩ F₂) := matroid_isFlat_inter M hf₁ hf₂ exact hnot ((hflat (F₁ ∩ F₂)).1 hfint) · intro h rcases simple_graph_completeGraph_three_leap_closed_not_intersection_closed with ⟨F₁, F₂, h₁, h₂, hnot⟩ rcases h (⊤ : SimpleGraph (Fin 3)) with ⟨M, _hE, hflat⟩ have hf₁ : M.IsFlat F₁ := (hflat F₁).2 h₁ have hf₂ : M.IsFlat F₂ := (hflat F₂).2 h₂ have hfint : M.IsFlat (F₁ ∩ F₂) := matroid_isFlat_inter M hf₁ hf₂ exact hnot ((hflat (F₁ ∩ F₂)).1 hfint)