THEOREM 1, "only if", §1.3, p. 69 — for any independence system, a partition into k independent sets forces |A| ≤ k·r(A)
ProvedEdmondsPartition.Main.only_if_partLet be a finite set with a family of independent subsets satisfying Axiom 1 only (every subset of an independent set is independent), an independence system, and let be the largest cardinality of an independent subset of . If is partitioned into independent sets , then for every ,
This is the easy half of THEOREM 1, and it holds without Axiom 2.
Formalization Note Only Axiom 1 is assumed; Axiom 2 and the non-emptiness of the family are dropped, which makes the statement stronger than the matroid case. The hypothesis is the partition of THEOREM 1 (disjoint parts covering , empty parts allowed); disjointness is not needed for the inequality but is kept so that the statement composes with the goal.
import Mathlib import Definitions.Def_WhitneyMatroid_RankIndep_Postulates import Definitions.Def_EdmondsPartition_Main_Basic
namespace EdmondsPartition.Main
open WhitneyMatroid.RankIndep
theorem only_if_part {α : Type*} [Fintype α] [DecidableEq α] (Indep : Finset α → Prop)
(h1 : IndepI1 Indep) :
∀ (k : ℕ) (I : Fin k → Finset α), IsPartitionInto Indep k I →
∀ A : Finset α, (A.card : ℤ) ≤ (k : ℤ) * rankOfIndep Indep A := by sorry
end EdmondsPartition.Main
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.