Hall's Marriage Theorem

Hall's marriage theorem is a result in combinatorics that specifies when distinct elements can be chosen from a collection of overlapping finite sets. It is equivalent to several beautiful theorems in combinatorics, including Dilworth's theorem. The name comes from an application to matchmaking: given a list of potential matches among an equal number of brides and grooms, the theorem gives a necessary and sufficient condition on the list for everyone to be married to an agreeable match.

Suppose I have $6$ gifts (labeled $1,2,3,4,5,6$) to give at Christmas, to $5$ friends (Alice, Bob, Charles, Dot, Edward). Can I distribute one gift to each person so that everyone gets something they want?

Certainly this depends on the preferences of my friends. If none of them like any of the gifts, then I am out of luck. But even if they all like some of the gifts, I may still not be able to give them out satisfactorily. For instance, if none of them like gifts $5$ or $6$, then I will have only $4$ gifts to give to my $5$ friends. Or suppose that

Alice wants: 1,3
Bob wants: 2,4,5,6
Charles wants: 2,3
Dot wants: 1,2,3
Edward wants: 2

There is still no way to distribute the gifts to make everyone happy. In fact, notice that I have four friends (Alice, Charles, Dot, Edward) who only want one of the first three gifts, which makes it clear that the problem is impossible.

It turns out, however, that this is the only way for the problem to be impossible. As long as there isn't a subset of the friends that collectively likes fewer gifts than there are friends in the subset, there will always be a way to give everyone something they want. This is the crux of Hall's marriage theorem.

Let $S$ be a family of finite sets. Here $S$ is allowed to be infinite, and elements in $S$ can be repeated. A transversal $T$ for $S$ is a set $T$ and a bijection $f \colon T \to S$ such that $t \in f(t)$ for all $t\in T$.

So a transversal consists of a choice of an element $t$ in each of the sets in $S$; the point is that the elements chosen must be unique even if the sets overlap. When $S$ is finite, a transversal for $S$ is often given as an ordered tuple of elements of the sets in $S$.

Let $S = \{ \{1,2,3\},\{2,3,4\},\{1,3\} \}$. Then $(1,4,3)$ is a transversal of $S$: pick $1$ from the first set, $4$ from the second set, $3$ from the third set. Note that if instead we try to pick $1$ from the first set and $3$ from the second set, there is no choice of element from the third set that leads to a transversal.

(Hall's Marriage Theorem) Let $S$ be a finite family of finite sets. Suppose that for every subfamily $R$ of sets in $S$, the number of subsets in $R$ is less than or equal to the total number of elements in those subsets: $$|R| \le \left |\bigcup_{X \in R} X\right |.$$ Then $S$ has at least one transversal.

Notes:

(1) The condition given in the theorem is clearly necessary for the existence of a transversal, because any transversal must include $|R|$ distinct elements from the sets in $R$, so those sets must together contain at least $|R|$ elements.

(2) The condition given in the theorem is generally called the "marriage condition." So Hall's Marriage Theorem says that $S$ has a transversal if and only if it satisfies the marriage condition.

Suppose there are $n$ women and $n$ men, all of whom want to get married to someone of the opposite sex. Suppose further that the women each have a list of the men they would be happy to marry, and that every man would be happy to marry any woman who is happy to marry him, and that each person can only have one spouse.

In this case, Hall's marriage theorem says that the men and women can all be paired off in marriage so that everyone is happy, if and only if the marriage condition holds: if in any group of women, the total number of men who are acceptable to at least one of the women in the group is greater than or equal to the size of the group.

Again, it is clear that this condition is necessary. Hall's marriage theorem is that it is sufficient as well. To see why the theorem applies in this case, let $S_i$ be the set of men that the $i$th woman would be happy to marry; then the marriage condition in the previous paragraph is the same as the marriage condition on the family of sets $S_i$. So there is a transversal $T$, which is a choice of an acceptable man for each woman.

Hall's marriage theorem can be restated in a graph theory context.

A bipartite graph is a graph where the vertices can be divided into two subsets $V_1$ and $V_2$ such that all the edges in the graph connect vertices from $V_1$ to vertices in $V_2$. (So none of the vertices in $V_1$ or in $V_2$ are connected to each other.)

A matching on a graph is a choice of edges with no common vertices. It covers a set $V$ of vertices if each vertex in $V$ is an endpoint of one of the edges in the matching.

A matching corresponds to a choice of 1s in the adjacency matrix, with at most one 1 in each row and in each column.

Suppose a bipartite graph has parts $V_1$ and $V_2$. Hall's marriage theorem says that there is a matching that covers $V_1$ if and only if, for every subset $W$ of $V_1$, the number of edges in the graph with endpoints in $W$ is $\ge |W|$.

Shuffle a deck of cards and deal $13$ piles of four cards each. Show that there is always a way to choose a card from each pile in such a way that the $13$ cards chosen contain one card of each rank (one ace, one king, etc.)

---

Consider the family of sets $S_i$ consisting of the ranks of the cards in pile $i$. A subfamily consists of $n$ subsets, which contains the ranks of $4n$ cards. Since there are only four cards of each rank, there must be at least $n$ distinct ranks. So the marriage condition is satisfied, so there is a transversal by Hall's marriage theorem. This transversal is exactly what the problem asks for. $\square$

(Putnam 2012 B3) A round-robin tournament of $2n$ teams lasted for $2n-1$ days, as follows. On each day, every team played one game against another team, with one team winning and one team losing in each of the $n$ games. Over the course of the tournament, each team played every other team exactly once. Can one necessarily choose one winning team from each day without choosing any team more than once?

---

The answer is yes. On the $i$th day, let $S_i$ be the set of winning teams. Each set $S_i$ has $n$ elements. To show that a transversal exists, we must show that the marriage condition holds.

Suppose it does not--so there are $k$ sets $S_i$ whose union contains less than $k$ elements; that is, suppose there are $k$ days in which fewer than $k$ teams won at least once. In this case, there will be at least one team that lost in every one of the $k$ rounds. But the $k$ teams it lost to will all have won at least once--contradiction.

So a transversal exists, and a transversal is just a choice of a distinct winning team from each day, as desired. $\square$

Other examples are given in this page: Applications of Hall's marriage theorem.

Here is a proof using Dilworth's theorem. Suppose $|S| = n$. Say the sets in $S$ are $X_1, X_2, \ldots, X_n$. Suppose the union of the sets $X_i$ consists of the elements $x_1, x_2, \ldots, x_k$. Now define a partial order on $$\{ x_1, x_2, \ldots, x_k, X_1, X_2, \ldots, X_n \}$$ by $x_i \le X_j$ if and only if $x_i \in X_j$. (And: no two $x_i$ are comparable and no two $X_j$ are comparable.)

The marriage condition implies that the largest antichain in this set is $\{x_1, x_2, \ldots, x_k \}$. This is because if there were a larger antichain consisting of $j$ $X$'s and $> k-j$ $x$'s, those $j$ $X$'s would contain only the $x$'s not in the antichain, of which there are $< j$, which would violate the marriage condition.

Then by Dilworth's theorem, there is a cover by $k$ chains. Each $x_i$ is in exactly one chain in the cover, and the chains in the cover are either $\{x_i\}$ or $\{x_i,X_j\}$. Since every $X_j$ must appear in the chain cover, the elements $x_i$ that appear alongside the $X_j$ form a transversal. $\square$