Enumerating independent sets in Abelian Cayley graphs
share
We show that any connected Cayley graph Γ on an Abelian group of order 2n and degree Ω̃(log n) has at most 2^n+1(1 + o(1)) independent sets. This bound is tight up to to the o(1) term when Γ is bipartite. Our proof is based on Sapozhenko's graph container method and uses the Plünnecke-Rusza-Petridis inequality from additive combinatorics.
READ FULL TEXT