{"id":"arxiv/2611.06604","url":"https://arxiv.org/abs/2611.06604","tags":["cs.DS","cs.DM","math.CO"],"score":0,"title":"A Sub-$3^n$ Upper Bound on the Number of Stable Matchings","domain":"cs.DS","source":"arxiv","authors":["Ken-ichi Kawarabayashi","Hikaru Wada","Masataka Yoneda"],"reviews":0,"subject":"cs.DS","summary":"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,…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-04","reactions":{}}