7
$\begingroup$

Erdos&Stone conjectured in 1946-08 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.

$\endgroup$
3
$\begingroup$

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. Also relevant: 1983-28. 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.