Enumerating independent sets in Abelian Cayley graphs

09/13/2021

∙

by   Aditya Potukuchi, et al.

∙

0

∙

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.