BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

A Simply Exponential upper bound on the Number of Stable Matchings Oveis Gharan, Shayan


We show that for any stable matching instance with n men and n women the number of stable matchings is at most C^n for some universal constant C>1. Our proof is based on a reduction to counting the number of downsets of a family of posets that we call mixing. This could be of independent interest in other counting applications. joint work with Anna Karlin and Robbie Weber

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International