The Clique Density Theorem

Understand

Tur\'{a}n's theorem is a cornerstone of extremal graph theory.

• It asserts that for any integer $r \geq 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.