View source for System of common representatives

''system of simultaneous representatives''

A set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091950/s0919501.png" /> of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091950/s0919502.png" /> which is a [[System of different representatives|system of different representatives]] for each of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091950/s0919503.png" /> families of subsets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091950/s0919504.png" /> of a given set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091950/s0919505.png" />, each of which consists of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091950/s0919506.png" /> elements. Suppose that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091950/s0919507.png" />, that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091950/s0919508.png" /> is finite, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091950/s0919509.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091950/s09195010.png" />, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091950/s09195011.png" />. A system of common representatives for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091950/s09195012.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091950/s09195013.png" /> exists if and only if no <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091950/s09195014.png" /> sets of the family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091950/s09195015.png" /> are contained in fewer than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091950/s09195016.png" /> sets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091950/s09195017.png" />, for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091950/s09195018.png" />. This theorem is valid also for infinite <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091950/s09195019.png" />, provided all the subsets in the families <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091950/s09195020.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091950/s09195021.png" /> are finite. Conditions for the existence of a system of common representatives are known for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091950/s09195022.png" />, but are more complicated to formulate.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  M. Hall,   "Combinatorial theory" , Wiley  (1986)</TD></TR></table>



====Comments====


====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  H.J. Ryser,   "Combinatorial mathematics" , Math. Assoc. Amer.  (1963)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  L. Mirsky,   "Transversal theory" , Acad. Press  (1971)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  M. Aigner,   "Combinatorial theory" , Springer  (1979)  pp. Chapt. II  (Translated from German)</TD></TR></table>