|
|
|
|
|
Marriage TheoremIn 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, -
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 -
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
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|