Dömötör Pálvölgyi “At most 4.47^n stable matchings” | Big Seminar

March 4, 2021
19.00 MSK (UTC +3)
Talk on Big Seminar

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

Dömötör Pálvölgyi from Eötvös Loránd University, Hungary gave the talk "At most $4.47^n$ stable matchings" on the labs' Big Seminar.

The talk will be held in zoom
Meeting ID: 279-059-822
Password: first 6 decimal places of $\pi$ after the decimal point

You can also write to Alexander Polyanskii (alexander.polyanskii@yandex.ru) or to Maksim Zhukovskii (zhukmax@gmail.com) if you want to be added to mailing list.


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.

Watch the video:

Everyone is invited to attend. The language of the lecture is English. The event is aimed at master and graduate students, as well as researchers in the field of combinatorics.