Hall's Marriage Theorem

Recall from the Systems of Distinct Representatives page that if $A$ is a finite set and $\mathcal A = (A_1, A_2, ..., A_n)$ is a collection of subsets of $A$ then a system of distinct representatives of $\mathcal A$ is a collection of elements $x_1, x_2, ..., x_n$ where $x_i \neq x_j$ for each $i, j \in \{1, 2, ..., n \}$, $i \neq j$ and such that $x_i \in A_i$ for each $i \in \{1, 2, ..., n \}$.

We noted that if $\biggr \lvert \bigcup_{i=1}^{n} A_i \biggr \rvert$ contains less than $n$ elements then a system of distinct representatives of $\mathcal A$ does not exist as there are not enough distinct elements $x_i$ to represent all $n$ sets in the collection $\mathcal A$. We will now expand further on this with a very famous theorem known as Hall's Marriage Theorem or simply, Hall's Theorem which provides us with a necessary and sufficient condition for whether a system of distinct representatives exists for a collection of subsets $\mathcal A$.

Theorem 1 (Hall's Marriage Theorem): Let $A$ be a finite set. The collection of subsets $\mathcal A = (A_1, A_2, ..., A_n)$ of $A$ has a system of distinct representatives if and only if for every integer $k$ such that $1 \leq k \leq n$ and $\{ i_1, i_2, ..., i_k \} \subseteq \{ 1, 2, ..., n \}$ we have that $\biggr \lvert \bigcup_{j=1}^{k} A_{i_j} \biggr \rvert \geq k$.

In simpler terms, Hall's Marriage Theorem says that if $A$ is a finite set then within any collection of $n$ subsets of $A$ there exists a system of distinct representatives if and only if for any subcollection of $k$ sets from $\mathcal A$ we have that their union contains at least $k$-elements.

• Proof: Let $A$ be a finite set and let $\mathcal A = (A_1, A_2, ..., A_n)$ be a collection of subsets of $A$.

• $\Rightarrow$ Suppose that there exists a system of distinct representatives of $\mathcal A$. Assume that for some subcollection $\mathcal B = (A_{i_1}, A_{i_2}, ..., A_{i_k})$ of $k$ subsets of $\mathcal A$ where $\{i_1, i_2, ..., i_k \} \subseteq \{ 1, 2, ..., n \}$ is such that $\biggr \lvert \bigcup_{j=1}^{k} A_{i_j} \biggr \rvert = p < k$. Then we have that $A_{i_1} \cup A_{i_2} \cup ... \cup A_{i_k} = \{x_1, x_2, ..., x_p \}$. To form a system of distinct representatives of $\mathcal B$ we need at least $k$ distinct elements between all $k$ subsets in the subcollection $\mathcal B$ but we only have $p < k$. Therefore no system of distinct representatives exists in $\mathcal B$. By extension, we cannot create a system of distinct representatives of $\mathcal A$ since the sets in the subcollection $\mathcal B$ cannot be distinctly represented, so we have arisen at a contradiction and so for every subcollection $\mathcal B = (A_{i_1}, A_{i_2}, ..., A_{i_k})$ of $k$ subsets of $\mathcal A$ we have that:

(1)

\begin{align} \quad \biggr \lvert \bigcup_{j=1}^{k} A_{i_j} \biggr \rvert \geq k \end{align}

• $\Leftarrow$ Now suppose that for each positive integer $k$ such that $1 \leq k \leq n$ and $\{i_1, i_2, ..., i_k \} \subseteq \{ 1, 2, ..., n \}$ that every subcollection $\mathcal B = (A_{i_1}, A_{i_2}, ..., A_{i_k})$ satisfies $\biggr \lvert \bigcup_{j=1}^{k} A_{i_j} \biggr \rvert \geq k$ has a system of distinct representatives as our induction hypothesis.

• First consider the case where for every positive integer $k$ such that $1 \leq k < n$ and $\{ i_1, i_2, ..., i_k \} \subset \{1, 2, ..., n \}$ that every subcollection $\mathcal B = (A_{i_1}, A_{i_2}, ..., A_{i_k})$ satisfies $\biggr \lvert \bigcup_{j=1}^{k} A_{i_j} \biggr \rvert \geq k + 1$. Choose any element $x_n \in A_n$ and consider the collection of sets $B_1, B_2, ..., B_{n-1}$ defined for each $i \in \{1, 2, ..., n-1 \}$ by:

(2)

\begin{align} \quad B_i = A_i \setminus \{ x_n \} \end{align}

• For each subset $B_i$ there are two cases to consider. If $x_n \not \in A_i$ then $A_i \setminus \{ x_n \} = A_i$ so then $B_i = A_i$ and $\mid B_i \mid = \mid A_i \mid$. If $x_n \in A_i$ then $\mid B_i \mid = \mid A_i \mid - 1$. So between any subcollection of $k$ subsets of $B_1, B_2, ..., B_{n-1}$ we have that each subset $B_i$ contains at least $\mid A_i \mid - 1$ distinct elements. The union of any collection of $k$ many $B_i$ has either as many elements as the union of corresponding $k$ many $A_i$ or $1$ less. Therefore:

(3)

\begin{align} \quad \biggr \lvert \bigcup_{j=1}^{k} B_{i_j} \biggr \rvert \geq k \end{align}

• Therefore $B_1, B_2, ..., B_{n-1}$ has a system of distinct representatives.

• Now consider the case where for every positive integer $k$ where $1 \leq k < n$ we have that for $\{ i_1, i_2, ..., i_k \} \subset \{ 1, 2, ..., n \}$ that every subcollection $\mathcal B = (A_{i_1}, A_{i_2}, ..., A_{i_k})$ is such that $\biggr \lvert \bigcup_{j=1}^{k} A_{i_j} \biggr \rvert \not \geq k + 1$. Then for some $k$ where $1 \leq k < n$ we have that $\biggr \lvert \bigcup_{j=1}^{k} A_{i_j} \biggr \rvert = k$. Suppose that that $\biggr \lvert \bigcup_{i=1}^k A_i \biggr \rvert = k$. By our induction hypothesis, since $1 \leq k < n$ we have that $A_1, A_2, ..., A_k$ have a system of distinct representatives $(x_1, x_2, ..., x_k)$.

• For each $i \in \{k+1, k+2, ..., n \}$ define $B_i$ as:

(4)

\begin{align} \quad B_i = A_i \setminus \bigcup_{j=1}^{k} A_j \end{align}

• We obtain another collection of $n - k$ subsets $B_{k+1}, B_{k+2}, ..., B_n$ to which none of these sets contain elements from $A_1$, $A_2$, …, $A_k$. We will show that a system of distinct representatives exist for the collection $B_{k+1}, B_{k+2}, ..., B_n$.

• Consider the subcollection $B_{i_1}, B_{i_2}, ..., B_{i_q}$ where $\{ i_1, i_2, ..., i_q \} \subseteq \{ k+1, k+2, ..., n \}$. Recall that none of the $B$'s share any elements in common with $A_1, A_2, ..., A_k$. So for each positive integer $t$ such that $1 \leq t \leq q$ we have that $\left ( \bigcup_{i=1}^{k} A_i \right ) \cup B_{i_t} = \emptyset$. By the addition principle we get:

(5)

\begin{align} \quad \biggr \lvert \left ( \bigcup_{i=1}^{k} A_i \right ) \cup \left ( \bigcup_{k=1}^{q} B_{i_k} \right ) \biggr \rvert = \biggr \lvert \bigcup_{i=1}^{k} A_i \biggr \rvert + \biggr \lvert \bigcup_{k=1}^{q} B_{i_k} \biggr \rvert \\ \quad \biggr \lvert \left ( \bigcup_{i=1}^{k} A_i \right ) \cup \left ( \bigcup_{k=1}^{q} B_{i_k} \right ) \biggr \rvert \overset{I.H.} = k + \biggr \lvert \bigcup_{k=1}^{q} B_{i_k} \biggr \rvert \\ \end{align}

• Also, for each positive integer $t$ such that $1 \leq t \leq q < n - k$ we have that:

(6)

\begin{align} \quad \biggr \lvert \left ( \bigcup_{i=1}^{k} A_i \right ) \cup \left ( \bigcup_{k=1}^{q} B_{i_k} \right ) \biggr \rvert = \biggr \lvert \left ( \bigcup_{i=1}^{k} A_i \right ) \cup A_{i_1} \cup A_{i_2} \cup ... \cup A_{i_q} \biggr \rvert \overset{I.H.} \geq k + q \end{align}

• Therefore:

(7)

\begin{align} \quad k + \biggr \lvert \bigcup_{k=1}^{q} B_{i_k} \biggr \rvert = \biggr \lvert \left ( \bigcup_{i=1}^{k} A_i \right ) \cup \left ( \bigcup_{k=1}^{q} B_{i_k} \right ) \biggr \rvert = \biggr \lvert \left ( \bigcup_{i=1}^{k} A_i \right ) \cup A_{i_1} \cup A_{i_2} \cup ... \cup A_{i_q} \biggr \rvert \geq k + q \end{align}

• So we have that $\biggr \lvert \bigcup_{k=1}^{q} B_{i_k} \biggr \rvert \geq q$ for each $1 \leq q \leq n - k < n$. Therefore by our induction hypothesis $B_{k+1}, B_{k+2}, ..., B_n$ has a system of distinct representatives $(x_{k+1}, x_{k+2}, ..., x_n)$ which is also a system of distinct representatives of $A_{k+1}, A_{k+2}, ..., A_n$, all of whose elements are different from the system of distinct representatives $(x_1, x_2, ..., x_k)$ of $A_1, A_2, ..., A_k$ by the way we defined the $B_i$'s. Therefore $(x_1, x_2, ..., x_k, x_{k+1}, ..., x_n)$ is a system of distinct representatives for $\mathcal A = (A_1, A_2, ..., A_n)$. $\blacksquare$