{"id":"arxiv/2611.06494","url":"https://arxiv.org/abs/2611.06494","tags":["cs.DS","cs.DM","math.CO"],"score":0,"title":"A $2.81^n$ upper bound on the number of stable matchings","domain":"cs.DS","source":"arxiv","authors":["Ebrahim Ghorbani","Matthias Mnich"],"reviews":0,"subject":"cs.DS","summary":"We study the maximum number ${\\rm 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 ${\\rm SM}(n)\\le 2^{17n}$ for sufficiently large $n$. Palmer and Pálvölgyi (FOCS 2021) improved this bound to $3.55^n+O(1)$. We prove that ${\\rm SM}(n)<2.81^n$. 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,…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-04","reactions":{}}