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.
Password: first 6 decimal places of $\pi$ after the decimal point
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.
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.