The number of cliques in graphs of given order and size

Abstract:

Let $k_{r}\left (n,m\right )$ denote the minimum number of $r$-cliques in graphs with $n$ vertices and $m$ edges. For $r=3,4$ we give a lower bound on $k_{r}\left (n,m\right )$ that approximates $k_{r}\left (n,m\right )$ with an error smaller than $n^{r}/\left (n^{2}-2m\right ).$

The solution is based on a constraint minimization of certain multilinear forms. Our proof combines a combinatorial strategy with extensive analytical arguments.