RECORD
The Clique Density Theorem
Combinatorics · Submitted 11 Dec 2012
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim In this article, we prove the conjecture for all values of $r$.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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. 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$.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Tur\'{a}n's theorem is a cornerstone of extremal graph theory. | background 1.00 | 0.02 | 0.01 | asserted 1.00 |
| s1 | 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. | background 1.00 | 0.03 | 0.03 | asserted 1.00 |
| s2 | The corresponding extremal graphs are balanced $(r-1)$-partite graphs. | background 0.99 | 0.04 | 0.01 | asserted 1.00 |
| s3 | 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. | background 0.97 | 0.03 | 0.02 | asserted 0.97 |
| s4 | 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. | background 0.89 | 0.02 | 0.04 | speculative 0.93 |
| s5 | Their conjecture was recently resolved for $r=3$ by Razborov and for $r=4$ by Nikiforov. | background 0.91 | 0.04 | 0.03 | asserted 1.00 |
| s6 | In this article, we prove the conjecture for all values of $r$. | contribution 0.67 | 0.97 | 0.97 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
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. 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$.
Human review
How the literature uses it
11 arXiv papers cite this in 13 sentences
Papers citing it · 5 sentences without a confident label
Uses its method or tool 1 paper
-
In this section, we use the so-called clique-density theorem [ref] and a result of Moon and Moser [ref] to directly characterize families of clique-dense graphs in terms of the required number of edges.
Towards quantum advantage via topological data analysis · Graphs with a quantum advantage · 0.91
Cites it as background 7 papers
-
The recent works of Razborov [ref] , Nikiforov [ref] and Reiher [ref] solved the problem for $s=2$ (with $r=3$, $r=4$ and all $r≥5$, respectively).
On the number of 4-cycles in a tournament · The minimum · 0.86
-
Few examples have been solved, the main ones corresponding to two constraints: edges and the complete graph $K_p$ on $p≥3$ vertices [ref] , which includes the edge/triangle model discussed below.
Multipodal Structure and Phase Transitions in Large Constrained Graphs · Introduction · 0.84
-
The state of our knowledge of $Π_l$ for $l ≥4$ is really very limited, though some work already exists, e.g., [ref] .
Graphs with few 3-cliques and 3-anticliques are 3-universal · Introduction · 0.98
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.