Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 48 min ago
PreprintCC BY-NC-ND 4.0arXiv

A 2.81n upper bound on the number of stable matchings

  • Ebrahim Ghorbani
  • Matthias Mnich
Open at sourcePDFDOICite

Abstract

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)≤ 217n for sufficiently large n. Palmer and Pálvölgyi (FOCS 2021) improved this bound to 3.55n+O(1). We prove that SM(n)<2.81n. 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.

Related

  1. A Sub-3n Upper Bound on the Number of Stable Matchings
    Ken-ichi Kawarabayashi, Hikaru Wada, Masataka Yoneda
    arXivPreprintCC BY 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{ghorbani2026281n,
  title = {{A $2.81^n$ upper bound on the number of stable matchings}},
  author = {Ebrahim Ghorbani and Matthias Mnich},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.06494},
  eprint = {2611.06494},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.06494},
  note = {CC BY-NC-ND 4.0},
}
RIS
TY  - UNPB
TI  - A 2.81^n upper bound on the number of stable matchings
AU  - Ebrahim Ghorbani
AU  - Matthias Mnich
PY  - 2026
DA  - 2026/11/04
PB  - arXiv
DO  - 10.48550/arxiv.2611.06494
UR  - https://arxiv.org/abs/2611.06494
AB  - 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^17n for sufficiently large n. Palmer and Pálvölgyi (FOCS 2021) improved this bound to 3.55^n+O(1). We prove that 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, 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.
ER  -