Аннотация:
We improve the upper bound for the maximum possible number of stable matchings among $n$ men and $n$ women from $O(131072^n)$ to $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.
Joint work with Cory Palmer.