At most 4.47^n stable matchings

11/02/2020
by   Cory Palmer, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset