System of common representatives

From Encyclopedia of Mathematics
Revision as of 17:19, 7 February 2011 by (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

system of simultaneous representatives

A set of cardinality which is a system of different representatives for each of the families of subsets of a given set , each of which consists of elements. Suppose that , that is finite, let , , and let . A system of common representatives for and exists if and only if no sets of the family are contained in fewer than sets of , for each . This theorem is valid also for infinite , provided all the subsets in the families and are finite. Conditions for the existence of a system of common representatives are known for , but are more complicated to formulate.


[1] M. Hall, "Combinatorial theory" , Wiley (1986)



[a1] H.J. Ryser, "Combinatorial mathematics" , Math. Assoc. Amer. (1963)
[a2] L. Mirsky, "Transversal theory" , Acad. Press (1971)
[a3] M. Aigner, "Combinatorial theory" , Springer (1979) pp. Chapt. II (Translated from German)
How to Cite This Entry:
System of common representatives. Encyclopedia of Mathematics. URL:
This article was adapted from an original article by V.E. Tarakanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article