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

Write I(G)I(G) for the set of independent sets of a graph GG and i(G)i(G) for |I(G)||I(G)|. It has been conjectured (by Alon and Kahn) that for an NN-vertex, dd-regular graph GG, i(G)≤(2d+1−1)N/2d.i(G)≤(2d+1−1)N/2d. If true, this bound would be tight, being achieved by the disjoint union of N/2dN/2d copies of Kd,dKd,d. Kahn established the bound for bipartite GG, and later gave an argument that established i(G)≤2N2(1+2d) for GG not necessarily bipartite. In this note, we improve this to i(G)≤2N2(1+1+o(1)d) where o(1)→0o(1)→0 as d→∞d→∞, 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(λ,G)=∑I∈I(G)λ|I|P(λ,G)=∑I∈I(G)λ|I| of an NN-vertex, dd-regular graph GG, namely P(λ,G)≤(1+λ)N22N(1+o(1))2d valid for all λ>0λ>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.