The Clique Density Theorem

Abstract

Turán's theorem is a cornerstone of extremal graph theory. It asserts that for any integer $r\ge 2$ every graph on $n$ vertices with more than $\frac{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ász and Simonovits conjectured in the 1970s 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$.

25 pages, second version addresses changes arising from the referee reports

Cited by in corpus (39)

• Extremal results in sparse pseudorandom graphs
• On the KŁR conjecture in random graphs
• Maximum density of an induced 5-cycle is achieved by an iterated blow-up of a 5-cycle
• Towards quantum advantage via topological data analysis
• Asymptotic Structure of Graphs with the Minimum Number of Triangles
• Rainbow triangles in three-colored graphs
• Fractional and integer matchings in uniform hypergraphs
• Extremal regular graphs: independent sets and graph homomorphisms
• Extremal results in random graphs
• Sidorenko's conjecture for blow-ups
• On the lower tail variational problem for random graphs
• Subgraph densities in a surface
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis
• Quantum Topological Data Analysis with Linear Depth and Exponential Speedup
• Complexity of Supersymmetric Systems and the Cohomology Problem
• Supersaturation for subgraph counts
• The number of additive triples in subsets of abelian groups
• The exact minimum number of triangles in graphs of given order and size
• Semidefinite Programming and Ramsey Numbers
• Maximum star densities
• A spectral Erdős-Faudree-Rousseau theorem
• The feasible region of induced graphs
• Minimizing the number of 5-cycles in graphs with given edge-density
• On the number of monotone sequences
• The feasible region of hypergraphs
• An upper bound theorem for a class of flag weak pseudomanifolds
• Densities of 3-vertex graphs
• Edges not in any monochromatic copy of a fixed graph
• Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics
• On the number of 4-cycles in a tournament
• Inducibility of rainbow graphs
• Maximizing proper colorings on graphs
• Graphs with few 3-cliques and 3-anticliques are 3-universal
• $PC$-polynomial of graph
• Triangle-degrees in graphs and tetrahedron coverings in 3-graphs
• Supersaturation Problem for the Bowtie
• Supersaturation Problem for Color-Critical Graphs
• Supersaturation and stability for forbidden subposet problems
• Getting to the Root of the Problem: Sums of Squares for Limits of Trees