Hall's marriage theorem
Tonight's idea
Four jobs, four people, and a list of who is qualified for what. Can every job be filled by a different qualified person? Draw jobs on the left, people on the right, and an edge for each qualification: a bipartite graph. A perfect matching picks one edge per job with no person used twice.
Here is an obstacle. Take any set \(S\) of jobs and let \(N(S)\) be the people qualified for at least one of them, the neighbourhood of \(S\). If \(N(S)\) is smaller than \(S\), you are stuck: those jobs need \(|S|\) different people (the bars mean "the number of elements of") and there are not enough. So a matching requires
Hall's condition. For every set \(S\) of jobs, \(|N(S)| \ge |S|\).
Hall's theorem (1935): the condition is also enough. If every \(k\) jobs have at least \(k\) qualified people between them, a perfect matching exists.
The easy direction is the obstacle, made precise: a matching pairs the jobs in \(S\) with \(|S|\) distinct qualified people, so \(|N(S)| \ge |S|\). The hard direction, that the condition forces a matching into existence, goes by induction on the number of jobs; we state it and use it. Checking all \(2^n\) sets is slow, but fast algorithms either build the matching or hand back a failing \(S\).
Watch one: four jobs
Job 1: A or B. Job 2: A or B. Job 3: A or B. Job 4: C or D. Every job has two candidates, which looks healthy. But \(S = \{1, 2, 3\}\) has \(N(S) = \{A, B\}\): three jobs, two people. Hall's condition fails and no cleverness helps. Now certify C for job 3, the dashed edge. Checking all 15 non-empty sets is tedious. Instead, exhibit the matching 1–A, 2–B, 3–C, 4–D: it is itself the proof that every set now passes, because the easy direction says a matching implies the condition.
Your turn
- Three jobs: job 1 can go to A only, job 2 to A or B, job 3 to B only. Find a perfect matching or a failing set \(S\). Check the sets of size 2 as well.
- Four jobs and four people. Every job has exactly two qualified people and every person is qualified for exactly two jobs. Show that a perfect matching always exists. Hint: count edges out of any \(k\) jobs.
- Five jobs. Job 1: A, C. Job 2: B, D. Job 3: A, C. Job 4: A, C. Job 5: A, B, C, D, E. Find a failing set. Then add one qualification that repairs it and write down a perfect matching.
- A standard 52-card deck is dealt into 13 piles of 4 cards, any way at all. Prove that you can pick one card from each pile so that the 13 chosen cards have all 13 ranks (ace, 2, …, king).
Stretch: finishing a Latin rectangle
An \(r \times n\) array with \(r \lt n\) is filled from the symbols \(1, \dots, n\) with no symbol repeated in any row or column. Show that a new row can always be added keeping the rule. Hint: jobs are columns, people are symbols, and a column is "qualified" for the symbols it lacks.
Answers
- Each single job passes and so does each pair: \(N(\{1,2\}) = N(\{1,3\}) = N(\{2,3\}) = \{A, B\}\), two people for two jobs. The whole set fails: \(N(\{1,2,3\}) = \{A, B\}\). No matching. The obstruction only shows at size 3, which is why every size must be checked.
- Take any \(k\) jobs. Between them they have \(2k\) edges. Each person is on at most 2 edges, so the edges reach at least \(2k / 2 = k\) people: \(|N(S)| \ge |S|\) for every \(S\). By Hall's theorem a perfect matching exists. The same argument works whenever every job and every person has the same number of edges.
- \(S = \{1, 3, 4\}\) has \(N(S) = \{A, C\}\): three jobs, two people. Add E to job 4. Then 1–A, 2–B, 3–C, 4–E, 5–D is a perfect matching, so every set passes. (Adding B or D to job 4 also works; the matching you write down is the check.)
- Jobs are the piles, people are the ranks, and a pile is qualified for a rank if it holds a card of that rank. Any \(k\) piles contain \(4k\) cards. Each rank is on exactly 4 cards in the deck, so \(4k\) cards carry at least \(4k / 4 = k\) different ranks. Hall's condition holds, and the matching tells you which card to take from each pile. The same proof works for 4 piles of 13 and the four suits.
Stretch. A column holds \(r\) distinct symbols, so it lacks \(n - r\). Each symbol appears once in every row, hence in exactly \(r\) columns, and is missing from exactly \(n - r\) columns. Any \(k\) columns have \(k(n - r)\) "lacks" edges, and each symbol absorbs at most \(n - r\) of them, so at least \(k\) symbols are reached. Hall gives each column a different symbol it lacks: that is the new row. Repeating, every Latin rectangle completes to a Latin square.