On the independence number of sparser random Cayley graphs

The Cayley sum graph ΓA of a set A ⊆ Zₙ is defined to have vertex set Zₙ and an edge between two distinct vertices x, y ∈ Zₙ if x + y ∈ A. Green and Morris proved that if the set A is a p-random subset of Zₙ with $p = 1/2$, then the independence number of ΓA is asymptotically equal to α(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, α(ΓA) = (1 + o(1)) α(G(n, p)) as long as p ≥ (log n)-1/80. One of the tools in our proof is a geometric-flavoured theorem that generalizes Fre{i}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.