The number of independent sets in a regular graph
From MaRDI portal
Publication:3557538
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.
Recommendations
- An upper bound for the number of independent sets in regular graphs
- The number of independent sets in an irregular graph
- The number of independent sets in a graph with small maximum degree
- Minimizing the number of independent sets in triangle-free regular graphs
- On the number of independent sets in expanders
Cites work
- Entropy, independent sets and antichains: A new approach to Dedekind's problem
- Ergodicity of the hard-core model on \(\mathbb{Z}^ 2\) with parity-dependent activities
- Independent sets in regular graphs and sum-free subsets of finite groups
- Matchings and independent sets of a fixed size in regular graphs
- Percolation and the hard-core lattice gas model
- THE CAMERON–ERDOS CONJECTURE
Cited in
(77)- An upper bound for the number of independent sets in regular graphs
- Independent sets in regular graphs and sum-free subsets of finite groups
- On the number of connected sets in bounded degree graphs
- On the number of independent sets in simple hypergraphs
- Minimizing the number of independent sets in triangle-free regular graphs
- Counting independent sets in cubic graphs of given girth
- A proof of the upper matching conjecture for large graphs
- Counting sum-free sets in abelian groups
- Number of \(A + B \neq C\) solutions in abelian groups and application to counting independent sets in hypergraphs
- Independence polynomials of bipartite graphs
- Counting cliques in 1-planar graphs
- Homomorphisms into loop-threshold graphs
- Independent sets in the middle two layers of Boolean lattice
- Counting independent sets in regular hypergraphs
- On the number of independent sets in uniform, regular, linear hypergraphs
- The number of independent sets in an irregular graph
- Counting colorings of a regular graph
- Counting independent sets in graphs
- Bounds on the number of vertex independent sets in a graph
- Counting maximal antichains and independent sets
- The maximum number of complete subgraphs in a graph with given maximum degree
- Maximum number of fixed points in AND-OR-NOT networks
- Regular independent sets
- Maximizing the number of independent sets in claw-free cubic graphs
- Counting dominating sets and related structures in graphs
- Entropy, independent sets and antichains: A new approach to Dedekind's problem
- Birthday inequalities, repulsion, and hard spheres
- On the Number of Connected Sets in Bounded Degree Graphs
- Counting independent sets in some classes of (almost) regular graphs
- The bipartite swapping trick on graph homomorphisms
- Counting independent sets in triangle-free graphs
- On replica symmetry of large deviations in random graphs
- A new method for enumerating independent sets of a fixed size in general graphs
- The number of independent sets in graphs
- The independent set sequence of regular bipartite graphs
- Extremal regular graphs: independent sets and graph homomorphisms
- On the average size of independent sets in triangle-free graphs
- On the number of independent sets in expanders
- Hypergraph Independent Sets
- Maximizing \(H\)-colorings of a regular graph
- Maximal independent sets and regularity of graphs
- Hypergraph containers
- Maximizing H‐Colorings of Connected Graphs with Fixed Minimum Degree
- Independent sets in graphs
- A Method for Computing the Merrifield–Simmons Index on Benzenoid Systems
- Interview with Yufei Zhao
- On the number of r-matchings in a tree
- On the number of maximum independent sets of graphs
- The Widom-Rowlinson model, the hard-core model and the extremality of the complete graph
- Graphs with the fewest matchings
- Extremal H‐Colorings of Graphs with Fixed Minimum Degree
- Independent sets, matchings, and occupancy fractions
- On the Widom-Rowlinson occupancy fraction in regular graphs
- On independent sets in graphs with given minimum degree
- Extremal graphs for homomorphisms. II
- Counting independent sets of a fixed size in graphs with a given minimum degree
- Tight bounds on the coefficients of partition functions via stability
- scientific article; zbMATH DE number 7746253 (Why is no real title available?)
- Regular Turán numbers and some Gan–Loh–Sudakov‐type problems
- On the independence number of regular graphs of matrix rings
- Extremal problems for independent set enumeration
- Two problems on independent sets in graphs
- On the number of independent and \(k\)-dominating sets in graphs with average vertex degree at most \(k\)
- Extremal values of degree-based entropies of bipartite graphs
- Asymptotic behavior of a generalized independent sets model on the two-dimensional Sierpinski gasket
- The number of independent sets in a graph with small maximum degree
- Maximizing the number of H-colorings of graphs with a fixed minimum degree
- The number of independent sets in bipartite graphs and benzenoids
- Independence polynomials of graphs with given cover number or dominate number
- Counting MSTD sets in finite abelian groups
- Counterexamples to conjectures on the occupancy fraction of graphs
- Efficient enumeration of cliques in graphs with bounded maximum degree
- On the number of independent sets in Halin graphs
- Counting homomorphisms in antiferromagnetic graphs via lorentzian polynomials
- Covers, orientations and factors
- A reverse Sidorenko inequality
- Independent sets in association schemes
This page was built for publication: The number of independent sets in a regular graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3557538)
