Marriage theorem

From Wikipedia, the free encyclopedia

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.

Let S = {S₁, S₂, ... } be a (not necessarily countable) set of finite subsets of some larger collection M. A system of distinct representatives (sometimes abbreviated as an SDR) is a set X = {x₁, x₂, ...} of pairwise 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 subset T = {T_i} of S,

$|\bigcup T_i| \ge |T|$ (i.e. any n subsets taken together have at least n elements)

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, 2, 3} S₂ = {1, 4, 5} S₃ = {3, 5}

For this set S = {S₁, S₂, S₃}, a valid SDR would be {1, 4, 5}. (Note this is not unique: {3, 4, 5} 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 the men and women so that every person is happy.

If we let M_i be the set of men that the ith 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 ( $|\bigcup _{i \in I} T_i|$ ) be at least as big as the number of women, $|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 between 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 them would 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.

1 Proof
- 1.1 Corollary
2 Graph theory
3 Logical Equivalences
4 References
5 External links

[edit] Proof

We prove Hall's marriage theorem by induction on $\left\vert S\right\vert$ , the size of $S$ .

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 \ge \left\vert T\right\vert+1$ for all $\emptyset \ne T \subset S$ . Pick any $x\in S_n$ as the representative of $S n$ ; we must choose an SDR from $S' = \left\{S_1\setminus\{x\},\ldots,S_{n-1}\setminus\{x\}\right\}$ . 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 \ge \left\vert\cup_{i=1}^{k} S_{j_i}\right\vert-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\ne 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\ge\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 \ge \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 \ge \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'$ . So by an already-proven case of the theorem, $S\setminus T$ does indeed have an SDR which avoids all elements of $\cup T$ .

This completes the proof

(*) See the Talk page for a dispute about this inequality.

[edit] 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 S\vert\leq \vert N(S)\vert$ for every subset $S\subset V_1$ .

[edit] 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)\|$