Cardinalities of the total number of independent sets

Abstract

We study the set of numbers the total number of independent sets can admit in $n$-vertex graphs. In this paper, we prove that the cardinality $\mathcal{N}i(n)$ of this set is very close to $2^n$ in the following sense: $\mathcal{N}i(n)/2^n=O(n^{-1/5})$ while for infinitely many $n$, we have ${\log }_2(\mathcal{N}i(n)/2^n)\ge -2^{(1+o(1)\sqrt{{\log }_{2}n}}$. This set is also precisely the set of possible values of the independence polynomial $I_G(x)$ at $x=1$ for $n$-vertex graphs $G$. As an application, we address an additive combinatorial problem on subsets of a given vector space that avoid certain intersection patterns with respect to subspaces.

18 pages, 2 figures