In mathematics, the marriage theorem (1935), 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.
Formally, let "S" = {"S""1", "S""2", ... } be a (not necessarily countable) collection of finite subsets of some larger set "M". A "transversal" for "S", also known as a "system of distinct representatives" for "S", or as used here, an "SDR", is a set "X" = {"x""1", "x""2", ...} of distinct elements of "M" (where |"X"| = |"S"|) and with the property that for all "i", "x""i" is in "S""i".
The marriage condition for "S" is that, for any subcollection "T" = {"T""i" } of "S",
:(i.e. the set created by the union of some n elements, which are themselves subsets of "M", in "S" must itself have cardinality of at least n)
The marriage theorem (more well known as Hall's Theorem) then states that there exists a system of distinct representatives "X" = {"x""i"} if and only if "S" meets the marriage condition.
Example: "S""1" = {1, 2, 3}"S""2" = {1, 4, 5}"S""3" = {3, 5}
For this set "S" = {"S""1", "S""2", "S""3"}, a valid SDR would be {1, 4, 5}. (Note this is not unique: {2, 1, 3} works equally well)
The standard example 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. Consider whether it is possible to pair up (in marriage) the men and women so that every person is happy.
If we let "M""i" be the set of men that the "i"-th woman would be happy to marry, then the marriage theorem states that each woman can happily marry a man if and only if the collection of sets {"M""i"} meets the marriage condition.
Note that the marriage condition is that, for any subset of the women, the number of men whom at least one of the women would be happy to marry, , be at least as big as the number of women in that subset, . It is obvious that this condition is "necessary", as if it does not hold, there are not enough men to share among the women. What is interesting is that it is also a "sufficient" 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".
This can also be applied to the problem of Assignment: Given a set of n employees, fill out a list of the jobs each of themwould be able to perform. Then, we can give each person a job suited to their abilities if, and only if, for every value of k (1...n), the union of any k of the lists contains at least k jobs.
The more general problem of selecting a (not necessarily distinct) element from each of a collection of sets is permitted in general only if the axiom of choice is accepted.
Proof
We prove the finite case of Hall's marriage theorem by induction on , the size of . The infinite case follows by a standard compactness argument.
The theorem is trivially true for .
Assuming the theorem true for all