§1.6, proof of THEOREM 1, p. 71 — counting step: some member I of F has |I ∩ S| < r(S)
ProvedEdmondsPartition.Main.exists_member_inter_lt_rankmatroidmatroid-partitionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1rank
Let be a finite set with an independence family and rank , the largest cardinality of an independent subset of . Let be mutually disjoint subsets of and let be an element in none of them. If contains and , then there is an index with
In the main proof this is applied to the nested spans : if every had elements in , their disjoint union together with would give more than elements in .
Formalization Note The argument is pure counting, so no matroid axiom and no independence of the is assumed; this makes the statement stronger than the page's setting, where the are the independent members of the family .
Preamble
import Mathlib import Definitions.Def_WhitneyMatroid_RankIndep_Postulates import Definitions.Def_EdmondsPartition_Main_Basic
Formal statement
namespace EdmondsPartition.Main
open WhitneyMatroid.RankIndep
theorem exists_member_inter_lt_rank {α : Type*} [Fintype α] [DecidableEq α]
(Indep : Finset α → Prop) (k : ℕ) (I : Fin k → Finset α)
(hdisj : (Set.univ : Set (Fin k)).PairwiseDisjoint I) (x : α) (hx : ∀ i, x ∉ I i)
(S : Finset α) (hxS : x ∈ S) (hS : (S.card : ℤ) ≤ (k : ℤ) * rankOfIndep Indep S) :
∃ i : Fin k, ((I i ∩ S).card : ℤ) < rankOfIndep Indep S := by sorry
end EdmondsPartition.Main
Source
Edmonds, Minimum partition of a matroid into independent subsets, J. Res. NBS 69B (1965), p. 71, §1.6, proof of THEOREM 1 ("Similarly, x ∈ S₁ = S(I₁) implies …")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.