Rado's theorem (defect form)
ProvedRado.rado_defectcombinatoricslinear-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 .
Then there are an independent partial transversal and a subset with
Together with weak duality this says that the largest size of an independent partial transversal equals . This is Rado's theorem on independent transversals in its defect (min-max) form; for subsets of a basis it is the defect form of Hall's marriage theorem.
Formalization Note. The conclusion is existential in ; LinearIndepOn k v J is linear independence of restricted to .
Preamble
import Mathlib
Formal statement
namespace Rado
theorem rado_defect {k V ι : Type*} [Field k] [AddCommGroup V] [Module k V] [Fintype ι]
[DecidableEq ι] (A : ι → Set V) (hA : ∀ i, (A i).Finite) :
∃ (J : Finset ι) (v : ι → V) (S : Finset ι),
(∀ j ∈ J, v j ∈ A j) ∧ LinearIndepOn k v (J : Set ι) ∧
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