Laboratory of combinatorial and geometric structures

событие 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 (Big Seminar):

Upcoming talk (The Vinberg Lecture):

Coming soon:

Did you know?

We announce the news about the lab events in Facebook and Vk. Also we have a YouTube Channel. Everyone is very welcome to subscribe.

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:

REC $Rightarrow$ Watch the videos from our conference in April (in process)

Recent big seminar videos

News and events

May - June, 2021
MoCCA'20

Recent events:

событие December 18 MIPT Cifra 2.35

Lecture by Balázs Patkós "Turán problems with dergee conditions"

Read more
событие November 29 and December 2 MIPT Arctica

Mini-course by István Tomon "Intersection graphs of geometric objects"

Read more
событие November 26-28 MIPT Arctica

Mini-course by Gábor Tardos "Extremal theory of vertex- and edge-ordered graphs"

Read more
All events

Recorded offline courses:

István Tomon
Intersection graphs of geometric objects
The two-lecture course by István Tomon that took place on 29 November and 2 December 2019
Gábor Tardos
Extremal theory of vertex- and edge-ordered graphs
Mini-course by Gábor Tardos. Two lectures were part of the "Combinatorics and Geometry Days I" conference on November 26-27, and the last one took place on November 28.