On the independence number of sparser random Cayley graphs

Abstract The Cayley sum graph of a set is defined to have vertex set and an edge between two distinct vertices if . Green and Morris proved that if the set is a ‐random subset of with , then the independence number of is asymptotically equal to with high probability. Our main theorem is the first extension of their result to : we show that, with high probability, as long as . 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.