The number of independent sets in an irregular graph

Abstract

Settling Kahn's conjecture (2001), we prove the following upper bound on the number $i(G)$ of independent sets in a graph $G$ without isolated vertices: \[ i(G) \le \prod_{uv \in E(G)} i(K_{d_u,d_v})^{1/(d_u d_v)}, \] where $d_u$ is the degree of vertex $u$ in $G$. Equality occurs when $G$ is a disjoint union of complete bipartite graphs. The inequality was previously proved for regular graphs by Kahn and Zhao. We also prove an analogous tight lower bound: \[ i(G) \ge \prod_{v \in V(G)} i(K_{d_v+1})^{1/(d_v + 1)}, \] where equality occurs for $G$ a disjoint union of cliques. More generally, we prove bounds on the weighted versions of these quantities, i.e., the independent set polynomial, or equivalently the partition function of the hard-core model with a given fugacity on a graph.

18 pages

References in corpus (12)

• Hypergraph containers
• Information Inequalities for Joint Distributions, with Interpretations and Applications
• The Number of Independent Sets in a Regular Graph
• On replica symmetry of large deviations in random graphs
• On the average size of independent sets in triangle-free graphs
• Extremal regular graphs: independent sets and graph homomorphisms
• On the hard sphere model and sphere packings in high dimensions
• The Bipartite Swapping Trick on Graph Homomorphisms
• Independent Sets, Matchings, and Occupancy Fractions
• The number of independent sets in a graph with small maximum degree
• Extremes of the internal energy of the Potts model on cubic graphs
• Counting proper colourings in 4-regular graphs via the Potts model

Cited by in corpus (1)

• IEEE 802.15.4.e TSCH-Based Scheduling for Throughput Optimization: A Combinatorial Multi-Armed Bandit Approach