Marriage theorem
|
|
In mathematics, the marriage theorem, usually credited to mathematician Philip Hall, is a combinatorial result that gives the condition allowing the selection of 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 is in Si, and xi ≠ xj if i ≠ j.
The marriage condition for S is that, for any subset T = {Ti} of S,
- <math>|\bigcup T_i| \ge |T|<math>
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.
Graph theory
The marriage theorem has applications in the area of graph theory. Formulated in graph theoretic terms the problem can be stated as:
Given a bipartite graph G:=(S + T, E) with two equally sized partitions S and T does there exist a perfect matching ?
The marriage theorem provides the answer:
A perfect matching exists if and only if for every subset X of S
- <math>\|X\| \leq \|N_G(X)\|<math>
with NG(X) the neighborhood of X. In other words every subset X has enough adjacent vertices in T.
A generalization to arbitrary graphs is provided by Tutte theorem.
External links
- Marriage Theorem (http://www.cut-the-knot.org/arithmetic/elegant.shtml)
- Marriage Theorem and Algorithm (http://www.cut-the-knot.org/arithmetic/marriage.shtml)