Theorem 34: Hall’s marriage theorem

I was recently given a box of chocolates.  This was a very nice surprise, but closer inspection revealed that I don’t like all of the flavours in the box.  There were twelve chocolates, and I like six of them.  I thought that perhaps I could invite some other people to share the chocolates with me, hoping that they’d take the ones I don’t like.  Naturally, if I do that I have to make sure that everyone gets one chocolate each, to be fair.  But I expect that some of them will like only certain chocolates too.  So I thought that I’d ask eleven people which of these chocolates they like.  That would give me twelve lists of acceptable chocolates (including my own).  But will I be able to assign chocolates to people so that everybody gets a chocolate they like?  If not, I’ll have to revise my guest list.

Well, I could try assigning theoretical chocolates to people in advance, to check.  But that sounds terribly time-consuming.  Is there some easy way in which I could tell whether it will be possible?  Are there any circumstances in which I could immediately tell that it would be impossible?

Here’s a scenario in which it’s obviously impossible.  Twelve people, twelve chocolates.  So no spares (on either side).  So if everybody tells me that, like me, they don’t like Scotch whisky chocolates, we’re going to have a problem: there’ll be twelve people fighting over the other eleven chocolates.  I should uninvite one person, and find someone who likes whisky in their chocolate.

Can I say more?  Well, we could extend the above idea.  I only like six of the chocolates.  If there are six other people who also only like those same six chocolates, we’re going to have a disagreement: seven people, six chocolates.  Disaster!

Hopefully you’re starting to get the idea.  Let’s be a bit more general.  For any collection of k people, I need to know that they (between them) like at least k different chocolates, don’t I?

So we have a necessary condition: any collection of k people must like at least k different chocolates.  If that condition isn’t satisfied, then I’m not going to be able to share the chocolates to everyone’s satisfaction.  Is that also a sufficient condition?  That is, if we know that condition is satisfied, can we be sure that I can share the chocolates, or might there be some other problem?

This week’s theorem tells us that this is both a necessary and a sufficient condition.

Theorem (Hall) I can match chocolates to people so that everyone gets a chocolate they like if, and only if, for each k (between 1 and 12), each possible group of k people likes at least k different chocolates between them.

OK, Hall did not write about chocolates.  I’ve usually come across this theorem in graph theory, where it talks about finding matchings in bipartite graphs, and where it’s usually phrased in terms of marrying men and women (which is why it’s called Hall’s marriage theorem).  But it can also be phrased in the language of group theory (in a way that Wikipedia seems to make particularly hard to understand).

It’s one of those theorems where one direction is pretty easy (it didn’t take us long to prove that the condition was necessary), but the other direction takes a bit more work (it’s certainly not obvious that the condition is sufficient).  I wrote about this phenomenon in Theorem 1 on this blog (for example).  I think it’s pretty interesting that the condition is indeed sufficient here, because it really isn’t obvious. 

I think I’m going to skip the proof here.  There are various ways of proving the result, including induction (which is the proof that the Wikipedia page describes).  You should be able to find a proof in a graph theory textbook, or just try searching online (or try to prove it for yourself!).  There are some very nice proofs, and they’re not terribly difficult.

Where next?  It turns out that it’s possible to generalise this result.  For example, what would happen if I decided to invite just five people, so that we each get two chocolates?  What would the necessary and sufficient condition be then?  (You might think of this as the polygamous version of Hall’s theorem!)  I’ll leave this as a nice exercise for you.

Of course, I have no intention of allocating chocolates in this way.  I intend to eat the ones that I like, and then pass the rest on to some lucky person (who may or may not like Scotch whisky and Earl Grey tea chocolates).  But that doesn’t make for a good blog post!


4 Responses to “Theorem 34: Hall’s marriage theorem”

  1. Ashley Says:

    hey, nice blog…really like it and added to bookmarks. keep up with good work

  2. Theorem 37: Sperner’s lemma « Theorem of the week Says:

    […] been a bit vague here.  The only key idea that I haven’t mentioned, though, is the use of Hall’s marriage theorem to show that it’s possible to do the `joining’ I’ve […]

  3. unknown Says:

    Thanks a lot for avoiding the term marriage or matching men an women! At least I could finally understand the idea of this theorem without getting my head on anoying analogies.

  4. spotsnz Says:

    I love this post. You have a good sense of humour. 🙂

Leave a Reply

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

You are commenting using your 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

%d bloggers like this: