Rado's theorem: weak duality for independent partial transversals
ProvedRado.rado_defect_lecombinatoricslinear-algebramatroidtransversal-theory
Let be a field, a -vector space, a finite index set, and a family of finite subsets of . For write . A partial transversal is a choice of vectors for the indices in a subset ; it is independent if is linearly independent over . A transversal is a choice for every .
If is an independent partial transversal, then for every
This is the easy half of Rado's theorem (the matroid analogue of the trivial direction of Hall's theorem).
Formalization Note. Each is assumed finite so that the dimensions are finite; LinearIndepOn k v J is linear independence of the family restricted to , and Sᶜ is the complement of S in the finite index type.
Preamble
import Mathlib
Formal statement
namespace Rado
theorem rado_defect_le {k V ι : Type*} [Field k] [AddCommGroup V] [Module k V] [Fintype ι]
[DecidableEq ι] (A : ι → Set V) (hA : ∀ i, (A i).Finite)
(J : Finset ι) (v : ι → V) (hv : ∀ j ∈ J, v j ∈ A j) (hind : LinearIndepOn k v (J : Set ι))
(S : Finset ι) :
J.card ≤ Sᶜ.card + Module.finrank k (Submodule.span k (⋃ i ∈ S, A i)) := by sorry
end Rado
Source
R. Rado, A theorem on independence relations, Quart. J. Math. Oxford 13 (1942), 83-89