Counting independent sets in regular graphs
by
David Galvin
University of Notre Dame

How many independent sets (sets of pairwise non-adjacent vertices) can a regular graph have? Alon conjectured that if ℑ(G) is the set of independent sets of an N-vertex, d-regular graph G, then

|ℑ(G)| ≤ 2[N/2]+[N/2d];

more precisely, |ℑ(G)| ≤ (2^d+1-1)^N/2d. This bound is attained by the disjoint union of N/2d complete bipartite graphs on 2d vertices. Kahn proved this conjecture for bipartite graphs, and gave an upper bound of the form 2^[N/2]+[N/d] for all graphs.

Here we prove that every N-vertex, d-regular G graph satisfies

|ℑ(G)| ≤ 2[N/d]+[N/2d]+o([N/d]),

and moreover that the stable set polynomial P(x, G)=∑_{I ∈ ℑ(G)} x^|I| satisfies

P(x, G) ≤ (1+x)[N/2] 2[N/2d]+o([N/d]).

This allows us to improve recent bounds obtained by Carroll, Galvin and Tetali on the number of independent sets of a fixed size in regular graphs.

Ingredients in the proof include weighted generalizations of results of Alekseev and Sapozhenko bounding the number of independent sets in graphs in terms of the size of the largest independent set.

Date received: April 9, 2009