RUS  ENG
Полная версия
СЕМИНАРЫ

Большой семинар лаборатории комбинаторных и геометрических структур
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.


© МИАН, 2024