When: Monday November 1st, 2021, 3PM (Israel time)
Where: B400 (CS\Engineering building)
Speaker: Noam Lifshitz (HUJI)
Title: Hypergraphs of Large Uniformities
Abstract:
Three of the most fundamental problems in hypergraph theory ask the following for a k-graph H:
1) The Turan problem: How large can an H-free hypergraph be?
2) The Ramsey problem: Is it true that any r-colouring of the complete k-graph on n vertices contains a monochromatic copy of H?
3) Hypergraph Removal lemmas: Is it true that every hypergraph that contains few copies of H is close to an H-free hypergraph.
We are mainly interested in the regime where: k is linear in n; and each edge of H contains at least 0.01n vertices of degree 1. This regime includes many of the well known theorems and open problems in extremal set theory, such as: the Erdos--Ko--Rado theorem, the Frankl--Rodl theorem, the Erdos--Szemeredi sunflower conjecture, and Chvatal's simplex conjecture. For such hypergraphs we solve problems (2) and (3), and determine when the largest H-free family is the dictatorship, i.e. the family of all sets containing a given vertex. We accomplish that by generalizing the invariance principle of Mossel, O'Donnell and Oleszkiewicz from the Boolean cube to another Sn-modules, called the multi-slice.
Based on joint work with Braverman, Khot, and Minzer.