The number of independent sets in an irregular graph
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)≤∏uv∈E(G)i(Kdu,dv)1/(dudv), where du is the degree of vertex u in G. Equality occurs when G is a disjoint union of complete bipartite graphs....
Main Authors: | Sah, Ashwin, Sawhney, Mehtaab, Zhao, Yufei |
---|---|
Other Authors: | Massachusetts Institute of Technology. Department of Mathematics |
Format: | Article |
Language: | English |
Published: |
Elsevier BV
2020
|
Online Access: | https://hdl.handle.net/1721.1/126178 |
Similar Items
-
Cayley Graphs Without a Bounded Eigenbasis
by: Sah, Ashwin, et al.
Published: (2022) -
A counterexample to the Bollobás–Riordan conjectures on sparse graph limits
by: Sah, Ashwin, et al.
Published: (2021) -
A counterexample to the Bollobás–Riordan conjectures on sparse graph limits
by: Sah, Ashwin, et al.
Published: (2021) -
Patterns without a popular difference
by: Sah, Ashwin, et al.
Published: (2022) -
Perfectly Sampling $k\geq (8/3 +o(1))\Delta$-Colorings in Graphs
by: Jain, Vishesh, et al.
Published: (2022)