2007
Lennon, Craig Thomas
Pittel, Boris G.
An instance of a size n - stable marriage problem involves n men and n
women, each individually ranking all members of opposite sex in order
of preference as a potential marriage partner. A complete matching, a
set of n marriages, is called stable if no unmatched man and woman
prefer each other to their partners in the matching. It is known that,
for every instance of marriage partner preferences, there exists at
least one stable matching, and that there are instances with
exponentially many stable matchings. Our focus is on a random instance
chosen uniformly from among all (n!)^{2n} possible instances. Boris
Pittel had proved that the expected number of stable marriages is of
order n ln(n), while its likely value is of order n^{1/2-o(1)} at
least. Here it is shown that the second order moment of that number is
of order (n ln (n))^2. The combination of the two moment estimates
implies that the fraction of problem instances with roughly c n ln(n)
solutions is 0.84, at least.