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 xi ≠ xj if i ≠ j.
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.
Referenced By
List of combinatorics topics | List of mathematical topics (M-O)
|
