AFTD Auto-Formalizing Theoretical Domains

simple_graph_hop_or_leap_maximal_not_matroid_flats

theoremverifiedoriginal

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

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.

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

    line 7

      constructor
  2. Assuming 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.

    lines 8–11

    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⟩
  3. 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.

    lines 12–15

    uses matroid_isFlat_inter

        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)
  4. 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.

    lines 16–19

    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⟩
  5. 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.

    lines 20–23

    uses matroid_isFlat_inter

        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)
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

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