prob017: Ramsey numbers

proposed by Toby Walsh
tw@cs.york.ac.uk

Results

Stanislaw Radziszowski has written an up-to-date survey for all types of Ramsey numbers.

The special case of R(k,k) numbers has attracted perhaps the most attention. R(4,4) has been shown to equal 18. R(5,5) is only known to lie between 43 and 49. This is a very difficult combinatorial problem.

Erdos related the following anecdote: "Aliens invade the earth and threaten to obliterate it in a year's time unless human beings can find the Ramsey number for red five and blue five [that is, 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 the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack. (Graham, Ronald L. and Joel H. Spencer. Ramsey Theory. Scientific American July 1990: 112-117).