Hall’s Marriage Theorem

Philip Hall was one of the greatest group theorists of the twentieth century. But it may well be that he is known to more people for a result which on the face of it is pure combinatorics, with nothing to do with group theory: Hall’s Marriage Theorem.

In the story form in which it is usually told, it goes like this. Let g₁,…,g_n be girls. Suppose that each girl g_i has a list B_i of boys she would be prepared to marry. Then a necessary and sufficient condition for it to be possible that all the girls marry boys from their list is that, given any set of k girls, their lists contain at least k boys altogether.

Said more formally, if B₁,…,B_n are finite sets, a system of distinct representatives or SDR for these sets consists of n elements b₁,…,b_n such that

• they are representatives of the sets, that is, b_i belongs to B_i for all i;
• and they are distinct, that is, b_i ≠ b_j for i ≠ j.

Then Hall’s theorem says that a necessary and sufficient condition for the sets to have an SDR is that the union of any k of them has cardinality at least k.

A moment’s thought shows that the condition is necessary; if the lists of k girls don’t contain at least k boys, then these girls cannot be married to boys on their lists. The proof that the condition is sufficient, that is, guarantees that the marriage arrangement is possible, is more difficult, but several very different proofs are known.

My purpose here is not to expound the proof, but to explain why a group theorist should be interested in this.

Let G be a finite group and H a subgroup of G. As you will know if you have done group theory up to Lagrange’s theorem, the right cosets of H in G (the sets Hg = {hg:h∈H}) are pairwise non-overlapping and cover G. Moreover, each coset has the same number of elements as H, since the map from H to Hg taking h to hg for all h∈H is a bijection.

If g₁,…g_n are elements such that the right cosets Hg₁,…Hg_n are distinct and cover the whole of G, we call these elements right coset representatives.

Similar statements hold for the left cosets, the sets gH = {gh:h∈H}. And from Lagrange’s Theorem, it follows that the numbers of left and right cosets are equal.

But in fact there is a much more elementary proof that these numbers are equal, which works equally well if G, H, or the number of cosets is infinite. Can you find it?

What Hall was after was the following statement:

Let H be a subgroup of the finite group G, with n cosets. Then there are elements g₁,…g_n of G which are simultaneously right and left coset representatives.

To see how this follows from Hall’s marriage theorem, we argue like this. Let x₁,…x_n be right coset representatives, and y₁,…y_n be left coset representatives. For each i∈{1,…,n}, let B_i be the set of indices j for which the left coset y_jH has non-empty intersection with the right coset Hx_i.

Now we claim that these sets of indices satisfy Hall’s condition for the existence of an SDR.

Let I be any set of indices, and let J be the set of all j belonging to the union of the B_i for i∈I. This means that the union of the right cosets Hx_i for i∈I is contained in the union of the left cosets y_jH for j∈J. Since all cosets have the same size, this entails I ≤ J, as required.

So, by Hall’s marriage theorem, there exists an SDR for the sets B₁,…B_n, that is, n distinct elements b_i where b_i∈B_i. This means that the intersection of the right coset Hx_i and the left coset y_biH is non-empty. Take an element g_i in this intersection. Then g₁,…g_n are both left and right coset representatives for H in G.

This is not the end of the story. Marshall Hall Jr. (another great 20th century mathematician who gave us textbooks on both group theory and combinatorics) extended Hall’s marriage theorem to the case where we have an infinite number of finite sets (that is, an infinite number of girls, but each has only finitely many boys on her list).

Using this, it is easy to see that Philip Hall’s observation about simultaneous left and right coset representatives holds also when the group G is infinite, provided that the subgroup H is finite.

As far as I can recall (and I admit my memory might be wrong), I have never actually used this nice result for anything; but I have always felt that there should be an application of it. Any thoughts?