Hall's Theorem and Systems of Distinct Representatives

Hall's marriage theorem characterizes when a bipartite graph has a matching that saturates one side. It is equivalent to several fundamental results in combinatorics and has elegant applications to Latin squares, permutation matrices, and fair division.

Hall's Condition

Definition6.3Hall's Marriage Condition

For a bipartite graph $G = (X \cup Y, E)$ , define $N(S) = \{y \in Y : xy \in E \text{ for some } x \in S\}$ for $S \subseteq X$ . Hall's condition: $|N(S)| \geq |S|$ for all $S \subseteq X$ . A system of distinct representatives (SDR) for subsets $A_1, \ldots, A_n$ of a set $Y$ is a choice of distinct elements $a_i \in A_i$ . An SDR exists iff Hall's condition holds for the bipartite graph with edges $\{(i, y) : y \in A_i\}$ .

ExampleLatin Squares from Hall's Theorem

A Latin square of order $n$ is an $n \times n$ array filled with $n$ symbols so each appears exactly once per row and column. Hall's theorem proves existence: the first row is any permutation. For subsequent rows, the bipartite graph (positions vs. symbols) satisfies Hall's condition because each symbol appears equally often in available positions. By induction, all $n$ rows can be completed.

Deficiency and Matching Extensions

Definition6.4Hall's Deficiency Version

The deficiency of $G$ relative to $X$ is $\mathrm{def}(G) = \max_{S \subseteq X}(|S| - |N(S)|)$ . The maximum matching saturating $X$ has size $|X| - \mathrm{def}(G)$ . When $\mathrm{def} = 0$ , Hall's condition holds and $X$ can be completely matched.

RemarkApplications of Hall's Theorem

(1) Doubly stochastic matrices: Birkhoff's theorem says every doubly stochastic matrix is a convex combination of permutation matrices. The proof uses Hall's theorem iteratively to find permutation matrices. (2) Dilworth's theorem: in a partially ordered set, the minimum number of chains covering all elements equals the maximum antichain size. This follows from Hall's theorem applied to an associated bipartite graph.

Stable Matchings

Definition6.5Stable Matching

Given $n$ men and $n$ women with preference lists, a stable matching has no blocking pair: a man $m$ and woman $w$ who prefer each other to their current partners. The Gale-Shapley algorithm (1962) produces a stable matching in $O(n^2)$ time: men propose to their most preferred unmatched woman; women tentatively accept their best proposal and reject others. The result is man-optimal (each man gets his best stable partner) and woman-pessimal.