Hall's marriage theorem

Hall's theorem (1935), also known as the marriage theorem is usually credited to mathematician Philip Hall. The theorem is a combinatorial result that gives the condition allowing the selection of a distinct element from each of a collection of finite sets.

Definitions and statement of the theorem

Let S = {S₁, S₂, ... } be a (not necessarily countable) collection of finite sets. A transversal for S, also known as a system of distinct representatives (SDR) for S, is a set X = {x₁, x₂, ...} of distinct elements with the property that for all i, x_i∈S_i.

The marriage condition for S is that, for any subcollection $T\subseteq S$,

$|T|\leq {\Bigl |}\bigcup _{A\in T}A{\Bigr |}$

(where |T| denotes the cardinality of the collection T).

Hall's theorem then states that there exists an SDR X if and only if S meets 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. 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 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 prove the finite case of Hall's marriage theorem by induction on $\left\vert S\right\vert$, the size of $S$. The infinite case follows by a compactness argument.

The theorem is trivially true for $\vert S\vert =0$.

Assuming the theorem true for all $\left\vert S\right\vert <n$, we prove it for $\left\vert S\right\vert =n$.

First suppose that we have the stronger condition $\left\vert \cup T\right\vert \geq \left\vert T\right\vert +1$ for any nonempty proper subset T of S. Pick any $x\in S_{n}$ to be a representative of $S_{n}$ to be part of an SDR R for S. If there is an SDR R' for $S'=\left\{S_{1}\setminus \{x\},\ldots ,S_{n-1}\setminus \{x\}\right\}$, then $R'\cup \{x\}$ is an SDR for S. But if $\{S_{j_{1}}\setminus \{x\},...,S_{j_{k}}\setminus \{x\}\}=T'\subseteq S'$ then, by our assumption, $\left\vert \cup T'\right\vert \geq \left\vert \cup _{i=1}^{k}S_{j_{i}}\right\vert -1\geq 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 \neq T\subset S$ we have the exact size $\left\vert \cup T\right\vert =\left\vert T\right\vert$. Inside $T$ itself, for any $T'\subseteq T\subset S$ we have $\left\vert \cup T'\right\vert \geq \left\vert T'\right\vert$, so by an already-proven case of the theorem we can pick an SDR for $T$.

It remains to pick an SDR for $S\setminus 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 S\setminus T$, even after discarding elements of $\cup T$ there remain enough elements in $\cup T'$: we must prove $\left\vert \cup T'\setminus \cup T\right\vert \geq \left\vert T'\right\vert$.

But

$\left\vert \cup T'\setminus \cup T\right\vert$

$=\left\vert \bigcup (T\cup T')\right\vert -\left\vert \cup T\right\vert \geq \left\vert T\cup T'\right\vert -\left\vert T\right\vert$

$=\left\vert T\right\vert +\left\vert T'\right\vert -\left\vert T\right\vert =\left\vert T'\right\vert ,$

using the disjointness of $T$ and $T'$, and keeping in mind we are considering the case where $\left\vert \cup T\right\vert =\left\vert T\right\vert$. So by an already-proven case of the theorem, $S\setminus T$ does indeed have an SDR which avoids all elements of $\cup T.$

Q.E.D.

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:

• König's theorem
• 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, there are simple proofs of the implications Dilworth's theorem ⇒ Hall's theorem ⇔ König-Egerváry theorem ⇔ König's theorem.

External links

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

proof of Hall's marriage theorem at PlanetMath.