ENCYCLOPEDIA 4U .com

 Web Encyclopedia4u.com

# 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 = {Si} 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 = {xi} with the property that for all i, xi in Si; and xixj if ij.

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

The marriage theorem then states that, there exists a set of distinct representatives X = {xi} 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 Mi 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 {Mi} 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.

Content on this web site is provided for informational purposes only. We accept no responsibility for any loss, injury or inconvenience sustained by any person resulting from information published on this site. We encourage you to verify any critical information with the relevant authorities.