Edmonds' partition theorem in counting form
ProvedEdmondsPartition.Main.partition_of_countingThroughout, 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 .
Let and let satisfy
Then there are mutually disjoint independent sets (some possibly empty) with .
This is the "if" part of Edmonds' THEOREM 1, stated for an arbitrary subset of the matroid. The proof applies Rado's theorem (rado_rank) to the -fold direct sum of the matroid on with the family , : Rado's condition for a set of elements is exactly , and an independent transversal is the same as a placement of every element of into one of the classes so that each class is independent.
Formalization Note Lean also assumes that the empty set is independent (), as in the milestone statements of this mission; the paper's rank presupposes that every set has an independent subset.
import Mathlib import Definitions.Def_WhitneyMatroid_RankIndep_Postulates import Definitions.Def_EdmondsPartition_Main_Basic
namespace EdmondsPartition.Main
open WhitneyMatroid.RankIndep
theorem partition_of_counting {α : Type*} [Fintype α] [DecidableEq α] (Indep : Finset α → Prop)
(h1 : IndepI1 Indep) (h2 : Axiom2 Indep) (h0 : Indep ∅) (k : ℕ) (U : Finset α)
(hU : ∀ J : Finset α, J ⊆ U → (J.card : ℤ) ≤ (k : ℤ) * rankOfIndep Indep J) :
∃ I : Fin k → Finset α, (∀ i, Indep (I i)) ∧
(Set.univ : Set (Fin k)).PairwiseDisjoint I ∧ Finset.univ.biUnion I = U := by sorry
end EdmondsPartition.Main