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?

About twenty years ago I became interested in

exactly this question! I asked several people who knew group theory better than me.

All of them knew the fact, but none of them knew any interesting group-theoretic applications of it.

A few of them asked other group theorists, but no one could remember seeing any application.

Since then, in my lectures I call Hall’s result

“The most beautiful useless theorem”, and encourage students to find applications.

I hope some of the readers of this blog can suggest one.

Did Hall have a use for it? Does anyone know?

I do not know whether Ph. Hall used this result for something else.

Does this mean there is a theorem out there which could be called “The Hall^2 Marriage Theorem”?

A more serious comment (at least, more serious i intent): you say that M. Hall’s extension of P. Hall’s theorem covers the case where |H| is finite but |G:H| might be infinite. What if |G:H| is assumed finite but |H| might be infinite?

Good question, and in fact I can answer it!

If H has finite index in G, then G acts as a permutation group on the cosets of H; the image of this homomorphism is a normal subgroup N of finite index in G and contained in G. So apply Hall’s theorem to G/N to find the simultaneous representatives.

Hall’s marriage theorem itself fails if the sets are not required to be finite. For a simple example, take the following subsets of the natural numbers: B_0={1,2,3,…} and B_i={i} for i>0.

I’m not sure that the result on coset representatives really was the motivation for Hall’s work on the Marriage Theorem. Mark Wildon and I looked into this question some years ago when we couldn’t find any reference to it in Hall’s published work. The claim is made in his obituary by Green, Roseblade and Thompson; we asked John Thompson about it, and he said it was folklore, and possibly false.

The coset representatives result had already appeared in print at least twice before Hall’s Marriage Theorem was published: Miller proved it using double cosets in 1910 (a very straightforward, purely group-theoretic argument: one simply observes that within a double coset, each left coset intersects non-trivially with each right coset). And Van der Waerden mentioned it in 1927, as an application of a combinatorial theorem quite similar to the Marriage Theorem.

The double coset proof also extends naturally to the infinite case, by the way, since inversion gives a bijection between the left and right cosets within a double coset.

Sorry, my claim that inversion gives a bijection between left and right cosets in a double coset is wrong: a double coset generally isn’t closed under inversion. (But it’s easy to show the necessary bijection between left and right cosets exists, provided the subgroup has finite order or finite index.)

Thanks John.

I can’t help feeling that there should be an application, maybe in quasigroup theory?

One area of group theory where Hall’s marriage theorem has proven to be quite useful is in studying amenability. In order to show that non-amenable groups admit paradoxical actions (i.e. one’s where you can perform a Banach-Tarski like Paradox) you need to use Hall’s marriage theorem.

Another, much more recent, application of Hall’s Marriage theorem to amenability came in the construction of so called multi-tilings of groups . Downarowicz, Huczek, and Zhang use Hall’s marriage theorem crucially to construct Folner multi-tilings of Amenable groups.

Do these applications actually use the fact about simultaneous left and right coset representatives?

Just the original theorem.