# Number of stable matchings

In the stable marriage problem, is it possible to find an instance with $$2^{n -1}$$ stable matchings when $$n$$ is a power of 2 (or just even)? If yes, how? I know how to build an instance in which $$2^{n/2}$$ stable matchings can be obtained, but was wondering if the aforementioned number of stable matchings ($$2^{n -1}$$) can be obtained too.

Yes. Thurber showed [1,Theorem 5] that for all $$n\geq 1$$, the maximum number of stable matchings is at least $$\frac{(2.28)^n}{(1+\sqrt{3})^{1+\log_2 n}}$$.
If I'm not mistaken this is strictly greater than $$2^n$$ for all $$n\geq 52$$ (and of course asymptotically it's an exponential factor more).
• He also mentions that examples meeting the specific question of the OP (instances with $2^{n-1}$ stable matchings when $n$ is a power of $2$) were previously constructed in P. W. Irving, R. Leather, The complexity of counting stable marriages, SIAM J. Comput. 15 (1986), 655--667. Commented Sep 16, 2022 at 8:16
• I've heard of this gem of a paper (soon to be updated) giving a $3.55^n$ upper bound: arxiv.org/abs/2011.00915 Commented Sep 18, 2022 at 18:25