Семинары: D. Pálvölgyi, At most $4.47^n$ stable matchings

СЕМИНАРЫ


Большой семинар лаборатории комбинаторных и геометрических структур 4 марта 2021 г. 19:00, Москва, Онлайн! https://zoom.us/j/279059822 пароль: первые шесть цифр числа \pi после запятой

At most $4.47^n$ stable matchings D. Pálvölgyi
https://youtu.be/ijtV181Zzd4 Аннотация: 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.