Let $G$ be a graph with $m$ edges and $n$ vertices. For a fixed integer $s \leq n$, what lower bound can be shown on the number of independent sets with $s$ vertices?


Letting $d$ denote the average degree $d = 2 m/n$, then when $G$ is a union of $d-1$-cliques it has $$
\frac{n (n - (d+1)) \dots (n - (d+1) (s-1))}{s!} = (d+1)^s \binom{n/(d+1)}{s}
$$
size-$s$ independent sets. Is this the extremal case? Is $G$ always guaranteed to contain this number of size-$s$ independent sets?



A bound on coefficient of independence polynomial
Yes. If you take the complement of your graph, then you get the clique density problem, which was solved recently: <https://arxiv.org/abs/1212.2454>


