# System of common representatives

system of simultaneous representatives

A set $R$ of cardinality $m$ which is a system of different representatives for each of the $t$ families of subsets ${\mathcal F} _ {1} \dots {\mathcal F} _ {t}$ of a given set $S$, each of which consists of $m$ elements. Suppose that $t = 2$, that $m$ is finite, let ${\mathcal F} _ {1} = \{ F _ {1} ^ { \prime } \dots F _ {m} ^ { \prime } \}$, ${\mathcal F} _ {2} = \{ F _ {1} ^ { \prime\prime } \dots F _ {m} ^ { \prime\prime } \}$, and let $S = \cup _ {i = 1 } ^ {m} F _ {i} ^ { \prime } = \cup _ {i = 1 } ^ {m} F _ {i} ^ { \prime\prime }$. A system of common representatives for ${\mathcal F} _ {1}$ and ${\mathcal F} _ {2}$ exists if and only if no $k$ sets of the family ${\mathcal F} _ {1}$ are contained in fewer than $k$ sets of ${\mathcal F} _ {2}$, for each $k = 1 \dots m$. This theorem is valid also for infinite $m$, provided all the subsets in the families ${\mathcal F} _ {1}$ and ${\mathcal F} _ {2}$ are finite. Conditions for the existence of a system of common representatives are known for $t > 2$, but are more complicated to formulate.

#### References

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

#### References

 [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: http://encyclopediaofmath.org/index.php?title=System_of_common_representatives&oldid=48942
This article was adapted from an original article by V.E. Tarakanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article