4
$\begingroup$

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 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.

| cite | improve this question | | | | |
$\endgroup$
2
$\begingroup$

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 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}$.

| cite | improve this answer | | | | |
$\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.