Ramsey properties of Cayley graphs

Importance: High ✭✭✭
Author(s): Alon, Noga
Recomm. for undergrads: no
Posted by: mdevos
on: June 10th, 2007

\begin{conjecture} There exists a fixed constant $c$ so that every abelian group $G$ has a subset $S \subseteq G$ with $-S = S$ so that the \Def[Cayley graph]{cayley graph} ${\mathit Cayley}(G,S)$ has no clique or independent set of size $> c \log |G|$. \end{conjecture}

The classic bounds from Ramsey theory show that every $n$ vertex graph must have either a clique or an independent set of size $c \log n$ and further random graphs almost surely have this property (using different values of $c$). The above conjecture asserts that every group has a Cayley graph with similar behavior.

Improving upon some earlier results of Agarwal et. al. [AAAS], Green [G] proved that there exists a constant $c$ so that whenever a set $S \subseteq {\mathbb Z}_n$ is chosen at random, and we form the graph with vertex set ${\mathbb Z}_n$ and two vertices $i$, $j$ joined if $i+j \in S$, then this graph almost surely has both maximum clique size and maximum independent size $O(\log n)$. The reader should note that such graphs are not generally Cayley graphs - although the definition is similar.

As a word of caution, Green [G] also shows that a randomly chosen subset of the group ${\mathbb Z}_2^n$ almost surely has both max. clique and max. independent set of size $\Theta( \log N \log \log N )$ where $N = 2^n$.


[AAAS] P. K. Agarwal, N. Alon, B. Aronov, S. Suri, \href[Can visibility graphs be represented compactly?]{http://www.math.tau.ac.il/~nogaa/PDFS/main.pdf} Discrete Comput. Geom. 12 (1994), no. 3, 347--365. \MRhref{1298916}

*[C] Problem BCC14.6 from the \href[BCC Problem List]{http://www.maths.qmul.ac.uk/~pjc/bcc/allprobs.pdf} (edited by Peter Cameron)

[G] B. Green, \href[Counting sets with small sumset, and the clique number of random Cayley graphs]{http://arxiv.org/PS_cache/math/pdf/0304/0304183v2.pdf}, Combinatorica 25 (2005), no. 3, 307--326. \MRhref{2141661}

* indicates original appearance(s) of problem.