Andrey Kupavskii “Random restrictions and forbidden intersections” | Big Seminar

November 25, 2021
19.00 MSK (UTC +3)
Talk on Big Seminar

Andrey Kupavskii "Random restrictions and forbidden intersections"

Andrey Kupavskii from MIPT, Russia and CNRS, France will give the talk "Random restrictions and forbidden intersections" on the labs' Big Seminar.

The talk will be held in zoom
Meeting ID: 279-059-822 zoom-link
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.

Abstract:

Random restrictions is a powerful tool that played a central role in the breakthrough result by Alweiss et al. on the famous Erdos-Rado sunflower conjecture. In this talk, I will describe a new approach to getting a junta-type approximation for families of sets based on random restrictions. Such approximations have several exciting consequences, and I will present a couple of them. The first one is an upper bound on the size of regular k-uniform intersecting families similar to the one obtained by Ellis, Kalai and Narayanan for intersecting families under a much stronger restriction of being transitive. The second one is significant progress on the t-intersection (and the Erdos-Sos forbidden one intersection) problem for permutations. Improving and simplifying previous results, we show that the largest family of permutations [n] -> [n] avoiding pairs of permutations with intersection exactly t-1, has size at most (n-t)!, for t polynomial in n. Previously, this was only known for fixed t.

Joint work with Dmitriy Zakharov.

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.