27
$\begingroup$

Can someone explain in a simple way why there are so few known exact Ramsey numbers? I guess it's because there are no efficient algorithms for this task, but are there so many combinations to test?

And an additional question: How are the bounds determined? Why do the bounds, that are known, have those values? Why not i.e. try to take a lower number for the upper bound for some 2-coloring?

$\endgroup$
  • 2
    $\begingroup$ What constitutes a simple explanation depends on what you know. What is your mathematical background? $\endgroup$ – Omnomnomnom Jul 15 '14 at 0:35
  • 7
    $\begingroup$ This is not an answer, but a relevant story that people should know. Paul Erdos told this story: "Aliens invade the earth and threaten to obliterate it in a year's time unless human beings can find $R(5,5)$. We could marshal the world's best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded $R(6,6)$, however, we would have no choice but to launch a preemptive attack." $\endgroup$ – Gerry Myerson Jul 15 '14 at 2:59
38
$\begingroup$

Unfortunately, the original proof that Ramsey numbers exist (as in, are finite) was non-constructive, so mathematicians have been fighting an uphill battle from the beginning. Consider the diagonal Ramsey numbers $R(s, s)$. The smallest of these which remains unknown is $R(5, 5)$, so let's say we suspect $R(5, 5) = 43$—the current lower bound. We would need to confirm that the relevant property holds for every possible $2$-coloring on $K_{43}$. Since this graph has $\displaystyle \binom{43}{2} = 903$ edges, there are $2^{903}$ possible colorings. This is a $272$ digit number! For comparison, this number is many orders of magnitude larger than the total number of protons, neutrons, and electrons in the entire observable universe. Of course, it's possible we can whittle this number down a bit with some ingenuity (for instance, some colorings are equivalent up to symmetry), but it would still be unimaginably gargantuan. Brute force is out of the question, even for the most powerful supercomputers.


Bounds:

The work on lower bounds for diagonal Ramsey numbers improves upon the original lower bound Paul Erdős found using his probabilistic method$^\dagger$. With this method, it's possible to show (rather easily) that $\displaystyle R(s, s) \geq \lfloor 2^{\frac{s}{2}} \rfloor$. Of course, the general lower bound has since been improved, but it still has an exponential growth factor of $\sqrt{2}$.

A relatively decent upper bound for diagonal Ramsey numbers can be proven using the same approach as in the proof that $R(s, t) < \infty$. That is, we can show $\displaystyle R(s, t) \leq \binom{s+t-2}{s-1}$. When $s=t$, we get $\displaystyle R(s, s) \leq \binom{2s-2}{s-1}$, which grows exponentially with a growth factor of $4$. The current upper bound has been improved a bit, but still has the same exponential growth factor.


$^\dagger$ I'd highly recommend checking out this proof; it's one of my favorites. A downright ingenious application of probability theory to this area of math. Find it here.

$\endgroup$
  • $\begingroup$ That's what I was looking for. Thank you a lot! $\endgroup$ – Fred Funks Jul 15 '14 at 7:12
  • $\begingroup$ @FredFunks, Glad I could help! $\endgroup$ – Kaj Hansen Jul 15 '14 at 7:53
  • 2
    $\begingroup$ "[W]e can whittle down this number significantly, but it would still be astronomical." Still bigger than astronomical, since it would still be much bigger than the number of atoms in the visible universe! $\endgroup$ – David Richerby Jul 15 '14 at 8:28
  • $\begingroup$ "Bigger than astronomical..." That's a phrase you'd be hard-pressed to hear outside of Ramsey theory. :) $\endgroup$ – Kaj Hansen Jul 15 '14 at 8:29
  • $\begingroup$ ...unless you have a look at some cryptographic problems, which are designed to have "bigger than astronomical" difficulty ;) $\endgroup$ – Massimo Jul 15 '14 at 13:36

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.