Answers are grounded in this paper and cite their sources.
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ⁿ 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 2.28ⁿ/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ⁿ bound. We also exploit relationships among local structures and use a charging argument to improve the bound to 2.999ⁿ.
No takes yet. Share an insight, caveat, or question.
Kawarabayashi et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: