Asymptotic Structure for the Clique Density Theorem

Asymptotic structure for the clique density theorem, Discrete Analysis 2020:19, 26 pp.

Turán’s theorem, which is regarded as the “first” result in extremal graph theory, is the statement that the $K_r$-free graph on $n$ vertices with the largest number of edges is a complete $(r-1)$-partite graph with vertex classes of sizes $\lfloor n/r\rfloor$ or $\lceil n/r\rceil$. (The case $r=3$ was due to Mantel.) This graph is denoted by $T_r(n)$ and the number of its edges by $t_r(n)$.

Since Turán’s theorem, several more detailed results, some of them deep and difficult, have been obtained, giving information about, for example, the structure of almost extremal graphs, or the number of copies of $K_r$ in a graph that has more than $t_r(n)$ edges.

The latter question is known as the Erdős-Rademacher problem. A bold conjecture of Lovász and Simonovits asserts that every extremal example for the problem must be obtained from some complete $s$-partite graph (for some $s$) by adding a triangle-free graph inside one of the parts. If this conjecture were proved, it would greatly restrict the possibilities for the extremal graphs and thereby greatly simplify the problem. However, this conjecture is still open.

Obtaining exact bounds for the Erdős-Rademacher problem seems to be very hard, so it is natural to try for asymptotic bounds. It is not hard to show that for every $\alpha$ there exists $g_r(\alpha)$ such that the smallest number of copies of $K_r$ in a graph of density $\alpha$ with $n$ vertices is $(g_r(\alpha)+o(1))\binom nr$, and also that $g_r(\alpha)$ depends continuously on $\alpha$. Thus, one can attempt to evaluate the function $g_r$ for each $r$.

An indication that this is not a straightforward problem comes from the answer when $r=3$, which was discovered by Alexander Razborov using his famous flag-algebra technique. If $t=\lfloor 1/(1-\alpha)\rfloor$, and therefore $\alpha\in(1-1/t,1-1/(t+1)]$, then $g_3(\alpha)$ is equal to

This strange-looking function is what one obtains when one takes the conjectured extremal examples of Lovász and Simonovits and optimizes over the various choices: it turns out to be best to partition the vertices into sets $V_1,\dots,V_{t+1}$, with $V_1,\dots,V_t$ of equal size, to take the complete $t$-partite graph with vertex sets $V_1,\dots,V_{t-1}$ and $V_t\cup V_{t+1}$, and to add a triangle-free graph inside $V_t\cup V_{t+1}$ with $|V_t||V_{t+1}|$ edges. (It is easy to see that it makes no difference what triangle-free graph with this number of edges one chooses.) However, Razborov’s proof did not show that these graphs were the only (asymptotically) optimal ones.

From here there were two natural directions to pursue: generalizing from triangles to cliques of arbitrary size, and showing that there were no more extremal examples. The first of these was achieved by Christian Reiher, while the second, for $r=3$, was achieved by Oleg Pikhurko and Razborov. This left the task of “completing the square” and generalizing in the two directions simultaneously. The difficulties involved in doing this appeared to be formidable, but that is what this paper achieves – circumventing some of the apparent difficulties by introducing new ideas.

It turns out that the extremal examples for $r\geq 3$ are more or less the same as those for triangles. The one difference is that if $\alpha$ is smaller than the Turán density $t_r(n)/\binom n2$, then obviously any $K_r$-free graph of density $\alpha$ minimizes the number of copies of $K_r$, so we must include these graphs as well. But the problem becomes interesting when $\alpha$ exceeds the Turán density.

One motivation for these asymptotic results is that there is a rather surprising method, pioneered by Simonovits, that sometimes enables one to deduce exact results from approximate ones. The rough idea is that one first proves a stability result, which says that an approximately extremal example must be close to an exact one, and then one proves that amongst all examples close to a conjectured extremal example, that example is itself the best. While the conjecture of Lovász and Simonovits has not yet been solved, there is therefore some reason to hope that this paper brings us closer to a solution.