Mertens’s conjecture on stable-roommates solvability probability

Mertens conjectured that the probability $p_n$ that a random stable-roommates instance is solvable satisfies $p_n\sim e\sqrt{2/\pi}\,n^{-1/4}$. The conjecture arose from numerical work by Mertens, reported in 2014–2015.

Known results

• Mertens (2014–2015): simulations supported $p_n\sim e\sqrt{2/\pi}\,n^{-1/4}$, but did not prove it.
• Pittel: a rigorous lower bound of order $n^{-1/2}$ is known.
• Pittel and Irving: a rigorous upper bound gives $\lim_{n\to\infty}p_n\leq\sqrt{e}/2$.
• A 2026 preprint proves only the weaker upper bound $p_n\leq n^{-1/17}$ for sufficiently large $n$, establishing $p_n\to0$.

October 2026 claimed asymptotic

Caden Young and Ian Studebaker claim to derive the exponent $n^{-1/4}$ rigorously, with a leading constant different from Mertens’s $e\sqrt{2/\pi}$. The preprint is unrefereed and has no independent mathematical assessment, so this is claimed progress rather than an established resolution.

Current status (as of October 2026): $p_n\to0$ is supported by a recent unrefereed bound, while the claimed sharp exponent and revised constant remain unverified and Mertens’s asymptotic conjecture remains open.