On random stable partitions

It is well known that the one-sided stable matching problem (“stable roommates problem”) does not necessarily have a solution. We had found that, for the independent, uniformly random preference lists, the expected number of solutions converges to $$e^{1/2}$$ e 1 / 2 as n, the number of members, grows, and with Rob Irving we proved that the limiting probability of solvability is below $$e^{1/2}/2$$ e 1 / 2 / 2 , at most. Stephan Mertens’s extensive numerics compelled him to conjecture that this probability is of order $$n^{-1/4}$$ 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 $$n^{1/4}$$ n 1 / 4 . However the standard deviation of that number is of order $$n^{3/8}\gg n^{1/4}$$ n 3 / 8 ≫ n 1 / 4 , i.e. too large to conclude that the odd cycles exist with probability $$1-o(1)$$ 1 - o ( 1 ) . Still, as a byproduct, we show that with probability $$1-o(1)$$ 1 - o ( 1 ) the fraction of members with more than one stable “predecessor” is of order $$n^{-1/2+o(1)}$$ n - 1 / 2 + o ( 1 ) . Furthermore, with probability $$1-o(1)$$ 1 - o ( 1 ) the average rank of a predecessor in every stable partition is of order $$n^{1/2}$$ n 1 / 2 . The likely size of the largest stable matching is $$n/2-O(n^{1/4+o(1)})$$ n / 2 - O ( n 1 / 4 + o ( 1 ) ) , and the likely number of pairs of unmatched members blocking the optimal complete matching is $$O(n^{3/4+o(1)})$$ O ( n 3 / 4 + o ( 1 ) ) .