The clique density theorem

DOI10.4007/ANNALS.2016.184.3.1zbMATH Open1348.05103arXiv1212.2454OpenAlexW1555702583MaRDI QIDQ338418FDOQ338418

Authors: Christian Reiher 

Publication date: 4 November 2016

Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)

Abstract: Tur'{a}n's theorem is a cornerstone of extremal graph theory. It asserts that for any integer $rgeq2$ every graph on $n$ vertices with more than $fracr-22(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'{a}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$.

Full work available at URL: https://arxiv.org/abs/1212.2454

Recommendations

• Asymptotic Structure for the Clique Density Theorem
• The maximum number of cliques in dense graphs
• Cliques and the spectral radius
• The clique structure of a graph
• Clique numbers of graphs
• scientific article; zbMATH DE number 19181
• On cliques in graphs
• On the densities of cliques and independent sets in graphs
• scientific article; zbMATH DE number 1161246

zbMATH Keywords

extremal graph theoryclique density problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Density (toughness, etc.) (05C42)

Cites Work

• Flag algebras
• Title not available (Why is that?)
• The number of cliques in graphs of given order and size
• Clique polynomials have a unique root of smallest modulus
• Lower bounds on the number of triangles in a graph
• On Sets of Acquaintances and Strangers at any Party
• On the Minimal Density of Triangles in Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Remark on the Number of Complete and Empty Subgraphs
• Note on the smallest root of the independence polynomial
• Title not available (Why is that?)
• Triangles in an Ordinary Graph

Cited In (55)

• Cycles of length three and four in tournaments
• Trivial colors in colorings of Kneser graphs
• Ordered and colored subgraph density problems
• The exact minimum number of triangles in graphs with given order and size
• Supersaturation for subgraph counts
• On the lower tail variational problem for random graphs
• The feasible region of induced graphs
• On the local approach to Sidorenko's conjecture
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• The sum of degrees in cliques
• The feasible region of hypergraphs
• Sidorenko's conjecture for blow-ups
• Tropicalization of graph profiles
• Finding cliques in social networks: a new distribution-free model
• Turán's theorem inverted
• Maximizing proper colorings on graphs
• Minimizing the number of 5-cycles in graphs with given edge-density
• Stability results for two classes of hypergraphs
• Regular Turán numbers and some Gan–Loh–Sudakov‐type problems
• Structure and supersaturation for intersecting families
• Triangle-degrees in graphs and tetrahedron coverings in 3-graphs
• A path forward: tropicalization in extremal combinatorics
• Edges not in any monochromatic copy of a fixed graph
• Two approaches to Sidorenko's conjecture
• Books versus triangles at the extremal density
• Minimum number of edges that occur in odd cycles
• Subgraph densities in a surface
• Local Density in Graphs with Forbidden Subgraphs
• On a conjecture of Nagy on extremal densities
• Finding cliques in social networks: a new distribution-free model
• On the Number of 4-Edge Paths in Graphs With Given Edge Density
• Asymptotic Structure for the Clique Density Theorem
• Unified approach to the generalized Turán problem and supersaturation
• Extremal results in sparse pseudorandom graphs
• On the densities of cliques and independent sets in graphs
• A new Turán-type theorem for cliques in graphs
• Cycles of length three and four in tournaments
• Paths in hypergraphs: a rescaling phenomenon
• Supersaturation in posets and applications involving the container method
• On the number of monotone sequences
• On the KŁR conjecture in random graphs
• The minimum number of triangles in graphs of given order and size
• Minimizing cycles in tournaments and normalized \(q\)-norms
• Rainbow triangles in three-colored graphs
• The number of cliques in graphs of given order and size
• Geometry and optimization in quantum information. Abstracts from the workshop held October 3--9, 2021 (hybrid meeting)
• Supersaturation problem for color-critical graphs
• Graph theory -- a survey on the occasion of the Abel Prize for László Lovász
• Asymptotic structure of graphs with the minimum number of triangles
• Multipodal structure and phase transitions in large constrained graphs
• On graphs that contain exactly \(k\) copies of a subgraph, and a related problem in search theory
• Semidefinite programming and Ramsey numbers
• Inducibility and universality for trees
• Compactness and finite forcibility of graphons
• On a conjecture of Erdős for multiplicities of cliques

This page was built for publication: The clique density theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q338418)