When: Sunday, May 23,
10am
Where: Schreiber 309
Speaker: Noam Lifshitz, Hebrew
University
Title: Hypergraphs with
Large Uniformities
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 completely 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 $S_n$-modules,
called the multi-slice.
Based on joint work with Braverman, Khot, and Minzer.