Hall’s Marriage Theorem explained intuitively

Imagine that you have 4 students looking for a job, and 4 positions available to fill. Not all students are equal — some are smarter than others. So the companies want to hire only the smartest students.

(Students are happy with any job they can get)

In this diagram, a bipartite graph, the students are at the top and the companies are at the bottom. A student and a company is connected if the company wants to hire the student. For example, Costco will hire any student, so Costco is connected to Andrei, Bill, Corki, and Danny.

Hall’s Theorem, formally

Hall’s Theorem tells us when we can have the perfect matching:

Suppose G is a bipartite graph with bipartition (A,B). There is a matching that covers A if and only if for every subset X \subseteq A, N(X) \geq |X| where N(X) is the number of neighbors of X.

Huh what?

Hall’s Theorem, intuitively

If you look closely at the diagram, you’ll notice that it doesn’t quite work:

Both Blizzard and Google want to hire Corki and only Corki. But Corki can only work for one company! So the whole thing collapses; the matching fails.

Let’s rewrite Hall’s condition in the context of students and jobs:

For a set of n companies, denote m to mean the number of students that at least one of these companies want. If m \geq n for every set of companies, then a matching is possible. Otherwise, the matching fails.

Here, a set of {Blizzard, Google} consists of 2 companies, but only one student, Corki, is wanted by either company. Since 1 < 2, the matching fails.

Suppose we tell this to Blizzard’s hiring manager, who decides he’ll hire Andrei instead:

Then the matching is successful and every student gets a job. Yay!

Notice that in this example, there are 4 students and 4 jobs. In general, these numbers don’t need to be equal. If we have 10 students and 4 jobs, and we want to fill every job, we can still use Hall’s Theorem. (of course, not every student will get a job)

I like this theorem because it seems so simple. The matching can fail in an obvious way. But if it doesn’t fail in this obvious way, then there’s no way it can fail in a less obvious way — it can’t fail at all.

Application: Putnam 2012 Problem B3

Let’s apply our knowledge to a harder problem. Actually, this problem becomes quite easy if we know to use Hall’s Theorem:

Suppose 2m teams play in a round-robin tournament. Over a period of 2m-1 days, every team plays every other team exactly once. There are no ties.

Show that for each day we can select a winning team, without selecting the same team twice.

Hint: we can view the teams as one half of the bipartite graph, and the days as the other half. A team is connected to a day if it won its match that day.

Solution

That’s the hint. Here’s a more detailed solution.

We want to find a matching that covers all the days. Suppose, for contradiction, that this is impossible.

From Hall’s Theorem, there has to be a set of n days, in which there are fewer than n winners in these n days.

Let’s call a team a “loser” if it lost every single game in these n days:

So this poor loser team has lost to n different teams in these n days.

But wait! If it has lost to n teams, then these n teams are winners! Yet we just stated that there are less than n winners. Contradiction — QED.

6 Responses to Hall’s Marriage Theorem explained intuitively

  1. […] Hall’s Marriage Theorem explained intuitively (luckytoilet.wordpress.com) […]

  2. Sorry for the mess. Please remove my two last comments.

    I do not understand your solution to the Putnam problem.

    First, since in every single day there are n winners, it is obvious that in every set of k days the total number of winners is at least n. Hence, if k < = n the total number of winners in k days is at least k,

    BUT, Hall’s condition requires that in every set of k days, the total number of winners is at least k, even when k > n! You didn’t prove this.

    • luckytoilet says:

      Your argument only works for small k: you’ve correctly pointed out that when k > n your argument breaks down.

      Re-read the part about the existence of a “loser”. Choose k > n and there are 2 cases. If there is no loser, you are done (since every team is covered).

      So assume there is a loser, he loses to k different teams. So these k teams form a set of size k.

  3. You write in the proof: “Suppose, for contradiction, that a matching is impossible. From Hall’s Theorem, there has to be a set of *n* days, in which there are fewer than *n* winners in these *n* days.”

    I think this is incorrect. From Hall’s theorem, if there is no matching, then there has to be a set of *k* days in which there are fewer than *k* winners. But k doesn’t have to be n! k can be any number from 1 to the number of nodes, which in this case is 2n-1!

    I.e., it is possible that *all* sets of n days have n winners, but still there is no matching because there is another set, larger than n, that violates Hall’s condition.

    • luckytoilet says:

      Ah I see your confusion, I accidently used the same variable twice — oops. The 2n and 2n-1 in the problem statement has nothing to do with the variable in the solution, I’ll change it to 2m and 2m-1.

      Other than that, the argument should be correct. Thanks for pointing this out!

  4. Ah, now the argument is clear. For every subset of n days: if there is a loser, then there are n winners; and if there is no loser, then there are 2m>n winners.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 72 other followers

%d bloggers like this: