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

Original · EN

Write 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) ≤ (2ᵈ⁺¹-1)ⁿ/²ᵈ. 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)≤ 2N/2(1+2/d) for G not necessarily bipartite. In this note, we improve this to i(G)≤ 2N/2(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) λ|ⁱ| of an N-vertex, d-regular graph G, namely P(,G) ≤ (1+)ⁿ/² 2ⁿ⁽¹⁺ᵒ⁽¹⁾⁾/²ᵈ 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.