Paperlane

no. 9 · Thursday 5 November 2026

A Sub-$3^n$ Upper Bound on the Number of Stable Matchings

Ken-ichi Kawarabayashi, Hikaru Wada and Masataka Yoneda

math.CO · via cs.DS · 56 pp

Abstract

We study the problem of determining the maximum number of stable matchings. This classical counting problem was posed by Knuth and has been studied for five decades. We obtain a new $2.999^n$ upper bound on the number of stable matchings with $n$ men and $n$ women. This improves the best-known previous result by Palmer and Pálvölgyi. This result gets much closer to the well-known lower bound $\frac{2.28^n}{\text{poly}(n)}$. We refine their entropy-based framework by capturing broader structural relationships among stable matchings. To capture these relationships, we introduce new frameworks, including cones and supports. This establishes the $3.332^n$ bound. We also exploit relationships among local structures and use a charging argument to improve the bound to $2.999^n$.

comments
56 pages, 12 figures
fields
Combinatorics
pdf ↗ page arXiv:2611.06604 ↗