Hall's marriage theorem

Statement

Let $\mathcal{F} = (S_1, \dots, S_n)$ be a finite family of finite sets. A transversal of $\mathcal{F}$ is an injective function $f : \{1, \dots, n\} \to \bigcup_i S_i$ with $f(i) \in S_i$ for every $i$. Then $\mathcal{F}$ has a transversal if and only if $\left| \bigcup_{i \in I} S_i \right| \ge |I|$ for every $I \subseteq \{1, \dots, n\}$.

Remarks

The condition on all subfamilies is the marriage condition. It is necessary, because a transversal $f$ maps $I$ injectively into $\bigcup_{i \in I} S_i$. A transversal is also called a system of distinct representatives. The sets $S_i$ may repeat in the family. The theorem is equivalent to Hall's theorem for bipartite graphs.

History

Philip Hall proved the theorem in 1935. The name marriage theorem comes from a 1950 paper by Halmos and Vaughan.

Explanations

L1 human

Each of $n$ people has a list of acceptable partners, and we want to give each person a different partner from the list. This is possible exactly when every group of $k$ people has at least $k$ names on their lists together.