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 as n, the number of members, grows, and with Rob Irving we proved that the limiting probability of solvability is below , at most. Stephan Mertens's extensive numerics compelled him to conjecture that this probability is of order . 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 . However the standard deviation of that number is of order , i.e. too large to conclude that the odd cycles exist with probability . Still, as a byproduct, we show that with probability the fraction of members with more than one stable "predecessor" is of order . Furthermore, with probability the average rank of a predecessor in every stable partition is of order . The likely size of the largest stable matching is , and the likely number of pairs of unmatched members blocking the optimal complete matching is .