Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
What constitutes a simple explanation depends on what you know. What is your mathematical background? –  Omnomnomnom Jul 15 at 0:35
3  
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." –  Gerry Myerson Jul 15 at 2:59
add comment

1 Answer 1

up vote 28 down vote accepted

For one thing, our interest in Ramsey numbers grew out of an incredibly non-constructive proof. I.e. the original proof did little more than show that $R(s, t)<\infty$. Right off the bat, we are working with very little.

Consider the diagonal Ramsey numbers $R(s, s)$. Now, the smallest unknown diagonal Ramsey number is $R(5, 5)$. Let's say we suspect $R(5, 5) = 43$, which is the current lower bound. We would need to confirm that the relevant property holds for every possible $2$-coloring on $K_{43}$. Given that there are $\binom{43}{2} = 903$ edges, then we would need to somehow confirm the property holds for all $2^{903}$ possible colorings. This is a $272$ digit number! For comparison, this number is many orders of magnitude larger than the number of protons, neutrons, and electrons in the entire observable universe. Of course, it's possible we can whittle down this number significantly, but it would still be unimaginably gargantuan.

Brute force is obviously 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. With this method, it's possible to show (rather easily) that $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 $R(s, t) \leq \binom{s+t-2}{s-1}$. When $s=t$, we get $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.


Footnote: If you're interested, I'd highly recommend looking into Erdős' proof of the lower bound (it's one of my favorites). The idea that one uses probability to arrive at a certain conclusion is really quite fascinating.

share|improve this answer
    
That's what I was looking for. Thank you a lot! –  Fred Funks Jul 15 at 7:12
    
@FredFunks, Glad I could help! –  Kaj Hansen Jul 15 at 7:53
2  
"[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! –  David Richerby Jul 15 at 8:28
    
"Bigger than astronomical..." That's a phrase you'd be hard-pressed to hear outside of Ramsey theory. :) –  Kaj Hansen Jul 15 at 8:29
    
...unless you have a look at some cryptographic problems, which are designed to have "bigger than astronomical" difficulty ;) –  Massimo Jul 15 at 13:36
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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