bibkey: rado1942independence
authors: Richard Rado
year: 1942
title: A theorem on independence relations
doi: 10.1093/qmath/os-13.1.83
url: https://doi.org/10.1093/qmath/os-13.1.83
claim: Independent representatives exist when every subfamily has rank at least its cardinality.
strata_touched:
  - D5/S3/Combinatorics/Matroids/LinearRado
license: citation-only
triage: anchor

Rado, independent representatives

Verified locator

DOI: 10.1093/qmath/os-13.1.83

Source: https://doi.org/10.1093/qmath/os-13.1.83

Rado’s independent representative theorem specializes to vector subspaces: representatives can be chosen linearly independently exactly when the span of every subfamily has dimension at least its cardinality. The spanning version follows by adjoining a common auxiliary vector space of the required deficit dimension, choosing independent representatives, and projecting back.

This is the classical linear representative theorem. It is distinct from the q-analogue of Rado’s theorem posed as Conjecture 1 in Saaltink’s paper.