×

zbMATH — the first resource for mathematics

Hypergraph Turán problems. (English) Zbl 1244.05159
Chapman, Robin (ed.), Surveys in combinatorics 2011. Papers from the 23rd British combinatorial conference, Exeter, UK, July 3–8, 2011. Cambridge: Cambridge University Press (ISBN 978-1-107-60109-3/pbk). London Mathematical Society Lecture Note Serie 392, 83-139 (2011).
Summary: 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 P. Turán in [Mat. Fiz. Lapok 48, 436–452 (1941; Zbl 0026.26903)] 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án 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. However, recent years have seen a revitalisation of this field, via significant developments in the available methods, notably the use of stability (approximate structure) and flag algebras. This article surveys the known results and methods, and discusses some open problems.
For the entire collection see [Zbl 1218.05005].

MSC:
05C65 Hypergraphs
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite