Sharp Asymptotics for the Solvability Probability of Random Stable Roommates
Abstract
For even n, let Pn be the probability that independent uniform strict preference lists on n participants admit a stable perfect matching. We prove Pn∼(e 21/4Γ(3/4))/√π n−1/4. This establishes Mertens's conjectured exponent of decay, with a leading constant different from his original numerical prediction. The proof starts from Mertens's exact alternating sum over stable permutations. To preserve its cancellation, we construct a common approximation for all cycle structures with the same number of vertices in cycles longer than two. By symmetry, the integrated first-order correction is the same for every such cycle structure, and the remaining errors can be summed in absolute value. The enumeration then reduces the probability to a one-dimensional sum with positive terms.
Related
- Asymptotics of the coefficients of polynomials, asymptotic zero distribution and free probability
- On the critical branching random walk I: branching capacity and visiting probability
- Asymptotics for partition functions of random normal matrix models with singularities
- Decoding Error Probability of the Random Code Ensemble over the Erasure Channel
- Asymptotics for Bivariate Risk Models with Random-Size Clusters of Dependent Claims
BibTeX
@misc{young2026sharp,
title = {{Sharp Asymptotics for the Solvability Probability of Random Stable Roommates}},
author = {Caden Young and Ian Studebaker},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.07741},
eprint = {2610.07741},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.07741},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Sharp Asymptotics for the Solvability Probability of Random Stable Roommates
AU - Caden Young
AU - Ian Studebaker
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.07741
UR - https://arxiv.org/abs/2610.07741
AB - For even n, let P_n be the probability that independent uniform strict preference lists on n participants admit a stable perfect matching. We prove P_n∼(e 2^1/4Γ(3/4))/√π n^−1/4. This establishes Mertens's conjectured exponent of decay, with a leading constant different from his original numerical prediction. The proof starts from Mertens's exact alternating sum over stable permutations. To preserve its cancellation, we construct a common approximation for all cycle structures with the same number of vertices in cycles longer than two. By symmetry, the integrated first-order correction is the same for every such cycle structure, and the remaining errors can be summed in absolute value. The enumeration then reduces the probability to a one-dimensional sum with positive terms.
ER -