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

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