Hall's marriage theorem

example 1, marriage condition met

Example 1: Consider S = {A₁, A₂, A₃} with

A₁ = {1, 2, 3}

A₂ = {1, 4, 5}

A₃ = {3, 5}.

A valid transversal would be (1, 4, 5). (Note this is not unique: (2, 1, 3) works equally well, for example.)

example 2, marriage condition violated

Example 2: Consider S = {A₁, A₂, A₃, A₄} with

A₁ = {2, 3, 4, 5}

A₂ = {4, 5}

A₃ = {5}

A₄ = {4}.

No valid transversal exists; the marriage condition is violated as is shown by the subfamily W = {A₂, A₃, A₄}. Here the number of sets in the subfamily is |W| = 3, while the union of the three sets A₂ U A₃ U A₄ contains only 2 elements of X.

Example 3: Consider S = {A₁, A₂, A₃, A₄} with

A₁ = {a, b, c}

A₂ = {b, d}

A₃ = {a, b, d}

A₄ = {b, d}.

The only valid transversals are (c, b, a, d) and (c, d, a, b).

The standard example 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 A_i 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 man if and only if the collection of sets {A_i} meets the marriage condition.

Note that the marriage condition is that, for any subset ${\displaystyle I}$ of the women, the number of men whom at least one of the women would be happy to marry, ${\displaystyle |\bigcup _{i\in I}A_{i}|}$, be at least as big as the number of women in that subset, ${\displaystyle |I|}$. It is obvious that this condition is necessary, as if it does not hold, there are not enough men to share among the ${\displaystyle I}$ women. What is interesting is that it is also a sufficient condition.

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) ⊆ N_G(W), since all elements of M(W) are neighbours of W. So, |N_G(W)| ≥ |M(W)| and hence, |N_G(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 u a vertex 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, N_G(W) ⊆ Z: let v in Y be connected to a vertex w in W. The edge (w,v) must be in M, otherwise u reaches w via an alternating path not containing v, and we could take this alternating path ending in w and extend it with v, getting an augmenting path (which would again contradict the maximality of M). Hence v must be in Z, and so |N_G(W)| ≤ |Z| = |W| − 1 < |W|.

Define a Hall violator as a subset W of X for which |N_G(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 x₀, either finds an M-augmenting path or a Hall violator containing x₀.

It uses

1. Initialize M := {}. // Empty matching.
2. Assert: M is a matching in G.
3. If M saturates all vertices of X, then return the X-perfect matching M.
4. Let x₀ be an unmatched vertex (a vertex in X \ V(M)).
5. Using the Hall violator algorithm, find either a Hall violator or an M-augmenting path.
6. In the first case, return the Hall violator.
7. 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.

Let S = (A₁, A₂, ..., A_n) where the A_i are finite sets which need not be distinct. Let the set X = {A₁, A₂, ..., A_n} (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 A_i.

We form a finite bipartite graph G := (X + Y, E), with bipartite sets X and Y by joining any element in Y to each A_i 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.

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.[6] 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:[7]

Suppose that (A₁, A₂, ..., A_n), where the A_i are finite sets that need not be distinct, is a family of sets satisfying the marriage condition, and suppose that |A_i| ≥ 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 A₁ = {1, 2, 3}, A₂ = {1, 2, 5} has both (1, 2) and (2, 1) as distinct transversals.

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, A₀ = {1, 2, 3, ...}, A₁ = {1}, A₂ = {2}, ..., A_i = {i }, ...

The marriage condition holds for this infinite family, but no transversal can be constructed.[8]

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.[9]