Spans: closure membership, span property and rank of S(J)
ProvedEdmondsPartition.Main.span_factsThroughout, is a finite matroid: a finite set of elements (the type ) together with a family of independent subsets satisfying Axiom 1 (every subset of an independent set is independent) and Axiom 2 (for every subset , all maximal independent subsets of have the same number of elements). The rank is the largest cardinality of an independent subset of . A span is a set such that no circuit (minimal dependent set) has exactly one element outside , and is the minimal span containing (the intersection of all spans containing ).
For every :
- an element lies in if and only if ;
- is itself a span;
- .
So the minimal span of is its rank closure. The proof shows that the rank closure is a span (a circuit with exactly one element outside the closure would force into the closure, by submodularity of the rank) and that it lies in every span containing (an element of the closure outside a span lies on a circuit meeting the complement of in one element).
Formalization Note Lean also assumes that the empty set is independent (). Part 1 is stated as an equivalence over all , including , for which both sides hold.
import Mathlib import Definitions.Def_WhitneyMatroid_RankIndep_Postulates import Definitions.Def_EdmondsPartition_Main_Basic
namespace EdmondsPartition.Main
open WhitneyMatroid.RankIndep
theorem span_facts {α : Type*} [Fintype α] [DecidableEq α] (Indep : Finset α → Prop)
(h1 : IndepI1 Indep) (h2 : Axiom2 Indep) (h0 : Indep ∅) (J : Finset α) :
(∀ e : α, e ∈ spanOf Indep J ↔ rankOfIndep Indep (insert e J) = rankOfIndep Indep J) ∧
IsSpan Indep (spanOf Indep J) ∧
rankOfIndep Indep (spanOf Indep J) = rankOfIndep Indep J := by sorry
end EdmondsPartition.Main