Small random instances of the stable roommates problem

Abstract

Let $p_n$ denote the probability that a random instance of the stable roommates problem of size $n$ admits a solution. We derive an explicit formula for $p_n$ and compute exact values of $p_n$ for $n\le 12$.

12 pages, 1 figure, 4 tables

References in corpus (5)

• Beauty and Distance in the Stable Marriage Problem
• Statistics of stable marriages
• Random Stable Matchings
• The marriage problem: from the bar of appointments to the agency
• The Marriage Problem and the Fate of Bachelors

Cited by in corpus (1)

• Structural and Algorithmic Results for Stable Cycles and Partitions in the Roommates Problem