<p>Yes. Thurber showed [1,Theorem 5] that for all <span class="math-container">$n\geq 1$</span>, the maximum number of stable matchings is at least <span class="math-container">$\frac{(2.28)^n}{(1+\sqrt{3})^{1+\log_2 n}}$</span>.</p>
<p>If I'm not mistaken this is strictly greater than <span class="math-container">$2^n$</span> for all <span class="math-container">$n\geq 52$</span> (and of course asymptotically it's an exponential factor more).</p>
<p>[1]<em>Thurber, Edward G.</em>, <a href="http://dx.doi.org/10.1016/S0012-365X(01)00194-7" rel="noreferrer"><strong>Concerning the maximum number of stable matchings in the stable marriage problem</strong></a>, Discrete Math. 248, No. 1-3, 195-219 (2002). <a href="https://zbmath.org/?q=an:0997.05002" rel="noreferrer">ZBL0997.05002</a>.</p>

CC BY-SA 4.0
2022-09-16T08:16:55.580Z
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.
Emil Jeřábek
CC BY-SA 4.0
2022-09-18T18:25:19.773Z
I've heard of this gem of a paper (soon to be updated) giving a $3.55^n$ upper bound: https://arxiv.org/abs/2011.00915
domotorp
CC BY-SA 4.0
2022-09-18T19:28:13.807Z
@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.
Tassle
CC BY-SA 4.0
2022-09-18T19:56:28.193Z
You can also watch it: https://www.youtube.com/watch?v=NmIj-yriOBw&ab_channel=IEEEFoundationsofComputerScience%28FOCS%292021
domotorp
CC BY-SA 4.0
2022-09-16T07:51:59.943Z
2022-09-16T07:51:59.943Z
Tassle
<p>In the stable marriage problem, is it possible to find an instance with <span class="math-container">$2^{n -1}$</span> stable matchings when <span class="math-container">$n$</span> is a power of 2 (or just even)? If yes, how? I know how to build an instance in which <span class="math-container">$2^{n/2}$</span> stable matchings can be obtained, but was wondering if the aforementioned number of stable matchings (<span class="math-container">$2^{n -1}$</span>) can be obtained too.</p>

<co.combinatorics><matching><bipartite-graphs>
Number of stable matchings
Keio203
# Number of stable matchings

(Asked by: username_0 on 2022-09-16)

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.

**Tags:** co.combinatorics, matching, bipartite-graphs

---

## 1 answers

### Answer by username_1 on 2022-09-16. Score: 5 | Accepted answer

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**](http://dx.doi.org/10.1016/S0012-365X(01)00194-7), Discrete Math. 248, No. 1-3, 195-219 (2002). [ZBL0997.05002](https://zbmath.org/?q=an:0997.05002).

> **Comments:**
> **username_2**: 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.  
> **username_3**: I've heard of this gem of a paper (soon to be updated) giving a $3.55^n$ upper bound: https://arxiv.org/abs/2011.00915  
> **username_1**: @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.  
> **username_3**: You can also watch it: https://www.youtube.com/watch?v=NmIj-yriOBw&ab_channel=IEEEFoundationsofComputerScience%28FOCS%292021  

---

