Turan's theorem tells us that if m is the number of edges in a graph with n vertices and clique number r, then 2m <= (r - 1)n^2/r.

If t denotes the number of triangles, is there a similar upper bound for t, using r and n and/or m for r >= 3? Many thanks.


Zykov [On some properties of linear complexes,Mat.Sbornik N.S.24(66), 163–188, 1949] proved the following generalisation of Turán’s Theorem:

Theorem: For all integers $k \geq s\geq 0$, the maximum number of $s$-cliques in a graph with $n$ vertices and no $(k + 1)$-clique is $\binom{k}{s}(\frac{n}{k})^s$.

This theorem with $s=3$ and $k=r$ solves your question. An easy proof is in my paper at http://users.monash.edu.au/~davidwo/papers/Wood-GC07.pdf


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.