Hall's marriage theorem

In mathematics, Hall's marriage theorem is a combinatorial result that gives the condition allowing the selection of a distinct element from each of a collection of finite sets. It was proved by Philip Hall (1935).

Definitions and statement of the theorem

Let S be a collection of finite sets.

A transversal for S is a set X and a bijection f from X to S such that for all x in X, x is a member of f(x). An alternative term for transversal is system of distinct representatives or "SDR".

The collection S satisfies the marriage condition if and only if for each subcollection $T \subseteq S$, we have

$|T| \le \Bigl|\bigcup_{A \in T} A\Bigr|.$

In other words, the number of subsets in each subcollection T is less than or equal to the number of distinct elements in the union over the subcollection T.

Hall's theorem states that S has a transversal (SDR) if and only if S satisfies the marriage condition.

Discussion and examples

Example 1: Consider S = {S₁, S₂, S₃} with

S₁ = {1, 2, 3}

S₂ = {1, 4, 5}

S₃ = {3, 5}.

A valid SDR would be {1, 4, 5}. (Note this is not unique: {2, 1, 3} works equally well, for example.)

Example 2: Consider S = {S₁, S₂, S₃, S₄} with

S₁ = {2, 3, 4, 5}

S₂ = {4, 5}

S₃ = {5}

S₄ = {4}.

No valid SDR exists; the marriage condition is violated as is shown by the subcollection {S₂, S₃, S₄}.

The standard example of an application of the marriage theorem is to imagine two groups; one of n men, and one of n women. For each woman, there is a subset of the men any one of which she would happily marry; 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 S_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 {S_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, $|\bigcup _{i \in I} S_i|$, be at least as big as the number of women in that subset, | 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 always 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 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 first prove: If G has a matching which covers every vertex in X then |N(S)| ≥ |S| for all S C X. Suppose G(X,Y) is a bipartite graph and M is a matching which saturates every vertex of X. Consider the set of all vertices in Y which saturates a given S by the matching M to be M(S). Therefore, |M(S)|=|S|, by definition of matching. But M(S) C N(S), since all elements of M(S) are neighbours of S. So, |N(S)| ≥ |M(S)| and hence, |N(S)| ≥ |S|. Now we prove: If |N(S)| ≥ |S| for all S C X, then G(X,Y) has a matching which saturates every vertex in X. Assume G(X,Y) is a bipartite graph that has no matching M which saturates all vertices of X. Consider a set S containing vertex u which is not saturated by a maximum matching M. Consider all augmenting paths starting from u. Let the set of all points in Y connected to u by these augmenting paths be T. Consider set of all vertices of S (in X) in these paths such that S \ u is saturated by M. So, |M(S)|=|S|-1, as u is not in a matching. But, all vertices in T are connected to u and set of all vertices connected to a vertex in S\u is in T. Therefore, |N(S)|=|T|. But |N(u)|=|T| as all neighbours of u are included in T. Also, for every vertex connected to u in T there exists a corresponding matching to another vertex in S. Hence, |N(u)|=number of matchings=|M(S)|=|S|-1. But |N(u)|=|T|=|N(S)|. Thus, |N(S)|=|S|-1 which implies |N(S)|<|S| (contradiction). Hence our assumption that G has no matching is false, therefore, G has a matching.

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 finite bipartite graph G:= (S + T, E) with two equally sized partitions S and T, does there exist a perfect matching, i.e. a set of edges so that every vertex of G is incident to precisely one of them?

The marriage theorem provides the answer:

For a set X of vertices of G, let N_G(X) denote the neighborhood of X in G, i.e. the set of all vertices adjacent to some element of X. 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 of S has enough adjacent vertices in T.

A generalization to arbitrary graphs is provided by Tutte theorem.

A more general statement

Let G:= (S + T, E) be a finite bipartite graph with S and T not necessarily equally sized. Then G contains a matching of S into T if and only if

$|X| \leq |N_G(X)|$

for all subsets X of S.

Logical equivalences

This theorem is part of a collection of remarkably powerful theorems in combinatorics, all of which are related to each other in an informal sense in that it is more straightforward to prove one of these theorems from another of them than from first principles. These include:

• The König–Egerváry 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.

In particular,^[1] there are simple proofs of the implications Dilworth's theorem ⇒ Hall's theorem ⇔ König–Egerváry theorem ⇔ König's theorem.

Notes

1. ^ Equivalence of seven major theorems in combinatorics

References

• Dongchen, Jiang; Nipkow, Tobias (2010), "Hall's Marriage Theorem", The Archive of Formal Proofs, ISSN 2150-914x, http://afp.sourceforge.net/entries/Marriage.shtml. Computer-checked proof. 
• Hall, Philip (1935), "On Representatives of Subsets", J. London Math. Soc. 10 (1): 26–30, doi:10.1112/jlms/s1-10.37.26 
• Halmos, Paul R. and Vaughan, Herbert E. "The marriage problem". American Journal of Mathematics 72, (1950). 214–215.

External links

• Marriage Theorem at cut-the-knot
• Marriage Theorem and Algorithm at cut-the-knot

This article incorporates material from proof of Hall's marriage theorem on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.