For parameters $m,k$, we call a graph on $n$ vertices Ramsey if it contains no complete subgraph on $m$ vertices and its complement contains no complete subgraph on $k$ vertices (or vice versa). The existence of a Ramsey graph of size $n$ implies that the Ramsey number $R(m,k)>n$.

It is common to use quadratic, cubic, or higher-order residues to construct candidate Ramsey graphs; the vertices of the graph are numbered $0,\ldots,n-1$, and an edge $(i,j)$ exists if $min\{(i-j)\ (mod\ n), (j-i)\ (mod\ n)\}\equiv x^c$ for some $x\in\mathbb{Z}_n$. There is a lot of literature on using this technique to bound Ramsey numbers, including the original Greenwood and Gleason and many more recent papers (one example).

Do we know if there is a tangible relationship here? Or is it just the "law of small numbers," a coincidence that the class of residue graphs happens to contain some Ramsey graphs for small $n$?

  • $\begingroup$ The intuition is that random graphs do pretty well, and these graphs are "close to random". There is even a suggestion that they might be "better than random". Making any of this intuition precise would be a huge breakthrough. $\endgroup$ – Ben Barber Mar 26 '17 at 10:28

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.