An upper bound for the number of independent sets in regular graphs

Write $\mathcal{I}(G)$ for the set of independent sets of a graph $G$ and $i(G)$ for $\mathrm{\mid }\mathcal{I}(G)\mathrm{\mid }$. It has been conjectured (by Alon and Kahn) that for an $N$-vertex, $d$-regular graph $G$, $$i(G)\le {(2^{d+1}-1)}^{N\mathrm{/}2d}\mathrm{.}$$ If true, this bound would be tight, being achieved by the disjoint union of $N\mathrm{/}2d$ copies of $K_{d,d}$. Kahn established the bound for bipartite $G$, and later gave an argument that established $$i(G)\le 2^{\frac{N}{2}(1+\frac{2}{d})}$$ for $G$ not necessarily bipartite. In this note, we improve this to $$i(G)\le 2^{\frac{N}{2}(1+\frac{1+o(1)}{d})}$$ where $o(1)\to 0$ as $d\to \mathrm{\infty }$, which matches the conjectured upper bound in the first two terms of the exponent. We obtain this bound as a corollary of a new upper bound on the independent set polynomial $P(\lambda ,G)={\sum }_{I\in \mathcal{I}(G)}{\lambda }^{\mathrm{\mid }I\mathrm{\mid }}$ of an $N$-vertex, $d$-regular graph $G$, namely $$P(\text{gl},G)\le (1+\text{gl}{)}^{\frac{N}{2}}{2}^{\frac{N(1+o(1))}{2d}}$$ valid for all $\text{gl}>0$. This also allows us to improve the bounds obtained recently by Carroll, Galvin and Tetali on the number of independent sets of a fixed size in a regular graph.