Number of sets with small sumset and the clique number of random Cayley graphs

Abstract

Let $G$ be a finite abelian group of order $n$. For any subset $B$ of $G$ with $B=-B$, the Cayley graph $G_B$ is a graph on vertex set $G$ in which $ij$ is an edge if and only if $i-j\in B.$ It was shown by Ben Green that when $G$ is a vector space over a finite field $Z/pZ$, then there is a Cayley graph containing neither a complete subgraph nor an independent set of size more than $clognloglogn,$ where $c$ is an absolute constant. In this article we observe that a modification of his arguments shows that for an arbitrary finite abelian group of order $n$, there is a Cayley graph containing neither a complete subgraph nor an independent set of size more than $c(omeg{a}^3(n)logomega(n)+lognloglogn)$, where $c$ is an absolute constant and $omega(n)$ denotes the number of distinct prime divisors of $n$.

15 pages, no figure, online abstract changed, submitted version