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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.