The clique density theorem

Christian Reiher¹

¹ Mathematisches Seminar der Universität Hamburg, Hamburg, Germany

Annals of mathematics, Tome 184 (2016) no. 3, pp. 683-707.

Résumé

Turán’s theorem is a cornerstone of extremal graph theory. It asserts that for any integer $r \geqslant 2$, every graph on $n$ vertices with more than ${\tfrac{r-2}{2(r-1)}\cdot n^2}$ edges contains a clique of size $r$, i.e., $r$ mutually adjacent vertices. The corresponding extremal graphs are balanced $(r-1)$-partite graphs.
The question as to how many such $r$-cliques appear at least in any $n$-vertex graph with $\gamma n^2$ edges has been intensively studied in the literature. In particular, Lov\’asz and Simonovits conjectured in the 1970’s that asymptotically the best possible lower bound is given by the complete multipartite graph with $\gamma n^2$ edges in which all but one vertex class is of the same size while the remaining one may be smaller.
Their conjecture was recently resolved for $r=3$ by Razborov and for $r=4$ by Nikiforov. In this article, we prove the conjecture for all values of $r$.

Détail

DOI : 10.4007/annals.2016.184.3.1