Abstract:
We improve Alon's upper bound for the number of independent sets in regular graphs and extend it to almost regular graphs. We also present an upper bound for the number of independent sets of non-typical size for almost regular graphs and an upper bound of the form $2^{(n/2)(1-c\delta)}$, where $c$ is a constant, for the number of independent sets in almost regular $\delta$-expanders.