Hall

Philosophy

This unit is very unique! It shows the power of Hall's theorem in solving combinatorics problems, most of which involve some kind of matching. Even though Hall is technically graph theory, they are very different because it tells you if a matching exists or not. It doesn't tell you how, but guarantees one exists. In Evan's words, ''Hall’s marriage theorem tells you whether you can construct an injective function X → Y .''

Many of the problems in the unit are of a similar flavor, but as the unit progresses the way to apply Hall may become hidden behind other combinatorics techniques. Knowing that Hall's marriage lemma needs to be applied eventually is already a big advantage in itself, though.

Strategies

• Don't think about problems like this in terms of graph theory! Instead think more about compatibility in bi- (or multi-) partite graphs.
• Be patient!
• Don't overcomplicate the problem! Often problems involving Hall's marriage lemma are not super complex but instead more difficult to figure out.

Difficulty

This is a shorter unit with a typical difficulty for a B-leveled unit.

Notable Problems

• Putnam 2012 B3: A classic application of Hall's marriage lemma.
• PUMaC 2016 A1: A walkthrough which seems grueling at first, but is resolved beautifully by Hall.
• Shortlist 2012 C5: A 9-club on the B version that requires some ingenuity to solve.