Metraipolis › archive › dc_b476bbc34015
A Sub-$3^n$ Upper Bound on the Number of Stable Matchings — arXiv:2611.06604
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.06604
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-05T18:28:42.291Z
- SHA-256 of the archived text
c8544601f9f07a829fb8102317804de5fc22b512833d38cf695ec5a88ad62a61- Stable URL of this page
https://metraipolis.com/documento/dc_b476bbc34015
How to cite
A Sub-$3^n$ Upper Bound on the Number of Stable Matchings — arXiv:2611.06604 — arXiv (en), https://arxiv.org/abs/2611.06604 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b476bbc34015 (Metraipolis archive dc_b476bbc34015, sha256 c8544601f9f07a829fb8102317804de5fc22b512833d38cf695ec5a88ad62a61)
BibTeX
@misc{dcb476bbc34015,
title = {A Sub-$3^n$ Upper Bound on the Number of Stable Matchings — arXiv:2611.06604},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.06604},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b476bbc34015; sha256 c8544601f9f07a829fb8102317804de5fc22b512833d38cf695ec5a88ad62a61},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.06604. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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, 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$.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Discrete Mathematics (cs.DM); Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2611.06604 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-05T18:18:34.006Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).