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 is a bipartite graph with bipartition . There is a matching that covers if and only if for every subset , where is the number of neighbors of .

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 companies, denote to mean the number of students that at least one of these companies want. If 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 teams play in a round-robin tournament. Over a period of 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 days, in which there are fewer than winners in these days.

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

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

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

Pingback: Hall’s Marriage Theorem | Eventually Almost Everywhere

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.

LikeLike

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.

LikeLike

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.

LikeLike

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!

LikeLike

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.

LikeLike

Female hypergamy completely destroys any real application of this beautiful theorem. Women are just too damn picky.

Women on OKCupid found 80% of men of “below average” attractiveness:

http://blog.okcupid.com/index.php/your-looks-and-online-dating/

In light of this theorem, it is clear that the decline of marriage in American society is due to women; and yet we see endless articles and books blaming and shaming men for the decline of marriage, telling them to “man up.”

If women understood some mathematics, which intuitive articles like this makes easier, they might have reevaluated their choices so as not to end up with that skewed OKCupid situation. They are choosing themselves out of the matching pool.

LikeLike