Hall’s marriage theorem

Let $S=\{S_1,S_2,\mathrm{\dots }{S}_n\}$ be a finite collection of finite sets. There exists a system of distinct representatives of $S$ if and only if the following condition holds for any $T\subseteq S$:

$$\left|\cup T\right|\ge |T|$$

As a corollary, if this condition fails to hold anywhere, then no SDR exists.

This is known as Hall’s marriage theorem. The name arises from a particular application of this theorem. Suppose we have a finite set of single men/women, and, for each man/woman, a finite collection of women/men to whom this person is attracted. An SDR for this collection would be a way each man/woman could be (theoretically) married happily. Hence, Hall’s marriage theorem can be used to determine if this is possible.

An application of this theorem to graph theory gives that 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 $|S|\le |N(S)|$ for every subset $S\subset V_1$.

Title	Hall’s marriage theorem
Canonical name	HallsMarriageTheorem
Date of creation	2013-03-22 12:35:14
Last modified on	2013-03-22 12:35:14
Owner	mathcam (2727)
Last modified by	mathcam (2727)
Numerical id	6
Author	mathcam (2727)
Entry type	Theorem
Classification	msc 05D15
Synonym	marriage theorem
Related topic	Saturate