# Selection theorems

A group of theorems in combinatorial theory related to the selection of elements from a set which in some way correspond to a family of subsets of that set. Selection theorems are commonly employed as existence theorems in solving various combinatorial problems. Below some of the most important selection theorems are listed, and examples of their application are given.

1) Let $S = \{ S _ {1} \dots S _ {n} \}$ be some family of subsets of a given set $T = \{ t _ {1} \dots t _ {m} \}$. A sample $R = \{ t _ {i _ {1} } \dots t _ {i _ {n} } \}$ of distinct elements of the set $T$ is called a system of distinct representatives (cf. System of different representatives) of the family $S$ if $t _ {i _ {j} } \in S _ {j}$, $j = 1 \dots n$; the element $t _ {i _ {j} }$ is a representative of the set $S _ {j}$. For example, if $T = \{ 1, 2, 3, 4, 5 \}$ and $S$ consists of $S _ {1} = \{ 2, 4, 5 \}$, $S _ {2} = \{ 2, 5 \}$, $S _ {3} = \{ 3, 4 \}$, $S _ {4} = \{ 1, 3, 4 \}$, then $R = \{ 5, 2, 3, 4 \}$ is a system of distinct representatives of $S$, where the element 5 represents the set $S _ {1}$, the element 2 represents set $S _ {2}$, etc. If, on the other hand, $S$ is composed of sets $S _ {1} = \{ 2, 4, 5 \}$, $S _ {2} = \{ 2, 5 \}$, $S _ {3} = \{ 4, 5 \}$, $S _ {4} = \{ 2, 4 \}$, $S$ will have no system of distinct representatives, since $S _ {1} , S _ {2} , S _ {3} , S _ {4}$ together contain only three elements.

The theorem on a system of distinct representatives: A family $S = \{ S _ {1} \dots S _ {n} \}$ has a system of distinct representatives if and only if the union of any $k$ sets of $S$ contains at least $k$ distinct elements, where $k = 1 \dots n$.

This theorem was proved by Ph. Hall  (see also , ). It may be used to prove the theorem on common representatives, which is also a selection theorem. Let

$$\tag{1 } T = A _ {1} \cup \dots \cup A _ {l} ,$$

$$\tag{2 } T = B _ {1} \cup \dots \cup B _ {l}$$

be two partitions of the set $T$, i.e. none of the components is empty and $A _ {i} \cap A _ {j} = B _ {i} \cap B _ {j} = \emptyset$ if $i \neq j$. The set $R = \{ t _ {i _ {1} } \dots t _ {i _ {l} } \}$ is called a system of common representatives of the partitions (1) and (2) if $R$ is a system of distinct representatives both for the family $A = \{ A _ {1} \dots A _ {l} \}$ and the family $B = \{ B _ {1} \dots B _ {l} \}$. For instance, if $T = \{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \}$ and if

$$T = A _ {1} \cup A _ {2} \cup A _ {3} \cup A _ {4} ,$$

$$T = B _ {1} \cup B _ {2} \cup B _ {3} \cup B _ {4}$$

are two partitions of $T$, where $A _ {1} = \{ 0, 1, 2, 3 \}$, $A _ {2} = \{ 4, 5, 6 \}$, $A _ {3} = \{ 7 \}$, $A _ {4} = \{ 8, 9 \}$, $B _ {1} = \{ 4, 7, 8 \}$, $B _ {2} = \{ 0, 5 \}$, $B _ {3} = \{ 2, 3, 6 \}$, $B _ {4} = \{ 1, 9 \}$, then $R = \{ 0, 6, 7, 9 \}$ is a system of common representatives of the families $A = \{ A _ {1} , A _ {2} , A _ {3} , A _ {4} \}$ and $B = \{ B _ {1} , B _ {2} , B _ {3} , B _ {4} \}$ since it is a system of distinct representatives for both $A$ and $B$; here the element 0 represents the sets $A _ {1}$ and $B _ {2}$, the element 6 represents $A _ {2}$ and $B _ {3}$, the element 7 represents $A _ {3}$ and $B _ {1}$, while the element 9 represents $A _ {4}$ and $B _ {4}$.

The theorem on a system of common representatives: The partitions (1) and (2) have a system of common representatives if and only if the union of any $k$ sets of $A$ contains at most $k$ sets from the family $B$, $k = 1 \dots l$, .

2) Let there be given a rectangular matrix. The term line will denote both a row and a column of this matrix.

König's theorem: If the elements of a rectangular matrix are zeros and ones, the minimum number of lines containing all ones is equal to the maximum number of ones which may be selected so that no two of them are located on the same line.

This theorem was formulated and proved by D. König (, see also , ). It is equivalent to the Ph. Hall theorem. It is employed, for example, in order to prove that certain matrices are linear combinations of permutation matrices (a permutation matrix is a rectangular matrix $P$ of dimension $m \times n$, consisting of zeros and ones, such that $P P ^ \prime = I$, where $P ^ \prime$ is the transposed matrix of $P$ and $I$ is the identity matrix of order $m$; for example, a square permutation matrix of order $m$ consists of $m$ ones which are so disposed that no two of them lie on the same line). In other words, if a matrix $A$ of dimension $m \times n$, $m \leq n$, has been given, with non-negative real numbers as its elements and such that the sum of the elements of each row in $A$ is $m ^ \prime$ and the sum of the elements of each column is $n ^ \prime$, then

$$A = c _ {1} P _ {1} + \dots + c _ {t} P _ {t} ,$$

where each $P _ {i}$ is a permutation matrix, while the coefficients $c _ {i}$ are non-negative real numbers , . In particular, if a square matrix $A$ of order $n$, consisting of zeros and ones, is such that the sum of the elements in any column or any row is equal to a positive integer $k$, then

$$A = P _ {1} + \dots + P _ {k} ,$$

where all $P _ {i}$ are permutation matrices of order $n$.

Let $T$ be a finite set and let $P _ {r} ( T)$ be the set of all its subsets containing exactly $r$ elements. Let

$$\tag{3 } P _ {r} ( T) = A _ {1} \cup \dots \cup A _ {l}$$

be an arbitrary ordered partition of $P _ {r} ( T)$ into $l$ components $A _ {1} \dots A _ {l}$. Let $q _ {1} \dots q _ {l}$ be integers such that

$$\tag{4 } 1 \leq r \leq q _ {1} \dots q _ {l} .$$

If there exists a subset, containing $q _ {i}$ elements of the set $T$, such that all its subsets containing exactly $r$ elements are contained in $A _ {i}$, it is said to be a $( q _ {i} , A _ {i} )$- subset of the set $T$.

Ramsey's theorem: Let there be given integers $q _ {1} \dots q _ {l}$ and $r$ which satisfy condition (4). Then there exists a natural number $N ( q _ {1} \dots q _ {l} , r )$ such that for any integer $n \geq N ( q _ {1} \dots q _ {l} , r )$ the following assertion is valid: Given a set $T$ of $n$ elements and an arbitrary ordered partition (3) of the set $P _ {r} ( T)$ into $l$ components $A _ {1} \dots A _ {l}$, then $T$ will contain a $( q _ {i} , A _ {i} )$- subset for some $i = 1 \dots l$.

This theorem was proved by F. Ramsey ; see also , . An example of an application of this theorem is the following result , , : For any given integer $m \geq 3$ there exists an integer $N _ {m}$ such that out of $n \geq N _ {m}$ points in a plane no three of which lie on a straight line, there are $m$ points which form a convex $m$- gon.

How to Cite This Entry:
Selection theorems. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Selection_theorems&oldid=48647
This article was adapted from an original article by M.P. Mineev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article