Hall's marriage theorem

Let ${\displaystyle {\mathcal {F}}}$ be a finite family of sets (note that although ${\displaystyle {\mathcal {F}}}$ is not itself allowed to be infinite, the sets in it may be so, and ${\displaystyle {\mathcal {F}}}$ may contain the same set multiple times).[1] Let ${\displaystyle X}$ be the union of all the sets in ${\displaystyle {\mathcal {F}}}$, the set of elements that belong to at least one of its sets. A transversal for ${\displaystyle {\mathcal {F}}}$ is a subset of ${\displaystyle X}$ that can be obtained by choosing a distinct element from each set in ${\displaystyle {\mathcal {F}}}$. This concept can be formalized by defining a transversal to be the image of an injective function ${\displaystyle f:{\mathcal {F}}\to X}$ such that ${\displaystyle f(S)\in S}$ for each ${\displaystyle S\in {\mathcal {F}}}$. An alternative term for transversal is system of distinct representatives.

The collection ${\displaystyle {\mathcal {F}}}$ satisfies the marriage condition when each subfamily of ${\displaystyle {\mathcal {F}}}$ contains at least as many distinct members as its number of sets. That is, for all ${\displaystyle {\mathcal {G}}\subseteq {\mathcal {F}}}$,

$${\displaystyle |{\mathcal {G}}|\leq {\Bigl |}\bigcup _{S\in {\mathcal {G}}}S{\Bigr |}.}$$

If a transversal exists then the marriage condition must be true: the function ${\displaystyle f}$ used to define the transversal maps ${\displaystyle {\mathcal {G}}}$ to a subset of its union, of size equal to ${\displaystyle |{\mathcal {G}}|}$, so the whole union must be at least as large. Hall's theorem states that the converse is also true:

example 1, marriage condition met

Example 1

Consider the family ${\displaystyle {\mathcal {F}}=\{A_{1},A_{2},A_{3}\}}$ with ${\displaystyle X=\{1,2,3,4,5\}}$ and

$${\displaystyle {\begin{aligned}A_{1}&=\{1,2,3\}\\A_{2}&=\{1,4,5\}\\A_{3}&=\{3,5\}.\\\end{aligned}}}$$

The transversal ${\displaystyle \{1,3,5\}}$ could be generated by the function that maps ${\displaystyle A_{1}}$ to ${\displaystyle 1}$, ${\displaystyle A_{2}}$ to ${\displaystyle 5}$, and ${\displaystyle A_{3}}$ to ${\displaystyle 3}$, or alternatively by the function that maps ${\displaystyle A_{1}}$ to ${\displaystyle 3}$, ${\displaystyle A_{2}}$ to ${\displaystyle 1}$, and ${\displaystyle A_{3}}$ to ${\displaystyle 5}$. There are other transversals, such as ${\displaystyle \{2,1,3\}}$ and ${\displaystyle \{1,4,5\}}$. Because this family has at least one transversal, the marriage condition is met. Every subfamily of ${\displaystyle {\mathcal {F}}}$ has equal size to the set of representatives it is mapped to, which is less than or equal to the size of the union of the subfamily.

example 2, marriage condition violated

Example 2

Consider ${\displaystyle {\mathcal {F}}=\{A_{1},A_{2},A_{3},A_{4}\}}$ with

$${\displaystyle {\begin{aligned}A_{1}&=\{2,3,4,5\}\\A_{2}&=\{4,5\}\\A_{3}&=\{5\}\\A_{4}&=\{4\}.\\\end{aligned}}}$$

No valid transversal exists; the marriage condition is violated as is shown by the subfamily ${\displaystyle {\mathcal {G}}=\{A_{2},A_{3},A_{4}\}}$. Here the number of sets in the subfamily is ${\displaystyle |{\mathcal {G}}|=3}$, while the union of the three sets ${\displaystyle A_{2}\cup A_{3}\cup A_{4}=\{4,5\}}$ contains only two elements.

A lower bound on the different number of transversals that a given finite family ${\displaystyle {\mathcal {F}}}$ of size ${\displaystyle n}$ may have is obtained as follows: If each of the sets in ${\displaystyle {\mathcal {F}}}$ has cardinality ${\displaystyle \geq r}$, then the number of different transversals for ${\displaystyle {\mathcal {F}}}$ is either ${\displaystyle r!}$ if ${\displaystyle r\leq n}$, or ${\displaystyle r(r-1)\cdots (r-n+1)}$ if ${\displaystyle r>n}$.[2]

Recall that a transversal for a family ${\displaystyle {\mathcal {F}}}$ is an ordered sequence, so two different transversals could have exactly the same elements. For instance, the collection ${\displaystyle A_{1}=\{1,2,3\}}$, ${\displaystyle A_{2}=\{1,2,5\}}$ has ${\displaystyle (1,2)}$ and ${\displaystyle (2,1)}$ as distinct transversals.

In an ${\displaystyle X}$-perfect matching ${\displaystyle M}$, every edge incident to ${\displaystyle W}$ connects to a distinct neighbor of ${\displaystyle W}$ in ${\displaystyle Y}$, so the number of these matched neighbors is at least ${\displaystyle |W|}$. The number of all neighbors of ${\displaystyle W}$ is at least as large.

Consider the contrapositive: if there is no ${\displaystyle X}$-perfect matching then Hall's condition must be violated for at least one ${\displaystyle W\subseteq X}$. Let ${\displaystyle M}$ be a maximum matching, and let ${\displaystyle u}$ be any unmatched vertex in ${\displaystyle X}$. Consider all alternating paths (paths in ${\displaystyle G}$ that alternately use edges outside and inside ${\displaystyle M}$) starting from ${\displaystyle u}$. Let ${\displaystyle W}$ be the set of vertices in these paths that belong to ${\displaystyle X}$ (including ${\displaystyle u}$ itself) and let ${\displaystyle Z}$ be the set of vertices in these paths that belong to ${\displaystyle Y}$. Then every vertex in ${\displaystyle Z}$ is matched by ${\displaystyle M}$ to a vertex in ${\displaystyle W}$, because an alternating path to an unmatched vertex could be used to increase the size of the matching by toggling whether each of its edges belongs to ${\displaystyle M}$ or not. Therefore, the size of ${\displaystyle W}$ is at least the number ${\displaystyle |Z|}$ of these matched neighbors of ${\displaystyle Z}$, plus one for the unmatched vertex ${\displaystyle u}$. That is, ${\displaystyle |W|\geq |Z|+1}$. However, for every vertex ${\displaystyle v\in W}$, every neighbor ${\displaystyle w}$ of ${\displaystyle v}$ belongs to ${\displaystyle Z}$: an alternating path to ${\displaystyle w}$ can be found either by removing the matched edge ${\displaystyle vw}$ from the alternating path to ${\displaystyle v}$, or by adding the unmatched edge ${\displaystyle vw}$ to the alternating path to ${\displaystyle v}$. Therefore, ${\displaystyle Z=N_{G}(W)}$ and ${\displaystyle |W|\geq |N_{G}(W)|+1}$, showing that Hall's condition is violated.

A problem in the combinatorial formulation, defined by a finite family of finite sets ${\displaystyle {\mathcal {F}}}$ with union ${\displaystyle X}$ can be translated into a bipartite graph ${\displaystyle G=({\mathcal {F}},X,E)}$ where each edge connects a set in ${\displaystyle {\mathcal {F}}}$ to an element of that set. An ${\displaystyle {\mathcal {F}}}$-perfect matching in this graph defines a system of unique representatives for ${\displaystyle {\mathcal {F}}}$. In the other direction, from any bipartite graph ${\displaystyle G=(X,Y,E)}$ one can define a finite family of sets, the family of neighborhoods of the vertices in ${\displaystyle X}$, such that any system of unique representatives for this family corresponds to an ${\displaystyle X}$-perfect matching in ${\displaystyle G}$. In this way, the combinatorial formulation for finite families of finite sets and the graph-theoretic formulation for finite graphs are equivalent.

The same equivalence extends to infinite families of finite sets and to certain infinite graphs. In this case, the condition that each set be finite corresponds to a condition that in the bipartite graph ${\displaystyle G=(X,Y,E)}$, every vertex in ${\displaystyle X}$ should have finite degree. The degrees of the vertices in ${\displaystyle Y}$ are not constrained.

By examining Philip Hall's original proof carefully, Marshall Hall Jr. (no relation to Philip Hall) was able to tweak the result in a way that permitted the proof to work for infinite ${\displaystyle {\mathcal {F}}}$.[10] This variant extends Philip Hall's Marriage theorem.

Suppose that ${\displaystyle {\mathcal {F}}=\{A_{i}\}_{i\in I}}$, is a (possibly infinite) family of finite sets that need not be distinct, then ${\displaystyle {\mathcal {F}}}$ has a transversal if and only if ${\displaystyle {\mathcal {F}}}$ satisfies the marriage condition.

The following example, due to Marshall Hall Jr., shows that the marriage condition will not guarantee the existence of a transversal in an infinite family in which infinite sets are allowed.

Let ${\displaystyle {\mathcal {F}}}$ be the family, ${\displaystyle A_{0}=\mathbb {N} }$, ${\displaystyle A_{i}=\{i-1\}}$ for ${\displaystyle i\geq 1}$. The marriage condition holds for this infinite family, but no transversal can be constructed.[11]

The graph theoretic formulation of Marshal Hall's extension of the marriage theorem can be stated as follows: Given a bipartite graph with sides A and B, we say that a subset C of B is smaller than or equal in size to a subset D of A in the graph if there exists an injection in the graph (namely, using only edges of the graph) from C to D, and that it is strictly smaller in the graph if in addition there is no injection in the graph in the other direction. Note that omitting in the graph yields the ordinary notion of comparing cardinalities. The infinite marriage theorem states that there exists an injection from A to B in the graph, if and only if there is no subset C of A such that N(C) is strictly smaller than C in the graph.[12]

The more general problem of selecting a (not necessarily distinct) element from each of a collection of non-empty sets (without restriction as to the number of sets or the size of the sets) is permitted in general only if the axiom of choice is accepted.