Rado's theorem (Hall form): independent transversals
ProvedRado.rado_hallcombinatoricslinear-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
then there is a transversal , , that is linearly independent. The condition is also necessary (weak duality with ). For in a standard basis this is Hall's marriage theorem.
Formalization Note. Only the sufficiency direction is stated; necessity is Rado.rado_defect_le with J = univ.
Preamble
import Mathlib
Formal statement
namespace Rado
theorem rado_hall {k V ι : Type*} [Field k] [AddCommGroup V] [Module k V] [Fintype ι]
[DecidableEq ι] (A : ι → Set V) (hA : ∀ i, (A i).Finite)
(h : ∀ S : Finset ι, S.card ≤ Module.finrank k (Submodule.span k (⋃ i ∈ S, A i))) :
∃ v : ι → V, (∀ i, v i ∈ A i) ∧ LinearIndependent k v := by sorry
end Rado
Source
R. Rado, A theorem on independence relations, Quart. J. Math. Oxford 13 (1942), 83-89