System of different representatives

system of distinct representatives, for a given family $ {\mathcal F} = \{ F _ {i} : i \in I \} $ of subsets of a set $ S $

A set $ R = \{ \pi ( i) : i \in I \} $ determined by a one-to-one mapping $ \pi : I \rightarrow S $ that has the property: $ \pi ( i) \in F _ {i} $ for any $ i \in I $( here $ I $ is an arbitrary index set). Another name for a system $ R $ of distinct representatives is transversal for the family $ {\mathcal F} $. One also considers partial transversals of a family $ {\mathcal F} $, namely sets of the form $ \{ \pi ( i) : i \in I _ {0} \} $, where $ I _ {0} $ is a subset of $ I $ and $ \pi : I _ {0} \rightarrow S $ 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 $ I $ is given by Phillip Hall's theorem: On a set $ S $, let a family $ {\mathcal F} = \{ F _ {i} : i \in I \} $ of $ | I | = n $ elements, $ n $ finite, be given; a system of distinct representatives exists if and only if $ | F _ {i _ {1} } \cup \dots \cup F _ {i _ {k} } | \geq k $ for every $ k $- subset $ \{ i _ {1} \dots i _ {k} \} \subseteq I $ and for every $ k $, $ k = 1 \dots n $. Hall's theorem is equivalent to König's theorem (see Selection theorems) about matrices of zeros and ones. This fundamental criterion can also be applied to infinite sets $ I $ when all $ F _ {i} $, $ i \in I $, 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 [3]). For example: a) when there is a subset $ I _ {0} \subset I $ for which $ I - I _ {0} $ is finite and the $ F _ {i} $ are finite for all $ i \in I _ {0} $; or b) when $ I $ is a countable set.

In view of the wide use of systems of distinct representatives, algorithms for their practical determination (see [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 of a matrix of zeros and ones. There are lower bounds for the number of such systems. Let the family $ {\mathcal F} $ consist of $ n $ subsets $ F _ {1} \dots F _ {n} $ and let these be ordered by cardinality: $ m = | F _ {1} | \leq \dots \leq | F _ {n} | $. If $ s( F) $ satisfies Hall's criterion, then the number of systems of distinct representatives is at least

$$ \prod _ {k = 1 } ^ { \min ( m, n) } (| F _ {k} | - k + 1). $$

Questions on systems of representatives are dealt with also in the theory of matroids (cf. Matroid, also called independence spaces or combinatorial geometries, cf. 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 $ {\mathcal F} $ is called the transversal matroid for $ {\mathcal F} $. 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) $ \rho $- transversals for a given family $ {\mathcal F} = \{ F _ {1} \dots F _ {n} \} $ and an integral vector $ \rho = ( \rho _ {1} \dots \rho _ {n} ) $ are sets $ \{ \pi ( 1) \dots \pi ( n) \} $, where the $ \pi ( i) \subseteq F _ {i} $, $ i = 1 \dots n $, are pairwise disjoint subsets of $ S $ such that $ 1 \leq | \pi ( i) | \leq \rho _ {i} $; b) $ k $- transversals for $ {\mathcal F} = \{ F _ {i} : i \in I \} $ and an integer $ k \geq 1 $ are subsets $ R = \{ \pi ( i) : i \in I \} $ for mappings $ \pi : I \rightarrow S $ with the properties $ \pi ( i) \in F _ {i} $ and $ 1 \leq | \{ \pi ^ {-} 1 ( \pi ( i)) \} | \leq k $, $ i \in I $.

References

[1]	M. Hall, "Combinatorial theory" , Wiley (1986)
[2]	L. Mirsky, "Transversal theory" , Acad. Press (1971)
[3]	V.E. Tarakanov, "On systems of representatives" , Problems of Cybernetics , 16 , Moscow (1975) pp. 110–124 (In Russian)

References

[a1]	H.J. Ryser, "Combinatorial mathematics" , Math. Assoc. Amer. (1963)
[a2]	D.J.A. Welsh, "Matroid theory" , Acad. Press (1976)
[a3]	M. Aigner, "Combinatorial theory" , Springer (1979) pp. Chapt. II (Translated from German)