Theorem 34 — the cycles are the 2^q sums (mod 2) of a strict fundamental set
ProvedWhitneyMatroid.Binary.cycles_eq_sums_of_strictFundamentalSetbinary-matroidscombinatoricsmatroidsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a matroid on the elements , , satisfying Postulate (C*), and let be a strict fundamental set of circuits in with respect to . Then the cycles of are exactly the sums (mod 2) of subfamilies of ,
and there are exactly cycles in .
So the cycles of a (C*)-matroid form a vector space over the integers mod 2 of dimension with the fundamental circuits as a basis; this is the counting step behind Theorems 35 and 37.
Formalization Note Elements are Fin (r + q), ground set all of it; subfamilies are indexed by Finset (Fin q) (with P i Whitney's ), and the number of cycles is the Set.ncard of the set of cycles.
Preamble
import Mathlib import Definitions.Def_WhitneyMatroid_Binary_Cycles import Definitions.Def_WhitneyMatroid_Binary_IsStrictFundamentalSet
Formal statement
namespace WhitneyMatroid.Binary
/-- Theorem 34 (Appendix, p. 531). Let `M` be a matroid on `e₁, …, eₙ` (`Fin (r + q)`)
satisfying (C*), and let `P₁, …, P_q` be a strict fundamental set of circuits in `M` with respect
to `e_{n-q+1}, …, eₙ`. Then the cycles in `M` are exactly the sums (mod 2) of subfamilies of
`P₁, …, P_q`, and there are exactly `2^q` of them. -/
theorem cycles_eq_sums_of_strictFundamentalSet {r q : ℕ} (M : Matroid (Fin (r + q)))
(hE : M.E = Set.univ) (hC : SatisfiesCStar {C | M.IsCircuit C})
(P : Fin q → Set (Fin (r + q))) (hP : IsStrictFundamentalSet M P) :
{Q | IsCycleOf {C | M.IsCircuit C} Q} = Set.range (fun s : Finset (Fin q) => sumMod2 s P) ∧
{Q | IsCycleOf {C | M.IsCircuit C} Q}.ncard = 2 ^ q := by sorry
end WhitneyMatroid.Binary
Source
Whitney, On the Abstract Properties of Linear Dependence, Amer. J. Math. 57 (1935), p. 531, Theorem 34
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.