I'm looking for a 2-page paper on a lower bound of Ramsey number $R(a,b)$ for some constants $a$ and $b$. The paper was published in 80s or 90s. I googled it for a few days, but I cannot find the paper.

The paper improves the lower bound of $R(a,b)$ to $n + 1$ by constructing a graph with $n$ vertices without $K_a$ in one color (red) nor $K_b$ in the other color (blue). IIRC $20 < n < 30$. It constructs the graph in the following steps:

  • Step 1. Place $n$ vertices on a circle.
  • Step 2. If $u, v \in V$ has odd number of vertices between them along the circle, color $uv \in E$ to one color (red). Otherwise, color $uv$ to the other color (blue).
  • Step 3. There is a list of a dozen of edges to change the color.

Can anyone help me to find this paper?

  • 7
    $\begingroup$ Memory is a fickle friend, it something something in the end. $\endgroup$
    – Ben McKay
    Sep 27 at 15:38
  • 1
    $\begingroup$ To me, most of this sounds like Exoo, "A Lower Bound For R(5,5)", except for Step 2. $\endgroup$ Sep 29 at 23:27
  • $\begingroup$ Please use a high-level tag like "co.combinatorics". I added this tag now. $\endgroup$
    – GH from MO
    Oct 5 at 23:47

The methodology you are looking for is referred as "cyclic Ramsey graphs", or "circulant coloring". You could also look at Distance Ramsey number, a generalization of circulant coloring.

In the 1983 article "A survey of bounds for classical Ramsey numbers", the authors, Chung and Grinstead state the following, (page 6 after Theorem 2.4).

Excerpt from Chung and Grinstead - A survey of bounds for classical Ramsey numbers

The short cited article Greenwood and Gleason - Combinatorial relations and chromatic graphs is older than you request, but it should be the correct methodology. In there the author proved that $n(3,5)>13$ and some other inequalities with this methodology. It might not be the exact one you were looking for but it should allow you to find the correct one.

Excerpt from Greenwood and Gleason - Combinatorial relations and chromatic graphs

In case you don't know it, Radziszowski maintains a survey on "Small Ramsey numbers" that probably contains the article you are looking for.


I might have found it, let me know if it's the right paper or not: enter image description here

Edited after the comment below: there is at least another one paper potentially relevant: Guldan - New lower bounds of some diagonal Ramsey numbers.

  • 1
    $\begingroup$ For the readers' convenience, here is the link: core.ac.uk/download/pdf/82482174.pdf, but the proof therein does not look entirely as the OP says (but maybe that's just a memory issue). $\endgroup$
    – Alex M.
    Sep 27 at 19:44
  • $\begingroup$ I think 2 pages papers on the subject published between 1980 and 1999 must not be that common. $\endgroup$ Sep 27 at 19:46

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.