Pálvölgyi Dömötör: At most 4.47^n stable matchings

Abstract: 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. Joint work with Cory Palmer.

https://zoom.us/j/2961946869