Home » Subject » Graph Theory » Algebraic G.T.
Importance: High ✭✭✭
Author(s): Alon, Noga
Subject: Graph Theory
» Algebraic Graph Theory
Keywords: Cayley graph
Ramsey number
Recomm. for undergrads: no
Posted by: mdevos
on: June 10th, 2007
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 Cayley graph $ {\mathit Cayley}(G,S) $ has no clique or independent set of size $ > c \log |G| $.

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 $.

Bibliography

[AAAS] P. K. Agarwal, N. Alon, B. Aronov, S. Suri, Can visibility graphs be represented compactly? Discrete Comput. Geom. 12 (1994), no. 3, 347--365. MathSciNet

*[C] Problem BCC14.6 from the BCC Problem List (edited by Peter Cameron)

[G] B. Green, Counting sets with small sumset, and the clique number of random Cayley graphs, Combinatorica 25 (2005), no. 3, 307--326. MathSciNet


* indicates original appearance(s) of problem.
add new comment

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options