Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 49 min ago
PreprintCC BY 4.0arXiv

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

  • Ken-ichi Kawarabayashi
  • Hikaru Wada
  • Masataka Yoneda
Open at sourcePDFDOICite

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.999n 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.28n/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.332n bound. We also exploit relationships among local structures and use a charging argument to improve the bound to 2.999n.

Related

  1. A 2.81n upper bound on the number of stable matchings
    Ebrahim Ghorbani, Matthias Mnich
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. A double-logarithmic upper bound on the chromatic number of the associahedron
    Sang-il Oum, David R. Wood
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. An upper bound of 61 for the Ramsey number $R(3,3,3,3)$
    Milos Tatarevic
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. The Tight Upper Bound on the Number of Distinct Squares in Circular Words
    Rikuya Hamai
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. An improved upper bound on the chromatic number of the n-dimensional sphere
    A. I. Bikeev, V. A. Voronov, A. M. Raigorodskii
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{kawarabayashi2026sub3n,
  title = {{A Sub-$3^n$ Upper Bound on the Number of Stable Matchings}},
  author = {Ken-ichi Kawarabayashi and Hikaru Wada and Masataka Yoneda},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.06604},
  eprint = {2611.06604},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.06604},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - A Sub-3^n Upper Bound on the Number of Stable Matchings
AU  - Ken-ichi Kawarabayashi
AU  - Hikaru Wada
AU  - Masataka Yoneda
PY  - 2026
DA  - 2026/11/04
PB  - arXiv
DO  - 10.48550/arxiv.2611.06604
UR  - https://arxiv.org/abs/2611.06604
AB  - 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 2.28^n/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.
ER  -