Los Angeles Math Circle

5/19 -- High School II: Bipartite Graphs (Harris Khan)

In this lesson we'll solve the "stable matching problem." Imagine two tennis clubs A and B competing in a tournament. Each player has a preference for which person they want to play from the other team. Can we find a pairing that is stable, i.e. where there is no pairing such that both players prefer to play someone else?