Hypergraph Tur\'an Problems

Peter Keevash
Queen Mary, University of London

One of the earliest results in Combinatorics is Mantel's theorem from 1907 that the largest triangle-free graph on a given vertex set is complete bipartite. However, a seemingly similar question posed by Tur\'an in 1941 is still open: what is the largest 3-uniform hypergraph on a given vertex set with no tetrahedron? This question can be considered a test case for the general hypergraph Tur\'an problem, where given an r-uniform hypergraph F, we want to determine the maximum number of edges in an r-uniform hypergraph on n vertices that does not contain a copy of F. To date there are very few results on this problem, even asymptotically. Recent years have seen significant developments in the available methods, including the use of link graphs, approximate structure (stability), Lagrangians and Flag Algebras. We will discuss these methods and some open problems.

Presentation (PDF File)

Back to Combinatorics Tutorials