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 (n) ^-1/80. One of the tools in our proof is a geometric-flavoured theorem that generalizes Freiman'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.