2017/05/23 by Pittel, Boris · 2 citations
#05C05 #05C30 #05C80 #34E05 #60C05 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1705.08340
The stable roommates problem does not necessarily have a solution, i.e. a stable matching. We had found that, for the uniformly random instance, the expected number of solutions converges to e1/2 as n, the number of members, grows, and with Rob Irving we proved that the limiting probability of solvability is e1/2/2, at most. Stephan Mertens's extensive numerics compelled him to conjecture that this probability is of order n-1/4. Jimmy Tan introduced a notion of a stable cyclic partition, and proved existence of such a partition for every system of members' preferences, discovering that presence of odd cycles in a stable partition is equivalent to absence of a stable matching. In this paper we show that the expected number of stable partitions with odd cycles grows as n1/4. However the standard deviation of that number is of order n3/8≫ n1/4, too large to conclude that the odd cycles exist with high probability (whp). Still, as a byproduct, we show that whp the fraction of members with more than one stable "predecessor" is of order n-1/4. Furthermore, whp the average rank of a predecessor in every stable partition is of order n1/2. The likely size of the largest stable matching is n/2-O(n1/4+o(1)), and the likely number of pairs of unmatched members blocking the optimal complete matching is O(n3/4+o(1)).