Hall's marriage theorem

Let $\backslash mathcal\; F$ be a finite family of sets (note that although $\backslash mathcal\; F$ is not itself allowed to be infinite, the sets in it may be so, and $\backslash mathcal\; F$ may contain the same set multiple times).{{harvnb|Hall|1986|loc=pg. 51}}. An alternative form of the marriage theorem applies to finite families of sets that can be infinite. However, the situation of having an infinite number of sets while allowing infinite sets is not allowed. Let $X$ be the union of all the sets in $\backslash mathcal\; F$, the set of elements that belong to at least one of its sets. A transversal for $\backslash mathcal\; F$ is a subset of $X$ that can be obtained by choosing a distinct element from each set in $\backslash mathcal\; F$. This concept can be formalized by defining a transversal to be the image of an injective function $f:\backslash mathcal\; F\backslash to\; X$ such that $f(S)\backslash in\; S$ for each $S\backslash in\backslash mathcal\; F$. An alternative term for transversal is system of distinct representatives.

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

$$|\backslash mathcal\; G|\backslash le\backslash Bigl|\backslash bigcup\_\{S\backslash in\; \backslash mathcal\; G\}\; S\backslash Bigr|.$$

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

{{math_theorem

| name = Hall's Marriage Theorem

| math_statement = A family $\backslash mathcal\; F$ of finite sets has a transversal if and only if $\backslash mathcal\; F$ satisfies the marriage condition.

}}The name "marriage theorem" came from {{Harvard citation|Halmos|Vaughan|1950}}

Suppose that each of a (possibly infinite) set of boys is acquainted with a finite set of girls. Under what conditions is it possible for each boy to marry one of his acquaintances? It is clearly necessary that every finite set of k boys be. collectively, acquainted with at least k girls... this condition is also sufficient.

File:Halls theorem positive example2.svg

;Example 1

: Consider the family $\backslash mathcal\; F=\backslash \{A\_1,A\_2,A\_3\backslash \}$ with $X=\backslash \{1,2,3,4,5\backslash \}$ and $$$$

\begin{align}

A_1&=\{1,2,3\}\\

A_2&=\{1,4,5\}\\

A_3&=\{3,5\}.\\

\end{align}

The transversal $\backslash \{1,3,5\backslash \}$ could be generated by the function that maps $A\_1$ to $1$, $A\_2$ to $5$, and $A\_3$ to $3$, or alternatively by the function that maps $A\_1$ to $3$, $A\_2$ to $1$, and $A\_3$ to $5$. There are other transversals, such as $\backslash \{1,2,3\backslash \}$ and $\backslash \{1,4,5\backslash \}$. Because this family has at least one transversal, the marriage condition is met. Every subfamily of $\backslash 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.

File:Halls theorem negartive example2.svg

;Example 2

: Consider $\backslash mathcal\; F=\backslash \{A\_1,A\_2,A\_3,A\_4\backslash \}$ with $$$$

\begin{align}

A_1&=\{2,3,4,5\}\\

A_2&=\{4,5\}\\

A_3&=\{5\}\\

A_4&=\{4\}.\\

\end{align}

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

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

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

File:Halls theorem matching graph theory2.svg

Let $G=(X,Y,E)$ be a finite bipartite graph with bipartite sets $X$ and $Y$ and edge set $E$. An $X$-perfect matching (also called an $X$-saturating matching) is a matching, a set of disjoint edges, which covers every vertex in $X$.

For a subset $W$ of $X$, let $N\_G(W)$ denote the neighborhood of $W$ in $G$, the set of all vertices in $Y$ that are adjacent to at least one element of $W$. The marriage theorem in this formulation states that there is an $X$-perfect matching if and only if for every subset $W$ of $X$: $$|W|\; \backslash leq\; |N\_G(W)|.$$ In other words, every subset $W$ of $X$ must have sufficiently many neighbors in $Y$.

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

Consider the contrapositive: if there is no $X$-perfect matching then Hall's condition must be violated for at least one $W\backslash subseteq\; X$. Let $M$ be a maximum matching, and let $u$ be any unmatched vertex in $X$. Consider all alternating paths (paths in $G$ that alternately use edges outside and inside $M$) starting from $u$. Let $W$ be the set of vertices in these paths that belong to $X$ (including $u$ itself) and let $Z$ be the set of vertices in these paths that belong to $Y$. Then every vertex in $Z$ is matched by $M$ to a vertex in $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 $M$ or not. Therefore, the size of $W$ is at least the number $|Z|$ of these matched neighbors of $Z$, plus one for the unmatched vertex $u$. That is, $|W|\backslash ge\; |Z|+1$. However, for every vertex $v\backslash in\; W$, every neighbor $w$ of $v$ belongs to $Z$: an alternating path to $w$ can be found either by removing the matched edge $vw$ from the alternating path to $v$, or by adding the unmatched edge $vw$ to the alternating path to $v$. Therefore, $Z=N\_G(W)$ and $|W|\backslash ge\; |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 $\backslash mathcal\; F$ with union $X$ can be translated into a bipartite graph $G=(\backslash mathcal\; F,X,E)$ where each edge connects a set in $\backslash mathcal\; F$ to an element of that set. An $\backslash mathcal\; F$-perfect matching in this graph defines a system of unique representatives for $\backslash mathcal\; F$. In the other direction, from any bipartite graph $G=(X,Y,E)$ one can define a finite family of sets, the family of neighborhoods of the vertices in $X$, such that any system of unique representatives for this family corresponds to an $X$-perfect matching in $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 $G=(X,Y,E)$, every vertex in $X$ should have finite degree. The degrees of the vertices in $Y$ are not constrained.

Hall's theorem can be proved (non-constructively) based on Sperner's lemma.{{Cite journal|last=Haxell|first=P.|date=2011|title=On Forming Committees|url=http://www.jstor.org/stable/10.4169/amer.math.monthly.118.09.777|journal=The American Mathematical Monthly|volume=118|issue=9|pages=777–788|doi=10.4169/amer.math.monthly.118.09.777|jstor=10.4169/amer.math.monthly.118.09.777|s2cid=27202372|issn=0002-9890}}{{Rp|Thm.4.1,4.2}}

The theorem has many applications. For example, for a standard deck of cards, dealt into 13 piles of 4 cards each, the marriage theorem implies that it is possible to select one card from each pile so that the selected cards contain exactly one card of each rank (Ace, 2, 3, ..., Queen, King). This can be done by constructing a bipartite graph with one partition containing the 13 piles and the other partition containing the 13 ranks. The remaining proof follows from the marriage condition. More generally, any regular bipartite graph has a perfect matching.{{cite web| last = DeVos |first = Matt | url = http://www.sfu.ca/~mdevos/notes/graph/345_matchings.pdf | title = Graph Theory |website = Simon Fraser University}}{{rp|2}}

More abstractly, let $G$ be a group, and $H$ be a finite index subgroup of $G$. Then the marriage theorem can be used to show that there is a set $T$ such that $T$ is a transversal for both the set of left cosets and right cosets of $H$ in $G$.{{cite journal|last1 = Button|first1 = Jack |first2= Maurice |last2 = Chiodo| first3 = Mariano |last3 = Zeron-Medina Laris|title = Coset Intersection Graphs for Groups|journal = The American Mathematical Monthly|volume = 121|issue = 10|year = 2014|pages = 922–26|doi = 10.4169/amer.math.monthly.121.10.922|arxiv = 1304.6111 |s2cid = 16417209 |quote = For $H$ a finite index subgroup of $G$, the existence of a left-right transversal is well known, sometimes presented as an application of Hall’s marriage theorem.}}

The marriage theorem is used in the usual proofs of the fact that an $r\backslash times\; n$ Latin rectangle can always be extended to an $(r+1)\backslash times\; n$ Latin rectangle when

journal = Bull. Amer. Math. Soc. |volume = 51 |year = 1945 |issue = 6|pages = 387–388|doi = 10.1090/S0002-9904-1945-08361-X|doi-access = free}}

This theorem is part of a collection of remarkably powerful theorems in combinatorics, all of which are related to each other in an informal sense in that it is more straightforward to prove one of these theorems from another of them than from first principles. These include:

• The König–Egerváry theorem (1931) (Dénes Kőnig, Jenő Egerváry)
• König's theoremThe naming of this theorem is inconsistent in the literature. There is the result concerning matchings in bipartite graphs and its interpretation as a covering of (0,1)-matrices. {{harvtxt|Hall|1986}} and {{harvtxt|van Lint|Wilson|1992}} refer to the matrix form as König's theorem, while {{harvtxt|Roberts|Tesman|2009}} refer to this version as the Kőnig-Egerváry theorem. The bipartite graph version is called Kőnig's theorem by {{harvtxt|Cameron|1994}} and {{harvtxt|Roberts|Tesman|2009}}.
• Menger's theorem (1927)
• The max-flow min-cut theorem (Ford–Fulkerson algorithm)
• The Birkhoff–Von Neumann theorem (1946)
• Dilworth's theorem.

In particular,[https://web.archive.org/web/20221027074219/http://www.robertborgersen.info/Presentations/GS-05R-1.pdf Equivalence of seven major theorems in combinatorics]{{harvnb|Reichmeider|1984}} there are simple proofs of the implications Dilworth's theorem ⇔ Hall's theorem ⇔ König–Egerváry theorem ⇔ König's theorem.

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 $\backslash mathcal\; F$.{{harvnb|Hall|1986|loc=pg. 51}} This variant extends Philip Hall's Marriage theorem.

Suppose that $\backslash mathcal\; F\; =\; \backslash \{A\_i\backslash \}\_\{i\backslash in\; I\}$, is a (possibly infinite) family of finite sets that need not be distinct, then $\backslash mathcal\; F$ has a transversal if and only if $\backslash 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 $\backslash mathcal\; F$ be the family, $A\_\{0\}=\backslash mathbb\; N$, $A\_\{i\}=\backslash \{i-1\backslash \}$ for $i\backslash geq\; 1$. The marriage condition holds for this infinite family, but no transversal can be constructed.{{harvnb|Hall|1986|loc=pg. 51}}

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.{{Cite journal|last=Aharoni|first=Ron|date=February 1984|title=König's Duality Theorem for Infinite Bipartite Graphs|journal=Journal of the London Mathematical Society|volume=s2-29|issue=1|pages=1–12|doi=10.1112/jlms/s2-29.1.1|issn=0024-6107}}

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.

A fractional matching in a graph is an assignment of non-negative weights to each edge, such that the sum of weights adjacent to each vertex is at most 1. A fractional matching is X-perfect if the sum of weights adjacent to each vertex is exactly 1. The following are equivalent for a bipartite graph G = (X+Y, E):{{Cite web|title=co.combinatorics - Fractional Matching version of Hall's Marriage theorem|url=https://mathoverflow.net/questions/271939/fractional-matching-version-of-halls-marriage-theorem|access-date=2020-06-29|website=MathOverflow}}

• G admits an X-perfect matching.
• G admits an X-perfect fractional matching. The implication follows directly from the fact that X-perfect matching is a special case of an X-perfect fractional matching, in which each weight is either 1 (if the edge is in the matching) or 0 (if it is not).
• G satisfies Hall's marriage condition. The implication holds because, for each subset W of X, the sum of weights near vertices of W is |W|, so the edges adjacent to them are necessarily adjacent to at least |W| vertices of Y.

{{main|Deficiency (graph theory)}}

When Hall's condition does not hold, the original theorem tells us only that a perfect matching does not exist, but does not tell what is the largest matching that does exist. To learn this information, we need the notion of deficiency of a graph. Given a bipartite graph G = (X+Y, E), the deficiency of G w.r.t. X is the maximum, over all subsets W of X, of the difference |W| - |N_G(W)|. The larger is the deficiency, the farther is the graph from satisfying Hall's condition.

Using Hall's marriage theorem, it can be proved that, if the deficiency of a bipartite graph G is d, then G admits a matching of size at least |X|-d.

• A characterization of perfect matchings in general graphs (that are not necessarily bipartite) is provided by the Tutte theorem.
• A generalization of Hall's theorem to bipartite hypergraphs is provided by various Hall-type theorems for hypergraphs.

• {{Citation|first=Richard A.|last=Brualdi|title=Introductory Combinatorics|publisher=Prentice-Hall/Pearson|place=Upper Saddle River, NJ|year=2010|isbn=978-0-13-602040-0}}
• {{Citation|first=Peter J.|last=Cameron|title=Combinatorics: Topics, Techniques, Algorithms|publisher= Cambridge University Press|place=Cambridge|year=1994|isbn=978-0-521-45761-3}}
• {{Citation|last=Hall|first=Marshall Jr.|title=Combinatorial Theory|edition=2nd|publisher=John Wiley & Sons|place=New York|year=1986|isbn=978-0-471-09138-7}}
• {{Citation | last1=Hall | first1=Philip | author1-link=Philip Hall | title=On Representatives of Subsets | doi=10.1112/jlms/s1-10.37.26 | year=1935 | journal=J. London Math. Soc. | volume=10 | issue=1 | pages=26–30}}
• {{citation | last1 = Halmos | first1 = Paul R. | author1-link = Paul Halmos | last2 = Vaughan | first2 = Herbert E. | doi = 10.2307/2372148 | journal = American Journal of Mathematics | mr = 0033330 | pages = 214–215 | title = The marriage problem | volume = 72 | issue = 1 | year = 1950| jstor = 2372148 }}
• {{Citation|last=Reichmeider|first=P.F.|title=The Equivalence of Some Combinatorial Matching Theorems|publisher=Polygonal Publishing House|year=1984|isbn=978-0-936428-09-3}}
• {{Citation|last1=Roberts|first1=Fred S.|last2=Tesman|first2=Barry|title=Applied Combinatorics|edition=2nd|publisher=CRC Press|place=Boca Raton|year=2009|isbn=978-1-4200-9982-9}}
• {{Citation|last1=van Lint|first1=J. H.|last2=Wilson|first2=R.M.|title=A Course in Combinatorics|publisher=Cambridge University Press|place=Cambridge|year=1992|isbn=978-0-521-42260-4}}

• [http://www.cut-the-knot.org/arithmetic/elegant.shtml Marriage Theorem] at cut-the-knot
• [http://www.cut-the-knot.org/arithmetic/marriage.shtml Marriage Theorem and Algorithm] at cut-the-knot
• [http://luckytoilet.wordpress.com/2013/12/21/halls-marriage-theorem-explained-intuitively/ Hall's marriage theorem explained intuitively] at Lucky's notes.

{{PlanetMath attribution|id=3059|title=proof of Hall's marriage theorem}}

Category:Matching (graph theory)

Category:Theorems in combinatorics

Category:Theorems in graph theory

Category:Articles containing proofs