Hall's marriage theorem
In mathematics, Hall's marriage theorem, proved by Philip Hall (1935), is a theorem with two equivalent formulations:
- The combinatorial formulation deals with a collection of finite sets. It gives a necessary and sufficient condition for being able to select a distinct element from each set.
- The graph theoretic formulation deals with a bipartite graph. It gives a necessary and sufficient condition for finding a matching that covers at least one side of the graph.
Combinatorial formulation[]
Let be a (possibly infinite) family of finite subsets of , where the members of are counted with multiplicity (That is, may contain the same set several times).[1]
A transversal for is the image of an injective function from to such that is an element of the set for every in the family . In other words, selects one representative from each set in in such a way that no two of these representatives are equal. An alternative term for transversal is system of distinct representatives.
The collection S satisfies the marriage condition when for each subfamily ,
Restated in words, the marriage condition asserts that every subfamily of contains at least as many distinct members as the number of sets in the subfamily.
If the marriage condition fails then there cannot be a transversal of .
Proof
|
---|
Suppose that the marriage condition fails, i.e., that for some subcollection of , Suppose, by way of contradiction, that a transversal of also exists. The restriction of to the offending subcollection would be an injective function from into . This is impossible by the pigeonhole principle since . Therefore no transversal can exist if the marriage condition fails. |
Hall's theorem states that the converse is also true:
Hall's Marriage Theorem — A family S of finite sets has a transversal if and only if S satisfies the marriage condition.
Examples[]
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/c2/Halls_theorem_positive_example2.svg/280px-Halls_theorem_positive_example2.svg.png)
Example 1: Consider S = {A1, A2, A3} with
- A1 = {1, 2, 3}
- A2 = {1, 4, 5}
- A3 = {3, 5}.
A valid transversal would be (1, 4, 5). (Note this is not unique: (2, 1, 3) works equally well, for example.)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d5/Halls_theorem_negartive_example2.svg/280px-Halls_theorem_negartive_example2.svg.png)
Example 2: Consider S = {A1, A2, A3, A4} with
- A1 = {2, 3, 4, 5}
- A2 = {4, 5}
- A3 = {5}
- A4 = {4}.
No valid transversal exists; the marriage condition is violated as is shown by the subfamily W = {A2, A3, A4}. Here the number of sets in the subfamily is |W| = 3, while the union of the three sets A2 U A3 U A4 contains only 2 elements of X.
Example 3: Consider S = {A1, A2, A3, A4} with
- A1 = {a, b, c}
- A2 = {b, d}
- A3 = {a, b, d}
- A4 = {b, d}.
The only valid transversals are (c, b, a, d) and (c, d, a, b).
Application to marriage[]
The standard example[citation needed] of an application of the marriage theorem is to imagine two groups; one of n men, and one of n women. For each woman, there is a subset of the men, any one of which she would happily marry; and any man would be happy to marry a woman who wants to marry him. Consider whether it is possible to pair up (in marriage) the men and women so that every person is happy.
If we let Ai be the set of men that the i-th woman would be happy to marry, then the marriage theorem states that each woman can happily marry a unique man if and only if for any subset of the women, the number of men whom at least one of these women would be happy to marry, , is at least as big as the number of women in that subset, .
This condition is necessary, as if it does not hold, there are not enough men to share among the women. What is interesting is that it is also a sufficient condition.
Graph theoretic formulation[]
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a7/Halls_theorem_matching_graph_theory2.svg/220px-Halls_theorem_matching_graph_theory2.svg.png)
Let G be a finite bipartite graph with bipartite sets X and Y (i.e. G := (X + Y, E)). An X-perfect matching (also called: X-saturating matching) is a matching which covers every vertex in X.
For a subset W of X, let NG(W) denote the neighborhood of W in G, i.e., the set of all vertices in Y adjacent to some 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:
In other words: every subset W of X has sufficiently many adjacent vertices in Y.
Proof of the graph theoretic version[]
Easy direction: we assume that some matching M saturates every vertex of X, and prove that Hall's condition is satisfied for all W ⊆ X. Let M(W) denote the set of all vertices in Y matched by M to a given W. By definition of a matching, |M(W)| = |W |. But M(W) ⊆ NG(W), since all elements of M(W) are neighbours of W. So, |NG(W)| ≥ |M(W)| and hence, |NG(W)| ≥ |W|.
Hard direction: we assume that there is no X-perfect matching and prove that Hall's condition is violated for at least one W ⊆ X. Let M be a maximum matching, and let u be a vertex of X not saturated by M. Consider all alternating paths (i.e., paths in G alternately using edges outside and inside M) starting from u. Let the set of all points in Y connected to u by these alternating paths be Z, and the set of all points in X connected to u by these alternating paths (including u itself) be W. No maximal alternating path can end in a vertex in Y, lest it would be an augmenting path, so that we could augment M to a strictly larger matching by toggling the status (belongs to M or not) of all the edges of the path. Thus every vertex in Z is matched by M to a vertex in W \ {u}. Conversely, every vertex v in W \ {u} is matched by M to a vertex in Z (namely, the vertex preceding v on an alternating path ending at v). Thus, M provides a bijection of W \ {u} and Z, which implies |W| = |Z| + 1. On the other hand, NG(W) ⊆ Z. Indeed, let v in NG(W) be connected to a vertex w in W. If the edge (w,v) is in M, then v precedes w in any alternating path that goes from u to w. If the edge (w,v) is not in M, then one can use it to extend any alternating path that goes from u to w. In either case, v is visited by some alternating path issued from u. Hence NG(W) ⊆ Z, and so |NG(W)| ≤ |Z| = |W| − 1 < |W|.
Constructive proof of the hard direction[]
Define a Hall violator as a subset W of X for which |NG(W)| < |W|. If W is a Hall violator, then there is no matching that saturates all vertices of W. Therefore, there is also no matching that saturates X. Hall's marriage theorem says that a graph contains an X-perfect matching if and only if it contains no Hall violators. The following algorithm proves the hard direction of the theorem: it finds either an X-perfect matching or a Hall violator. It uses, as a subroutine, an algorithm that, given a matching M and an unmatched vertex x0, either finds an M-augmenting path or a Hall violator containing x0.
It uses
- Initialize M := {}. // Empty matching.
- Assert: M is a matching in G.
- If M saturates all vertices of X, then return the X-perfect matching M.
- Let x0 be an unmatched vertex (a vertex in X \ V(M)).
- Using the Hall violator algorithm, find either a Hall violator or an M-augmenting path.
- In the first case, return the Hall violator.
- In the second case, use the M-augmenting path to increase the size of M (by one edge), and go back to step 2.
At each iteration, M grows by one edge. Hence, this algorithm must end after at most |E| iterations. Each iteration takes at most |X| time. The total runtime complexity is similar to the Ford-Fulkerson method for finding a maximum cardinality matching.
Equivalence of the combinatorial formulation and the graph-theoretic formulation[]
Let S = (A1, A2, ..., An) where the Ai are finite sets which need not be distinct. Let the set X = {A1, A2, ..., An} (that is, the set of names of the elements of S) and the set Y be the union of all the elements in all the Ai.
We form a finite bipartite graph G := (X + Y, E), with bipartite sets X and Y by joining any element in Y to each Ai which it is a member of. A transversal of S is an X-perfect matching (a matching which covers every vertex in X) of the bipartite graph G. Thus a problem in the combinatorial formulation can be easily translated to a problem in the graph-theoretic formulation.
Topological proof[]
Hall's theorem can be proved (non-constructively) based on Sperner's lemma.[2]: Thm.4.1, 4.2
Applications[]
The theorem has many other interesting "non-marital" applications. For example, take a standard deck of cards, and deal them out into 13 piles of 4 cards each. Then, using the marriage theorem, we can show that it is always possible to select exactly 1 card from each pile, such that the 13 selected cards contain exactly one card of each rank (Ace, 2, 3, ..., Queen, King). More generally, any regular bipartite graph has a perfect matching.[3]: 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.[4]
The marriage theorem is used in the usual proofs of the fact that an (r × n) Latin rectangle can always be extended to an ((r +1) × n) Latin rectangle when r < n, and so, ultimately to a Latin square.[5]
Logical equivalences[]
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 theorem[6]
- Menger's theorem (1927)
- The max-flow min-cut theorem (Ford–Fulkerson algorithm)
- The Birkhoff–Von Neumann theorem (1946)
- Dilworth's theorem.
In particular,[7][8] there are simple proofs of the implications Dilworth's theorem ⇔ Hall's theorem ⇔ König–Egerváry theorem ⇔ König's theorem.
Infinite families[]
Marshall Hall Jr. variant[]
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 S.[9] This variant refines the marriage theorem and provides a lower bound on the number of transversals that a given S may have. This variant is:[10]
Suppose that (A1, A2, ..., An), where the Ai are finite sets that need not be distinct, is a family of sets satisfying the marriage condition, and suppose that |Ai| ≥ r for i = 1, ..., n. Then the number of different transversals for the family is at least r! if r ≤ n and r(r − 1) ... (r − n + 1) if r > n.
Recall that a transversal for a family S is an ordered sequence, so two different transversals could have exactly the same elements. For instance, the family A1 = {1, 2, 3}, A2 = {1, 2, 5} has both (1, 2) and (2, 1) as distinct transversals.
Marriage condition does not extend[]
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 S be the family, A0 = {1, 2, 3, ...}, A1 = {1}, A2 = {2}, ..., Ai = {i }, ...
The marriage condition holds for this infinite family, but no transversal can be constructed.[11]
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.
The marriage theorem does extend to the infinite case if stated properly. 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]
Fractional matching variant[]
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):[13]
- 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.
Quantitative variant[]
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| - |NG(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.
Generalizations[]
- A generalization of Hall's theorem to 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.
Notes[]
- ^ Hall, Jr. 1986, pg. 51. It is also possible to have infinite sets in the family, but the number of sets in the family must then be finite, counted with multiplicity. Only the situation of having an infinite number of sets while allowing infinite sets is not allowed.
- ^ Haxell, P. (2011). "On Forming Committees". The American Mathematical Monthly. 118 (9): 777–788. doi:10.4169/amer.math.monthly.118.09.777. ISSN 0002-9890.
- ^ DeVos, Matt. "Graph Theory" (PDF). Simon Fraser University.
- ^ Button, Jack; Chiodo, Maurice; Zeron-Medina Laris, Mariano (2014). "Coset Intersection Graphs for Groups". The American Mathematical Monthly. 121 (10): 922–26. doi:10.4169/amer.math.monthly.121.10.922.
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.
- ^ Hall, Marshall (1945). "An existence theorem for latin squares". Bull. Amer. Math. Soc. 51: 387–388. doi:10.1090/S0002-9904-1945-08361-X.
- ^ The 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. Hall, Jr. (1986) and van Lint & Wilson (1992) refer to the matrix form as König's theorem, while 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 Cameron (1994) and Roberts & Tesman (2009).
- ^ Equivalence of seven major theorems in combinatorics
- ^ Reichmeider 1984
- ^ Hall, Jr. 1986, pg. 51
- ^ Cameron 1994, pg.90
- ^ Hall, Jr. 1986, pg. 51
- ^ Aharoni, Ron (February 1984). "König's Duality Theorem for Infinite Bipartite Graphs". Journal of the London Mathematical Society. s2-29 (1): 1–12. doi:10.1112/jlms/s2-29.1.1. ISSN 0024-6107.
- ^ "co.combinatorics - Fractional Matching version of Hall's Marriage theorem". MathOverflow. Retrieved 2020-06-29.
References[]
- Brualdi, Richard A. (2010), Introductory Combinatorics, Upper Saddle River, NJ: Prentice-Hall/Pearson, ISBN 978-0-13-602040-0
- Cameron, Peter J. (1994), Combinatorics: Topics, Techniques, Algorithms, Cambridge: Cambridge University Press, ISBN 978-0-521-45761-3
- Dongchen, Jiang; Nipkow, Tobias (2010), "Hall's Marriage Theorem", The Archive of Formal Proofs, ISSN 2150-914X. Computer-checked proof.
{{citation}}
: CS1 maint: postscript (link) - Hall, Jr., Marshall (1986), Combinatorial Theory (2nd ed.), New York: John Wiley & Sons, ISBN 978-0-471-09138-7
- Hall, Philip (1935), "On Representatives of Subsets", J. London Math. Soc., 10 (1): 26–30, doi:10.1112/jlms/s1-10.37.26
- Halmos, Paul R.; Vaughan, Herbert E. (1950), "The marriage problem", American Journal of Mathematics, 72 (1): 214–215, doi:10.2307/2372148, JSTOR 2372148, MR 0033330
- Reichmeider, P.F. (1984), The Equivalence of Some Combinatorial Matching Theorems, Polygonal Publishing House, ISBN 978-0-936428-09-3
- Roberts, Fred S.; Tesman, Barry (2009), Applied Combinatorics (2nd ed.), Boca Raton: CRC Press, ISBN 978-1-4200-9982-9
- van Lint, J. H.; Wilson, R.M. (1992), A Course in Combinatorics, Cambridge: Cambridge University Press, ISBN 978-0-521-42260-4
External links[]
- Marriage Theorem at cut-the-knot
- Marriage Theorem and Algorithm at cut-the-knot
- Hall's marriage theorem explained intuitively at Lucky's notes.
This article incorporates material from proof of Hall's marriage theorem on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.
- Matching (graph theory)
- Theorems in combinatorics
- Theorems in graph theory