Abstract: A conjecture of Noga Alon states that for any group $G$ of $n$ elements, there is a Cayley graph containing neither a complete subgraph nor an independent set of size more than $b \log n$ elements, where $b$ is an absolute constant. A weaker version of the conjecture with the term $\log n$ replaced by $\log^2 n$ was proved by Alon and Orilitsky. Ben Green proved the conjecture in the special case when $G$ is cyclic. Moreover in the case when $G$ is a vector space over a finite field, Green proved a weaker version of the conjecture with the term $\log n$ replaced by $\log n \log \log n$.

We show that a modification of Green's arguments show that for any finite abelian group $G$ of order $n$, a weaker version of the conjecture holds with the term $\log n$ replaced by $g(n)$ with $g(n) = c(\omega^3(n)\log \omega (n) + \log n \log\log n$, where $\omega(n)$ denotes the number of distinct prime divisors of $n$. This is proven by showing that the clique number of a random Cayley graph for a finite abelian group $G$ is at most $g(n)$. This in turn is obtained by obtaining an estimate for the number of sets with small "difference" set.