Theorem 36 — any admissible P₁, …, P_q is the strict fundamental set of a unique (C*)-matroid
ProvedWhitneyMatroid.Binary.exists_unique_matroid_of_strictFundamentalSetbinary-matroidscombinatoricsmatroidsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a set of elements, , and let be any subsets such that contains and possibly elements from alone:
Then there is a unique matroid on satisfying Postulate (C*) with as a strict fundamental set of circuits (with respect to ).
In Whitney's words, this furnishes a simple method of constructing all matroids satisfying (C*): each is obtained from a free choice of subsets of .
Formalization Note Elements are Fin (r + q) (); is Fin.natAdd r (i-1) and is the range of Fin.castAdd q. Uniqueness is among matroids whose ground set is all of Fin (r + q).
Preamble
import Mathlib import Definitions.Def_WhitneyMatroid_Binary_Cycles import Definitions.Def_WhitneyMatroid_Binary_IsStrictFundamentalSet
Formal statement
namespace WhitneyMatroid.Binary
/-- Theorem 36 (Appendix, p. 531). Let `e₁, …, eₙ` (`Fin (r + q)`) be a set of elements, and let
`P₁, …, P_q` be any subsets such that `Pᵢ` contains `e_{n-q+i}` and possibly elements from
`e₁, …, e_{n-q}` alone. Then there is a unique matroid `M` on `e₁, …, eₙ` satisfying (C*), with
`P₁, …, P_q` as a strict fundamental set of circuits (with respect to `e_{n-q+1}, …, eₙ`). -/
theorem exists_unique_matroid_of_strictFundamentalSet {r q : ℕ}
(P : Fin q → Set (Fin (r + q)))
(hmem : ∀ i, Fin.natAdd r i ∈ P i)
(hsub : ∀ i, P i ⊆ insert (Fin.natAdd r i) (Set.range (Fin.castAdd q : Fin r → Fin (r + q)))) :
∃! M : Matroid (Fin (r + q)),
M.E = Set.univ ∧ SatisfiesCStar {C | M.IsCircuit C} ∧ IsStrictFundamentalSet M P := by sorry
end WhitneyMatroid.Binary
Source
Whitney, On the Abstract Properties of Linear Dependence, Amer. J. Math. 57 (1935), p. 531, Theorem 36
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.