PROPOSITION 3 (Lehman), p. 70 — strong circuit elimination: a ∈ C ⊆ C₁ ∪ C₂ − e
ProvedEdmondsPartition.Main.proposition_3circuitcircuit-eliminationmatroidp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a family of subsets ("circuits") of a finite set satisfying Axiom 1c (no circuit contains a different circuit) and Axiom 2c (if distinct circuits both contain , then contains a circuit). If are circuits with an element and an element , then there is a circuit with
This strengthening of Axiom 2c, due to Lehman, controls which element the eliminated circuit keeps; it is used in the proof of PROPOSITION 4.
Formalization Note The page states the result for the circuits of a matroid, but its proof assumes only Axioms 1c and 2c, so it is stated for any circuit family satisfying them; the matroid form follows by PROPOSITION 2. Edmonds writes for inclusion, rendered here as .
Preamble
import Mathlib import Definitions.Def_WhitneyMatroid_RankIndep_Postulates import Definitions.Def_EdmondsPartition_Main_Basic
Formal statement
namespace EdmondsPartition.Main
open WhitneyMatroid.RankIndep
theorem proposition_3 {α : Type*} [Fintype α] [DecidableEq α]
(Circ : Finset α → Prop) (h1c : Axiom1c Circ) (h2c : Axiom2c Circ) :
∀ (C₁ C₂ : Finset α) (e a : α), Circ C₁ → Circ C₂ → e ∈ C₁ → e ∈ C₂ → a ∈ C₁ → a ∉ C₂ →
∃ C : Finset α, Circ C ∧ a ∈ C ∧ C ⊆ (C₁ ∪ C₂).erase e := by sorry
end EdmondsPartition.Main
Source
Edmonds, Minimum partition of a matroid into independent subsets, J. Res. NBS 69B (1965), p. 70, PROPOSITION 3 (Lehman)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.