Marriage theorem

In mathematics, the marriage theorem, usually credited to mathematician Phillip Hall[?], is a combinatorial result that gives the condition allowing us to select a distinct element from each of a collection of subsets.

Let S = {S_i} be a (possibly infinite) set of finite subsets of some larger collection. A set of distinct representatives (sometimes abbreviated as an SDR) is a set X = {x_i} with the property that for all i, x_i in S_i; and x_i ≠ x_j if i ≠ j.

The marriage condition for S is that, for any subset T = {T_i} of S,

<math>|\cup T_i| \ge |T|</math>

The marriage theorem then states that, there exists a set of distinct representatives X = {x_i} if and only if S meets the marriage condition.

The standard example (somewhat dated at this point) of an application of the marriage theorem is to imagine two groups of n men and women. Each woman would happily marry some subset of the men; and any man would be happy to marry a woman who wants to marry him.

If we let M_i be the set of men that the ith woman would be happy to marry, then each woman can happily marry a man if and only if the collection of sets {M_i} meets the marriage condition.

The theorem has many other interesting "non-marital" applications. For example, take a standard deck of cards, and deal them out into 13 piles of 4 cards each. Then, using the marriage theorem, we can show that it is possible to select exactly 1 card from each pile, such that the 13 selected cards contain exactly one card of each rank (ace, 2, 3, ..., queen, king}.

More abstractly, let G be a group, and H be a finite subgroup of G. Then the marriage theorem can be used to show that there is a set X such that X is an SDR for both the set of left cosets and right cosets of H in G.

The theorem also has applications in the area of graph theory.