Klas Markström: Turan-problem for hypergraphs

Lunch is served at 12:00 noon (register at doodle.com/i2gde6v9e4kbuqyt by Monday Nov 11 at 8 pm). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for ca two hours of more technical discussions.

Abstract

The classical Turan-problem asks the following question. Given a graph H, what is the maximum number of edges in a graph on n vertices which does not contain a copy of H? For ordinary graphs a results of Erdös, Stone and Simonovits gives an asymptotic solution to this problem. However the asymptotics for bipartite graphs H and graphs H which do not have constant size still present problems. The latter connects to the well known triangle removal lemma.

A 3-graph, or 3-uniform hypergraph, consists of a vertex set and a set of edges, which are vertex sets of size 3. Unlike the Turan-problem for graphs, the Turan-problem for 3-graphs is still far from understood, for example we do not know the correct asymptotics for any complete 3-graph.

I will survey some methods and problems in this area, discussing how lower and upper bounds have been proven.