Enumerating independent sets in Abelian Cayley graphs

Abstract

We show that any connected Cayley graph $\Gamma$ on an Abelian group of order $2n$ and degree $\tilde{\Omega }(\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 $\Gamma$ is bipartite. Our proof is based on Sapozhenko's graph container method and uses the Plünnecke-Rusza-Petridis inequality from additive combinatorics.

21 pages, fixed minor typos and citations

References in corpus (2)

• The number of independent sets in a graph with small maximum degree
• Independent sets in the discrete hypercube