Namespaces
Variants
Actions

System of common representatives

From Encyclopedia of Mathematics
Jump to: navigation, search


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)

Comments

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