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 g1,…,gn be girls. Suppose that each girl gi has a list Bi 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 B1,…,Bn are finite sets, a system of distinct representatives or SDR for these sets consists of n elements b1,…,bn such that

  • they are representatives of the sets, that is, bi belongs to Bi for all i;
  • and they are distinct, that is, bi ≠ bj 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:hH}) 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 hH is a bijection.

If g1,…gn are elements such that the right cosets Hg1,…Hgn 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:hH}. 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 g1,…gn 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 x1,…xn be right coset representatives, and y1,…yn be left coset representatives. For each i∈{1,…,n}, let Bi be the set of indices j for which the left coset yjH has non-empty intersection with the right coset Hxi.

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 Bi for iI. This means that the union of the right cosets Hxi for iI is contained in the union of the left cosets yjH for jJ. 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 B1,…Bn, that is, n distinct elements bi where biBi. This means that the intersection of the right coset Hxi and the left coset ybiH is non-empty. Take an element gi in this intersection. Then g1,…gn 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?

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition and tagged , , , , . Bookmark the permalink.

13 Responses to Hall’s Marriage Theorem

  1. Felix Lazebnik says:

    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.

  2. Yemon Choi says:

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

  3. Yemon Choi says:

    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.

  4. jbritnell2013 says:

    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.

    • jbritnell2013 says:

      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.

      • jbritnell2013 says:

        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?

  5. Josh Frisch says:

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.