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

Abstract

Write $\mathcal{I}(G)$ for the set of independent sets of a graph $G$ and $i(G)$ for $|\mathcal{I}(G)|$. It has been conjectured (by Alon and Kahn) that for an $N$-vertex, $d$-regular graph $G$, $$i(G)\le {\left(2^{d+1}-1\right)}^{N/2d}.$$ If true, this bound would be tight, being achieved by the disjoint union of $N/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}\left(1+\frac{2}{d}\right)}$$ for $G$ not necessarily bipartite. In this note, we improve this to $$i(G)\le 2^{\frac{N}{2}\left(1+\frac{1+o(1)}{d}\right)}$$ where $o(1)\to 0$ as $d\to \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 }^{|I|}$ of an $N$-vertex, $d$-regular graph $G$, namely $$ P(\gl,G) \leq (1+\gl)^{\frac{N}{2}} 2^{\frac{N(1+o(1))}{2d}} $$ valid for all $\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.