p.s. in particular, quoth Wikipedia: • The Paley graph of order 17 is the unique largest graph G such that neither G nor its complement contains a complete 4-vertex subgraph (Evans et al. 1981). It follows that the Ramsey number R(4, 4) = 18. • The Paley graph of order 101 is currently the largest known graph G such that neither G nor its complement contains a complete 6-vertex subgraph. Cris On Aug 6, 2013, at 5:17 PM, Cris Moore <moore@santafe.edu> wrote:
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