Ian Studebaker

Sharp Asymptotics for the Solvability Probability of Random Stable Roommates

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\sim\frac{e\,2^{1/4}\Gamma(3/4)}{\sqrt\pi}\,n^{-1/4}. \] This establishes Mertens's conjectured exponent of decay, with a leading constant different from his or...