At most $4.47^n$ stable matchings

Cory Palmer, Dömötör Pálvölgyi

Published 2020-11-02Version 1

We improve the upper bound for the maximum possible number of stable matchings among $n$ men and $n$ women from $O(131072^n)$ to $O(4.47^n)$. To establish this bound, we develop a novel formulation of a probabilistic technique that is easy to apply and may be of independent interest in counting other combinatorial objects.