Fix integers $V$ and $E\_{\text{max}}$, and consider graphs $G$ with $V$ vertices and at most $E\_{\text{max}}$ edges. What is the best lower bound that one can give on the number of distinct independent sets that exist in $G$?


(You can also phrase this in terms of cliques; we're asking if a graph with a large enough number of edges is forced to have a lot of cliques.)


Note that there are many results, proceeding from the classical work of Turan, giving good lower bounds for the number of $k$-cliques for some fixed $k$, and this of course gives us *some* bounds on the number of cliques overall. But I'm interested in the best bounds one can find on the number of cliques overall, and this seems to be a different problem.


[This paper](http://arxiv.org/pdf/math/0602191.pdf) of Wood solves the opposite problem (maximizing the number of cliques for fixed $V$ and $E$). Wood's paper also says 'lower bounds
on the number of cliques in a graph have also been obtained' and gives a number of references. But those references all seem to concern Turan type problems where we try to minimize the number of $k$ cliques for some fixed $k$, not the total number of cliques overall.



What is the minimum number of independent sets for a graph with fixed numbers of vertices and edges?
I'll phrase the answer in terms of maximizing the number of cliques when $|E| \ge \gamma|V|^2$ with some constant $\gamma > 1/4$. Note that if $|E| \le |V|^2/4$, then by taking a bipartite graph with two (nearly) equal parts, we can make sure that there are no triangles, so that the only cliques are vertex singletons and edges.


[Christian Reiher's clique density theorem](http://arxiv.org/abs/1212.2454) tells us an explicit function $f(k, \gamma)$ such that minimum number of $k$-cliques in a graph on $n$ vertices with $\gamma n^2$ edges is $(f(k,\gamma)+o(1))n^k$. 


The asymptotic minimum is achieved by a complete multipartite graph with $s + 1$ vertex classes, where all vertex classes have the same size, with the exception of at most one part, which may be smaller. For each $\gamma$, there is a unique value of $s$ (as a non-decreasing function of $\gamma$), such that there is an $(s+1)$-partite graph as above with $|E| = (\gamma + o(1))|V|^2$.


To obtain the answer to the original question when the size $k$ of clique is not fixed, let $s$ be the unique positive integer, as above, so that $f(s+1,\gamma) > 0$ and $f(s+2,\gamma) = 0$. The minimum number of copies of $K\_{s+1}$ is $(f(s+1,\gamma) + o(1))n^{s+1}$ by Reiher's theorem. On the other hand, in the multipartite construction above, there are $(f(s+1,\gamma) + o(1))n^{s+1}$ copies of $K\_{s+1}$, no copies of $K\_k$ for $k > s+1$, and at most $n^k = o(n^{s+1})$ copies of $K\_k$ for $k < s+1$. It follows that the minimum number of cliques in a graph on $n$ vertices with at least $\gamma n^2$ edges is $(f(s+1,\gamma) + o(1))n^{s+1}$. 


