6 Aug
2013
6 Aug
'13
5:17 p.m.
The Paley graph has vertices {0,1,...,p-1} where p is prime. Draw an edge between every pair (x,y), and color it red or blue depending on whether or not (x-y) is a quadratic residue, i.e. whether it has a square root. (If p=1 mod 4, then x-y is a residue if and only if y-x is, so the color is the same in both directions.) Some people believe that the largest monochromatic clique in the Paley graph has size O(log n) --- which, in terms of Ramsey graphs, makes it as good (within a constant) as a uniformly random coloring. How much numerical work has been done on this? What is the largest value of p that has been tried? - Cris