A bound on coefficient of independence polynomial

Question

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?

Answer 1

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