The clique density theorem

DOI10.4007/ANNALS.2016.184.3.1MaRDI QIDQ338418zbMATH OpenOpenAlexFDO

Authors Christian Reiher

Publication date 4 November 2016

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

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

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)

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$.

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

Cites work

• scientific article; zbMATH DE number 3821782 (Why is no real title available?)
• scientific article; zbMATH DE number 3745218 (Why is no real title available?)
• scientific article; zbMATH DE number 3508542 (Why is no real title available?)
• scientific article; zbMATH DE number 3185004 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• A Remark on the Number of Complete and Empty Subgraphs
• Clique polynomials have a unique root of smallest modulus
• Flag algebras
• Lower bounds on the number of triangles in a graph
• Note on the smallest root of the independence polynomial
• On Sets of Acquaintances and Strangers at any Party
• On the Minimal Density of Triangles in Graphs
• The number of cliques in graphs of given order and size
• Triangles in an Ordinary Graph

Cited in

(55)

• On a conjecture of Erdős for multiplicities of cliques
• The exact minimum number of triangles in graphs with given order and size
• Supersaturation for subgraph counts
• The feasible region of induced graphs
• On the lower tail variational problem for random graphs
• On the local approach to Sidorenko's conjecture
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• The feasible region of hypergraphs
• The sum of degrees in cliques
• Sidorenko's conjecture for blow-ups
• Turán's theorem inverted
• Maximizing proper colorings on graphs
• Tropicalization of graph profiles
• Finding cliques in social networks: a new distribution-free model
• Minimizing the number of 5-cycles in graphs with given edge-density
• Stability results for two classes of hypergraphs
• Structure and supersaturation for intersecting families
• A path forward: tropicalization in extremal combinatorics
• Regular Turán numbers and some Gan–Loh–Sudakov‐type problems
• Triangle-degrees in graphs and tetrahedron coverings in 3-graphs
• Edges not in any monochromatic copy of a fixed graph
• Two approaches to Sidorenko's conjecture
• Minimum number of edges that occur in odd cycles
• Books versus triangles at the extremal density
• Cycles of length three and four in tournaments
• 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
• Trivial colors in colorings of Kneser graphs
• Extremal results in sparse pseudorandom graphs
• A new Turán-type theorem for cliques in graphs
• Cycles of length three and four in tournaments
• Supersaturation in posets and applications involving the container method
• On the densities of cliques and independent sets in graphs
• Paths in hypergraphs: a rescaling phenomenon
• 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
• Rainbow triangles in three-colored graphs
• Minimizing cycles in tournaments and normalized \(q\)-norms
• Ordered and colored subgraph density problems
• 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
• Multipodal structure and phase transitions in large constrained graphs
• Asymptotic structure of graphs with the minimum number of triangles
• 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

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)