A remark on the independence number of sparse random Cayley sum graphs

Abstract

The Cayley sum graph ${\Gamma }_S$ of a set $S\subseteq {\mathbb{Z}}_n$ is defined on the vertex set ${\mathbb{Z}}_n$, with an edge between distinct $x,y\in {\mathbb{Z}}_n$ if $x+y\in S$. Campos, Dahia, and Marciano have recently shown that if $S$ is formed by taking each element in ${\mathbb{Z}}_n$ independently with probability $p$, for $p>(\log n{)}^{-1/80}$, then with high probability the largest independent set in ${\Gamma }_S$ is of size $$(2+o(1)){\log }_{1/(1-p)}(n).$$ This extends a result of Green and Morris, who considered the case $p=1/2$, and asymptotically matches the independence number of the binomial random graph $G(n,p)$. We improve the range of $p$ for which this holds to $p>(\log n{)}^{-1/3+o(1)}$. The heavy lifting has been done by Campos, Dahia, and Marciano, and we show that their key lemma can be used a bit more efficiently.

arXiv comment10 pages