<p>Isn't the conjecture in the paper that the number of $(k+1)$-cliques in this case is at least $c^{k-1}$? That's the number you get by adding a single edge to the Turan-graph. I think it's proved in <a href="http://www.renyi.hu/~p_erdos/1969-10.pdf" rel="nofollow">1969-10</a>. Also relevant: <a href="http://www.renyi.hu/~p_erdos/1983-28.pdf" rel="nofollow">1983-28</a>.
Recently, there has been significant progress on bounding the number of cliques as a function of the quadratic term of the number of edges: <a href="http://arxiv.org/abs/1212.2454" rel="nofollow">arxiv:1212.2454</a>.  </p>

CC BY-SA 3.0
2013-11-30T00:30:25.323Z
2013-11-30T00:30:25.323Z
Thomas Kalinowski
<p>Erdos&amp;Stone conjectured in <a href="http://www.renyi.hu/~p_erdos/1946-08.pdf">1946-08</a> that </p>

<p>there are at least $ck-1$ (k+1)-cliques in $G=(V,E)$ 
whenever $|V|=ck$, $|E|-1$ is the edge-count in Turan's 
$T(|V|,k)$, i.e., </p>

<p>$|E|= 1+\lfloor {(k-1)|V|^2} / (2k) \rfloor$. </p>

<p>I am looking to see whether this conjecture has been proved in literature. 
Didn't see a trace of it myself. </p>

<p>Thanks in advance. </p>

<reference-request><graph-theory><co.combinatorics><clique>
Erdos conjecture, number of cliques, Turan`s graph
ashley
# Erdos conjecture, number of cliques, Turan`s graph

(Asked by: username_0 on 2013-10-04)

Erdos&Stone conjectured in [1946-08](http://www.renyi.hu/~p_erdos/1946-08.pdf) that

there are at least $ck-1$ (k+1)-cliques in $G=(V,E)$
whenever $|V|=ck$, $|E|-1$ is the edge-count in Turan's
$T(|V|,k)$, i.e.,

$|E|= 1+\lfloor {(k-1)|V|^2} / (2k) \rfloor$.

I am looking to see whether this conjecture has been proved in literature.
Didn't see a trace of it myself.

Thanks in advance.

**Tags:** reference-request, graph-theory, co.combinatorics, clique

---

## 1 answers

### Answer by username_1 on 2013-11-30. Score: 3

Isn't the conjecture in the paper that the number of $(k+1)$-cliques in this case is at least $c^{k-1}$? That's the number you get by adding a single edge to the Turan-graph. I think it's proved in [1969-10](http://www.renyi.hu/~p_erdos/1969-10.pdf). Also relevant: [1983-28](http://www.renyi.hu/~p_erdos/1983-28.pdf).
Recently, there has been significant progress on bounding the number of cliques as a function of the quadratic term of the number of edges: [arxiv:1212.2454](http://arxiv.org/abs/1212.2454).


---

