The Number of Independent Sets in a Regular Graph

Abstract

We show that the number of independent sets in an N-vertex, d-regular graph is at most (2^{d+1} - 1)^{N/2d}, where the bound is sharp for a disjoint union of complete d-regular bipartite graphs. This settles a conjecture of Alon in 1991 and Kahn in 2001. Kahn proved the bound when the graph is assumed to be bipartite. We give a short proof that reduces the general case to the bipartite case. Our method also works for a weighted generalization, i.e., an upper bound for the independence polynomial of a regular graph.

5 pages. Accepted by Combin. Probab. Comput

Cited by in corpus (10)

• Hypergraph containers
• On replica symmetry of large deviations in random graphs
• The Bipartite Swapping Trick on Graph Homomorphisms
• Independent Sets, Matchings, and Occupancy Fractions
• Maximizing the number of independent sets of a fixed size
• The number of independent sets in a graph with small maximum degree
• Counting MSTD Sets in Finite Abelian Groups
• The number of independent sets in an irregular graph
• Tight bounds on the coefficients of partition functions via stability
• Performance Evaluation of Stochastic Bipartite Matching Models