Answers are grounded in this paper and cite their sources.
We study the maximum number SM(n) of stable matchings in an instance with n men and n women. Karlin, Oveis Gharan, and Weber (STOC 2018) proved the first single-exponential upper bound; their argument gives SM(n)≤ 2¹⁷ⁿ for sufficiently large n. Palmer and Pálvölgyi (FOCS 2021) improved this bound to 3.55ⁿ+O(1). We prove that SM(n)<2.81ⁿ. This brings the exponential base closer to $2.28$, the base of the best known lower bound. More precisely, we bound the number of stable matchings in each instance in terms of each person's number of stable partners, where a stable partner is someone matched to that person in at least one stable matching. Our proof assigns each person a weight determined by this number and uses these weights to bound the number of stable matchings by induction.
No takes yet. Share an insight, caveat, or question.
Ghorbani et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: