Enumerating independent sets in Abelian Cayley graphs

Abstract: We show that any Cayley graph 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 the $o(1)$ term whenever the graph is bipartite. The proof is based on the container method and the Pl\"{u}nnecke-Rusza-Petridis inequality from additive combinatorics.

Joint work with Liana Yepremyan.

combinatoricsprobability

Audience: researchers in the topic

Extremal and probabilistic combinatorics webinar

Series comments: We've added a password: concatenate the 6 first prime numbers (hence obtaining an 8-digit password).