Special Colloquium
Oleg Pikhurko
Carnegie Mellon University
Hypergraph Tur\'an Problem
Abstract: The Tur\'an function of a given $k$-graph (that is, a $k$-uniform set
system) $F$ is the maximum number of edges in an $F$-free $k$-graph on $n$
vertices. This problem goes back to the fundamental paper of Tur\'an from
1941 who solved it for complete graphs. For an arbitrary graph $F$, the
Turan problem is completely understood, if we are happy to tolerate
additive error $o(n^2)$, by the celebrated Erd\H os-Stone-Simonovits
Theorem.
Unfortunately, when we move to $k$-graphs with $k\ge 3$, then very few
non-trivial instances of the problem have been solved. In particular, the
problem of Tur\'an from 1941 (also a \$1000 question of Erd\H os) to
determine the Tur\'an function of the tetrahedron is still open in spite
of decades of active attempts.
In this talk we will survey some results and methods on the hypergraph
Tur\'an problem. In particular, we describe the recent progress on the
tetrahedrom problem obtained by Razborov using his flag algebra technique
as well as the corresponding exact result by the speaker. Time permitting,
we discuss the stability approach of Simonovits that greatly helps in
converting asymptotic computations, such as those obtained via flag
algebras or (hyper)graph limits, into exact results.
There will be tea before the talk in SE) 300 at 3:30.
Thursday December 3, 2009 at 4:00 PM in SEO 636