Abstract

The paper to be presented is:

Title: A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings
Authors: Anna Karlin, Shayan Oveis Gharan, and Robbie Weber

Paper Abstract: Stable matching is a classical combinatorial problem that has been the subject of intense theoretical and empirical study since its introduction in 1962 in a seminal paper by Gale and Shapley. In this paper, we provide a new upper bound on f(n), the maximum number of stable matchings that a stable matching instance with n men and n women can have. It has been a long-standing open problem to understand the asymptotic behavior of f(n) as n→∞, first posed by Donald Knuth in the 1970s. Until now the best lower bound was approximately 2.28^n, and the best upper bound was 2^(nlogn−O(n)). In this paper, we show that for all n, f(n)≤c^n for some universal constant c. This matches the lower bound up to the base of the exponent. Our proof is based on a reduction to counting the number of downsets of a family of posets that we call "mixing". The latter might be of independent interest.

Link to paper.

This week's presenter is: Aditi Dudeja, Rutgers University.

To receive email notifications about upcoming presentations and instructions for joining please subscribe to the reading group mailing list. If you would like to attend only this meeting, please contact the organizers for a link to join.