Marriage theorem

From Free net 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 set 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,

<math>|\bigcup T_i| \ge |T|</math> (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 set 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 (somewhat dated at this point) 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 <math>I</math> of the women, the number of men whom at least one of the women would be happy to marry (<math>|\bigcup _{i \in I} T_i|</math>) be at least as big as the number of women, <math>|I| = |\{T_i: i \in I\}|</math>. It is obvious that this condition is necessary, as if it does not hold, there are not enough men to share between the <math>I</math> 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 <math>\left\vert S\right\vert</math>, the size of <math>S</math>.

The theorem is trivially true for <math>\vert S\vert=0</math>.

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

First suppose that we have the stronger condition <math> \left\vert\cup T\right\vert \ge \left\vert T\right\vert+1</math> for all <math>\emptyset \ne T \subset S</math>. Pick any <math>x\in S_n</math> as the representative of <math>S_n</math>; we must choose an SDR from <math> S' = \left\{S_1\setminus\{x\},\ldots,S_{n-1}\setminus\{x\}\right\}</math>. But if <math> \{S_{j_1}\setminus\{x\},...,S_{j_k}\setminus\{x\}\} = T'\subseteq S'</math> then, by our assumption, <math> \left\vert\cup T'\right\vert \ge \left\vert\cup_{i=1}^{k} S_{j_i}\right\vert-1 \ge k</math>. By the already-proven case of the theorem for <math>S'</math> we see that we can indeed pick an SDR for <math>S'</math>.

Otherwise, for some <math>\emptyset\ne T \subset S</math> we have the ``exact size <math> \left\vert\cup T\right\vert=\left\vert T\right\vert</math>. Inside <math>T</math> itself, for any <math>T'\subseteq T\subset S</math> we have <math> \left\vert\cup T'\right\vert\ge\left\vert T'\right\vert</math>, so by an already-proven case of the theorem we can pick an SDR for <math>T</math>.

It remains to pick an SDR for <math>S\setminus T</math> which avoids all elements of <math>\cup T</math> (these elements are in the SDR for <math>T</math>). To use the already-proven case of the theorem (again) and do this, we must show that for any <math>T'\subseteq S\setminus T</math>, even after discarding elements of <math>\cup T</math> there remain enough elements in <math>\cup T'</math>: we must prove <math> \left\vert\cup T' \setminus \cup T\right\vert \ge \left\vert T'\right\vert</math>.

But

<math>\left\vert\cup T' \setminus \cup T\right\vert</math>

<math> = \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</math> (*)

<math> = \left\vert T\right\vert + \left\vert T'\right\vert - \left\vert T\right\vert = \left\vert T'\right\vert</math>,

using the disjointness of <math>T</math> and <math>T'</math>. So by an already-proven case of the theorem, <math>S\setminus T</math> does indeed have an SDR which avoids all elements of <math>\cup T</math>.

This completes the proof

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

[edit]

Corollary

If <math>G(V_1, V_2, E)</math> is a bipartite graph, then <math>G</math> has a complete matching that saturates every vertex of <math>V_1</math> if and only if <math>\vert S\vert\leq \vert N(S)\vert</math> for every subset <math>S\subset V_1</math>.

[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 <math>N_G(X)</math> 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

In other words every subset X has enough adjacent vertices in T.

A generalization to arbitrary graphs is provided by Tutte theorem.

[edit]