View source for System of different representatives

''system of distinct representatives, for a given family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s0919601.png" /> of subsets of a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s0919602.png" />''

A set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s0919603.png" /> determined by a one-to-one mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s0919604.png" /> that has the property: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s0919605.png" /> for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s0919606.png" /> (here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s0919607.png" /> is an arbitrary index set). Another name for a system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s0919608.png" /> of distinct representatives is transversal for the family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s0919609.png" />. One also considers partial transversals of a family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196010.png" />, namely sets of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196011.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196012.png" /> is a subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196013.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196014.png" /> is a one-to-one mapping.

Systems of distinct representatives are used both in purely combinatorial mathematical studies and in applications to linear programming, mathematical economics and cybernetics. In the framework of combinatorial mathematics, systems of distinct representatives play an important role in questions of choice and in extremal problems. They are used, in particular, in the study of Latin squares, in the assignment problem, in various extremal problems, in min-max theorems, and in the study of matrices with non-negative entries and with row and column sums in given ranges.

A criterion for the existence of a system of distinct representatives for a finite set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196015.png" /> is given by Phillip Hall's theorem: On a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196016.png" />, let a family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196017.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196018.png" /> elements, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196019.png" /> finite, be given; a system of distinct representatives exists if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196020.png" /> for every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196021.png" />-subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196022.png" /> and for every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196023.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196024.png" />. Hall's theorem is equivalent to König's theorem (see [[Selection theorems|Selection theorems]]) about matrices of zeros and ones. This fundamental criterion can also be applied to infinite sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196025.png" /> when all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196026.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196027.png" />, are finite. Roughly speaking, as is shown by examples, such cases exhaust the domain of applicability of Hall's criterion, but it serves as a starting point for various criteria in several other cases (see [[#References|[3]]]). For example: a) when there is a subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196028.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196029.png" /> is finite and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196030.png" /> are finite for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196031.png" />; or b) when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196032.png" /> is a countable set.

In view of the wide use of systems of distinct representatives, algorithms for their practical determination (see [[#References|[1]]]) are of interest.

One of the main problems on systems of distinct representatives is the problem of the number of such systems for finite families of finite sets; this is connected with the calculation of the [[Permanent|permanent]] of a matrix of zeros and ones. There are lower bounds for the number of such systems. Let the family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196033.png" /> consist of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196034.png" /> subsets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196035.png" /> and let these be ordered by cardinality: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196036.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196037.png" /> satisfies Hall's criterion, then the number of systems of distinct representatives is at least

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196038.png" /></td> </tr></table>

Questions on systems of representatives are dealt with also in the theory of matroids (cf. [[Matroid|Matroid]], also called independence spaces or combinatorial geometries, cf. [[Combinatorial geometry|Combinatorial geometry]]). The connection between the theory of representatives and matroids is given by the Edmonds–Fulkerson theorem: For a given family of subsets of a finite set, the totality of all partial transversals is the totality of independent subsets of some matroid. The matroid so obtained from the family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196039.png" /> is called the transversal matroid for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196040.png" />. Many matroids can be represented as transversal matroids for some family of sets.

The concept of a system of distinct representatives can be generalized in various directions, for example: a) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196042.png" />-transversals for a given family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196043.png" /> and an integral vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196044.png" /> are sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196045.png" />, where the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196046.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196047.png" />, are pairwise disjoint subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196048.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196049.png" />; b) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196051.png" />-transversals for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196052.png" /> and an integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196053.png" /> are subsets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196054.png" /> for mappings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196055.png" /> with the properties <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196056.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196057.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091960/s09196058.png" />.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  M. Hall,   "Combinatorial theory" , Wiley  (1986)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  L. Mirsky,   "Transversal theory" , Acad. Press  (1971)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  V.E. Tarakanov,   "On systems of representatives" , ''Problems of Cybernetics'' , '''16''' , Moscow  (1975)  pp. 110–124  (In Russian)</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">  D.J.A. Welsh,   "Matroid theory" , Acad. Press  (1976)</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>