1
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

5
$\begingroup$

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).

[1]Thurber, Edward G., Concerning the maximum number of stable matchings in the stable marriage problem, Discrete Math. 248, No. 1-3, 195-219 (2002). ZBL0997.05002.

$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$ Sep 16, 2022 at 8:16
  • $\begingroup$ 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 $\endgroup$
    – domotorp
    Sep 18, 2022 at 18:25
  • $\begingroup$ @domotorp Nice! I had read the proof of the previous exponential upper bound (with the huge base) but was not aware of this improvement. I'll give this one a read as well, curious to see how you achieved that. $\endgroup$
    – Tassle
    Sep 18, 2022 at 19:28
  • 1
    $\begingroup$ You can also watch it: youtube.com/… $\endgroup$
    – domotorp
    Sep 18, 2022 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.