A $2.81^n$ upper bound on the number of stable matchings
Source: arxiv.org/abs/2611.06494
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,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.06494
curl -X POST /api/v1/records/arxiv/2611.06494/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.06494/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'