 |
November 25, 202119.00 |
Andrey Kupavskii "Random restrictions and forbidden intersections" |
|
| Big Seminar Zoom | |
|
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. See more
|
Upcoming talk on The Vinberg Lecture:
Recently recorded [in Russian]:
|
November 25, 202119.00 |
Andrey Kupavskii "Random restrictions and forbidden intersections" |
|
| Big Seminar Zoom | |
|
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. See more
|
Upcoming talk on The Vinberg Lecture:
Upcoming talk on Big Seminar:
Welcome!
We are the Laboratory of Combinatorial and Geometric Structures at the Moscow Institute of Physics and Technology. On this website, you can learn about Lab activities and members, as well as related events and useful materials like past and future workshops, talks, and video lectures. The lab aims to initiate collaboration and exchange between foreign and Russian researchers who work on different theoretical questions in the fields of Combinatorics, Discrete and Computational Geometry, and Theoretical Сomputer Science, and it was formed in December 2019.
Head of the laboratory: Prof. János Pach
Vice-head: Dr. Andrey Kupavskii
Assistant head: Dr. Alexandr Polyanskii
Recent video lectures:
Recent video lectures:
Coming soon:
REC $Rightarrow$ Watch the videos from our conference in April (in process)
Recent big seminar videos
News and events
Testing Utreon
We are testing Utreon platform for publishing Labs' videos in order to get rid of unwanted advertisement. Utreon embeds sometimes may lead to increasing loading time or other performance issues on our website. If you are facing a problem with loading video, please visit directly Labs' Channels on platforms:
Utreon page Youtube ChannelTwo Lab members got the Prize for Young Mathematicians
Learn more
Round the World Relay in Combinatorics
See the talk page