Bipartite Graphs and Matching

A bipartite graph is simply one whose dots split into two teams, with lines only between the teams, never inside one. "Bi-partite" means "two parts." A matching pairs dots from one team with dots from the other along those lines, with nobody paired twice, and it's good for any assignment problem: applicants to jobs, students to dorm rooms, donors to patients. Hall's condition $|N(S)| \ge |S|$ looks cryptic, but it's just this: pick any group $S$ of applicants, look at $N(S)$ (all the jobs at least one of them qualifies for), and check that there are at least as many jobs as people, $|N(S)| \ge |S|$. If that holds for every group, everyone can be hired. It's a bottleneck check, nothing more.

Bipartite test. You've seen this idea already in the last lesson: splitting into two teams with no edges inside a team is the same as coloring the vertices with 2 colors. And a 2-coloring exists exactly when there's no odd cycle, since going around an odd cycle you'd have to alternate teams and land back on the wrong one. Breadth-first search checks this in one pass.

Matchings. A matching is a set of edges with no shared vertices. It's perfect if it covers every vertex. So how do you find a big one? Greedily grabbing pairs can get stuck, with someone left over even though a better arrangement exists. The fix is an augmenting path: a path that alternates between unused and used edges and starts and ends at unmatched vertices. Notice it has one more unused edge than used ones, since it starts and ends on unused edges. So flipping it, swapping used for unused all along the path, adds one edge to the matching while keeping it a matching. And a matching is maximum exactly when no augmenting path exists. There's an animation further down that does exactly this.

Hall's theorem. Side $A$ can be matched completely if and only if every group $S$ of $A$-vertices is, collectively, joined to at least $|S|$ vertices, so there's no bottleneck. One direction is the pigeonhole principle from the counting unit: if three applicants all qualify for only the same two jobs, some two of them would have to share a job, so matching fails. The surprising part is the other direction: if no group is ever short, a complete matching always exists.

Stable matching. When both sides have preferences, the Gale–Shapley algorithm finds a matching where no two people would both rather be with each other. It earned Lloyd Shapley and Alvin Roth the 2012 Nobel Prize in Economics.

A common mistake. It's tempting to check Hall's condition one applicant at a time: everyone qualifies for at least one job, so we're fine. That isn't enough. In the example below, Ana and Ben each qualify for a job, but together they only have one between them. The condition has to hold for every group.

The U.S. medical residency match and kidney exchange programs run matching algorithms, the work honored by the 2012 Nobel Prize in Economics.