18
$\begingroup$

The reason for the gorgeous simplicity of the classic proofs of $R(3,3)$, $R(4,4)$, $R(3,4)$ and $R(3,5)$ is that essentially all you need is the trivial bound and a picture.

But for bigger Ramsey numbers, the bound $R(p,q)\leq R(p-1,q)+R(p,q-1)$ is not best anymore, which adds to the complication of having an increasingly intractable graphs involved.

For $R(3,6)$ and $R(3,7)$, you can replace it with another simple bound, and the construction of an explicit coloring does the rest.

(Actually, I don't think I've seen a proof of $R(3,7)\leq 23$. The original paper by Kalbfleisch proves that $R(3,7)\geq 23$, and mentions a communication by Jack Graver and Jim Yackel at a conference for the other inequality. Yet Kalbfleisch is usually credited with the proof (see here por example))

(Actualization. As j.c. mentions in the comments, the $R(3,7)\leq 23$ bound by Graver and Yackel was published two years, see the paper here, page 21, computation O (the notation is shifted by 1)).

In comparison with those, the proof of the other known Ramsey numbers, $R(3,8)$, $R(3,9)$ and $R(4,5)$ seem extremely unenlightening. Obviously the size of the colorings make neccesary extensive computation, so perhaps the proofs are as good as possible. But still I feel like I should ask.

Is there a simpler or more intuitive proof of any of those three results?

Since all three original papers are avaible online, I'll include them for easier reference:

$\endgroup$
  • $\begingroup$ At least as far as R(3,7) is concerned, it seems the source cited by your Mathworld link is Kalbfleisch's Ph.D. thesis. There's also a paper of Graver and Yackel including a bound for R(3,7) (they use a notation which is shifted by 1) sciencedirect.com/science/article/pii/S0021980068800389 that also cites Kalbfleisch's thesis. I haven't read it so I don't know if it will help you. $\endgroup$ – j.c. Oct 15 '15 at 17:48
  • $\begingroup$ It is a joke that if out planet earth was invaded by aliens, and the ask for the exact value of R(5,5), we should add together all of our computing capabilities to do it. but if they asked for R(6.6) we should simply give up and let them do what they do! $\endgroup$ – Mohemnist Nov 3 '15 at 17:23
  • 1
    $\begingroup$ A joke due to the one and only Erdos. $\endgroup$ – Bernardo Recamán Santos Feb 23 '16 at 4:49

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.