Namespaces
Variants
Actions

Difference between revisions of "System of common representatives"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
s0919501.png
 +
$#A+1 = 22 n = 0
 +
$#C+1 = 22 : ~/encyclopedia/old_files/data/S091/S.0901950 System of common representatives,
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
''system of simultaneous 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.
+
A set $  R $
 +
of cardinality $  m $
 +
which is a [[System of different representatives|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====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  M. Hall,  "Combinatorial theory" , Wiley  (1986)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  M. Hall,  "Combinatorial theory" , Wiley  (1986)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
 
  
 
====References====
 
====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>
 
<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>

Latest revision as of 08:24, 6 June 2020


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