What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?

Stable Marriage Problem: http://en.wikipedia.org/wiki/Stable_marriage_problem

I am aware that for an instance of a SMP, many other stable marriages are possible apart from the one returned by the Gale-Shapley algorithm. However, if we are given only $n$ , the number of men/women, we ask the following question - Can we construct a preference list that gives the maximum number of stable marriages? What is the upper bound on such a number?

For an instance with $n$ men and $n$ women, the trivial upper bound is $n!$, and nothing better is known. For a lower bound, Knuth (1976) gives an infinite family of instances with $\Omega(2.28^n)$ stable matchings, and Thurber (2002) extends this family to all $n$.

• Actually, I believe that this family of instances (for powers of two) is due to Irving and Leather and that Knuth has proved that the recurrence relation satisfied by this family is $\Omega(2.28^n)$ Jan 11 '12 at 14:12
• R.W. Irving and P. Leather. The complexity of counting stable marriages. SIAM Journal on Computing, 15:655-667,1986 Jan 11 '12 at 14:20
• I was confused by the "For a lower bound" phrase. Shouldn't it rather be, "For a tighter/smaller upper bound"? Jan 31 '21 at 19:10
• @JohnRed, No, this is a lower bound in the sense that there are instances with this many stable marriages. It is not a smaller upper bound. Jul 13 '21 at 6:33

An upper bound on the maximum number of stable matchings for a Stable Marriage instance is given in my Master's thesis and it is extended to the Stable Roommates problem as well.The bound is of magnitude $O(n!/2^n)$ and it can be shown that it is actually of magnitude $O\left((n!)^\frac{2}{3}\right)$.

The document is thesis number 97 on page http://mpla.math.uoa.gr/msc/

An exponential upper bound has been given in Anna R. Karlin, Shayan Oveis Gharan, Robbie Weber: A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings.

It is well known that an instance of $n$ men/women can have an exponential number ($O(2^n)$) of stable matchings, but giving a tight upper bound is still open. See Encyclopedia of algorithms http://www.amazon.com/dp/0387307702

• The sentence is misleading, but I think it only claims an exponential lower bound: One of the open problems posed by Knuth in his early monograph on stable marriage  was that of determining the maximum possible number xn of stable matchings for any SM instance involving n men and n women. This problem remains open, although Knuth himself showed that xn grows exponentially with n. Irving and Leather  conjecture that, when n is a power of 2, this function satisfies the recurrence $x_n = 3x^2_{n/2} - 2x^4_{n/4}$ Mar 26 '11 at 20:26

Interesting results on this issue can be found on pages 24 and 25 of the book: The Stable Marriage Problem by Dan Gusfield and Robert Irving, MIT Press, 1989.