A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings

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\to \infty$, 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^{n\log n-O(n)}$. In this paper, we show that for all $n$, $f(n)\le 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.