§1.6, proof of THEOREM 1, p. 71 — one-element augmentation: make room for x in a family of k disjoint independent sets
ProvedEdmondsPartition.Main.augment_oneThroughout, is a finite matroid: a finite set of elements (the type , with the whole set) 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). For , 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 . Assume that every span satisfies . Let be mutually disjoint independent sets (any of them may be empty) and let be an element in none of them. Then there are mutually disjoint independent sets with
This is the heart of the proof of THEOREM 1: elements are rearranged among the sets so that fits into one of them while independence and disjointness are preserved, and no previously covered element is lost. Repeating it covers all of .
Formalization Note Lean also assumes that the empty set is independent (). The paper's rank, "the number of elements in each maximal independent set contained in ", presupposes that every set has an independent subset; with an empty family Axioms 1 and 2 hold vacuously and the statement fails. The conclusion is an equality of unions, so the new family covers exactly the old elements together with .
import Mathlib import Definitions.Def_WhitneyMatroid_RankIndep_Postulates import Definitions.Def_EdmondsPartition_Main_Basic
namespace EdmondsPartition.Main
open WhitneyMatroid.RankIndep
theorem augment_one {α : Type*} [Fintype α] [DecidableEq α] (Indep : Finset α → Prop)
(h1 : IndepI1 Indep) (h2 : Axiom2 Indep) (h0 : Indep ∅) (k : ℕ)
(hspan : ∀ S : Finset α, IsSpan Indep S → (S.card : ℤ) ≤ (k : ℤ) * rankOfIndep Indep S)
(I : Fin k → Finset α) (hI : ∀ i, Indep (I i))
(hdisj : (Set.univ : Set (Fin k)).PairwiseDisjoint I) (x : α) (hx : ∀ i, x ∉ I i) :
∃ I' : Fin k → Finset α, (∀ i, Indep (I' i)) ∧ (Set.univ : Set (Fin k)).PairwiseDisjoint I' ∧
Finset.univ.biUnion I' = insert x (Finset.univ.biUnion I) := by sorry
end EdmondsPartition.Main
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.