On the independence number of sparser random Cayley graphs

Abstract

The Cayley sum graph ${\Gamma }_A$ of a set $A\subseteq {\mathbb{Z}}_n$ is defined to have vertex set ${\mathbb{Z}}_n$ and an edge between two distinct vertices $x,y\in {\mathbb{Z}}_n$ if $x+y\in A$. Green and Morris proved that if the set $A$ is a $p$-random subset of ${\mathbb{Z}}_n$ with $p=1/2$, then the independence number of ${\Gamma }_A$ is asymptotically equal to $\alpha (G(n,1/2))$ with high probability. Our main theorem is the first extension of their result to $p=o(1)$: we show that, with high probability, $$\alpha ({\Gamma }_A)=(1+o(1))\alpha (G(n,p))$$ as long as $p\ge (\log n{)}^{-1/80}$. One of the tools in our proof is a geometric-flavoured theorem that generalises Freĭman's lemma, the classical lower bound on the size of high dimensional sumsets. We also give a short proof of this result up to a constant factor; this version yields a much simpler proof of our main theorem at the expense of a worse constant.

Small adjustments following a helpful referee report, version accepted for publication in the Journal of the London Mathematical Society

References in corpus (3)

• The structure theory of set addition revisited
• Sumsets and entropy revisited
• On a discrete John-type theorem