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*_{1},…,*g _{n}* be girls. Suppose that each girl

*g*has a list

_{i}*B*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

_{i}*k*girls, their lists contain at least

*k*boys altogether.

Said more formally, if *B*_{1},…,*B _{n}* are finite sets, a

*system of distinct representatives*or SDR for these sets consists of

*n*elements

*b*

_{1},…,

*b*such that

_{n}- they are
*representatives*of the sets, that is,*b*belongs to_{i}*B*for all_{i}*i*; - and they are
*distinct*, that is,*b*≠_{i}*b*for_{j}*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*_{1},…*g _{n}* are elements such that the right cosets

*Hg*

_{1},…

*Hg*are distinct and cover the whole of

_{n}*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*_{1},…*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*_{1},…*x _{n}* be right coset representatives, and

*y*

_{1},…

*y*be left coset representatives. For each

_{n}*i*∈{1,…,

*n*}, let

*B*be the set of indices

_{i}*j*for which the left coset

*y*has non-empty intersection with the right coset

_{j}H*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*for

_{i}*i*∈

*I*is contained in the union of the left cosets

*y*for

_{j}H*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*_{1},…*B _{n}*, that is,

*n*distinct elements

*b*where

_{i}*b*∈

_{i}*B*. This means that the intersection of the right coset

_{i}*Hx*and the left coset

_{i}*y*is non-empty. Take an element

_{bi}H*g*in this intersection. Then

_{i}*g*

_{1},…

*g*are both left and right coset representatives for

_{n}*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?