Marriage theorem

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",

:$$|igcup T_i| ge |T|(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 $$I of the women, the number of men whom at least one of the women would be happy to marry, $$|igcup _{i in I} T_i|, be at least as big as the number of women in that subset, $$|I| = |{T_i: i in I}|. It is obvious that this condition is "necessary", as if it does not hold, there are not enough men to share among the $$I 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 $$leftvert S ightvert, the size of $$S. The infinite case follows by a standard compactness argument.

The theorem is trivially true for $$vert Svert=0.

Assuming the theorem true for all $$leftvert S ightvert, we prove it for $$leftvert S ightvert=n.

First suppose that we have the stronger condition$$leftvertcup T ightvert ge leftvert T ightvert+1for all $$emptyset e T subset S. Pick any $$xin S_n as the representative of $$S_n; we must choose an SDR from$$S' = left{S_1setminus{x},ldots,S_{n-1}setminus{x} ight}.But if$$ {S_{j_1}setminus{x},...,S_{j_k}setminus{x}} = T'subseteq S'then, by our assumption,$$leftvertcup T' ightvert ge leftvertcup_{i=1}^{k} S_{j_i} ightvert-1 ge k.By the already-proven case of the theorem for $$S' we see that we can indeed pick an SDR for $$S.

Otherwise, for some $$emptyset e T subset S we have the "exact" size$$leftvertcup T ightvert=leftvert T ightvert.Inside $$T itself, for any $$T'subseteq Tsubset S we have$$leftvertcup T' ightvertgeleftvert T' ightvert,so by an already-proven case of the theorem we can pick an SDR for $$T.

It remains to pick an SDR for $$Ssetminus T which avoids all elements of $$cup T (these elements are in the SDR for $$T). To use the already-proven case of the theorem (again) and do this, we must show that for any $$T'subseteq Ssetminus T, even after discarding elements of $$cup T there remain enough elements in $$cup T': we must prove$$leftvertcup T' setminus cup T ightvert ge leftvert T' ightvert.

But

$$leftvertcup T' setminus cup T ightvert

$$ = leftvertigcup(Tcup T') ightvert - leftvertcup T ightvert ge leftvert Tcup T' ightvert - leftvert T ightvert

$$ = leftvert T ightvert + leftvert T' ightvert - leftvert T ightvert = leftvert T' ightvert,

using the disjointness of $$T and $$T', and keeping in mind we are considering the case where $$leftvertcup T ightvert=leftvert T ightvert. So by an already-proven case of the theorem, $$Ssetminus T does indeed have an SDR which avoids all elements of $$cup T,

Q.E.D.

Corollary

If $$G(V_1, V_2, E) is a bipartite graph, then $$G has a complete matching that saturates every vertex of $$V_1 if and only if $$vert Svertleq vert N(S)vert for every subset $$Ssubset V_1.

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:

Let $$N_G(X) denote the neighborhood of "X" in "G". The Marriage theorem (Hall's Theorem) for Graph theory states that a perfect matching exists if and only if for every subset "X" of "S" :$$|X| leq |N_G(X)|In other words every subset "X" has enough adjacent vertices in "T".

A generalization to arbitrary graphs is provided by Tutte theorem.

A more general statement

Let G be a bipartite graph, BIP^N(X,Y), with X and Y not necessarily equally sized. Then G contains a matching of X into Y iff Hall's condition is satisfied for X.

If we denote the set of all vertices adjacent to at least one member of A by Г(A) (previously $$N_G(A)), then Hall's condition is that for all subsets A of X, |Г(A)| $$ge |A|.

Logical equivalences

This theorem is part of a collection of remarkably powerful theorems in combinatorics, all of which are logically equivalentFact|date=September 2008. These include:

* König's theorem
* The Konig-Egervary theorem (1931) (Dénes Kőnig, Jenő Egerváry)
* Menger's theorem (1927)
* The Max-Flow-Min-Cut theorem (Ford-Fulkerson Algorithm)
* The Birkhoff-Von Neumann theorem (1946)
* Dilworth's theorem

References

* [http://robertborgersen.info/Presentations/GS-05R-1.pdf Equivalence of seven major theorems in combinatorics]

External links

* [http://www.cut-the-knot.org/arithmetic/elegant.shtml Marriage Theorem] at cut-the-knot
* [http://www.cut-the-knot.org/arithmetic/marriage.shtml Marriage Theorem and Algorithm] at cut-the-knot