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
Let’s call a team a “loser” if it lost every single game in these
So this poor loser team has lost to
But wait! If it has lost to
Lucky's Notes 
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
Your Putnam problem statement is poorly worded. Your statement allows one team to play more than one game on a particular day and thus play no game on another day. This permits a looser to generate less than n winners in the n days. This blocks the proof. You have to stipulate that each team plays one and only one game against another team. This is what the original problem states. Please think twice before modifying a well posed problem.
LikeLike
Sorry for the confusion — I attempted to make the statement less wordy and omit details that I thought were obvious. If you allow more than one game per day, then you can put all the games on the first day and no games on the remaining days, and the problem would be trivially false.
LikeLike
That is my point. That is no justification for the ambiguity of your new problem statement. I could well say that your problem is trivially false. A correct proposition is for $p\implies q$ to be true rather than finding r such that $p\wedge r \implies q$ is true.
LikeLike