Here come the arrows! The notation means that every -colored complete graph on vertices contains a monochromatic complete subgraph with vertices. Using the notation for the cardinality of the natural numbers the abridged Ramsey theorems state that and that .
Now let us take a particular case: . Our objective here is to prove that . In other words, if the edges of are -colored then there exists a monochromatic . Fix a vertex in . From the edges emanating from , at least three must share a color: call it . Now if all the edges in triangle made by those three vertices are not colored , we are done for we have found a monochromatic in the other color. If even one edge, say among the triangle made by those three vertices is of color then we have a monochromatic colored with vertices and .
The fact that is also referred to as the solution of the party problem: Prove that in any gathering of six people there are three mutual friends, or three mutual strangers. By representing the people as vertices and their relationships via the colors on the edges connecting them we easily see that a monochromatic triangle is guaranteed and therefore the result holds. It is also obvious that the gathering may contain more then six people, a monochromatic triangle is still guaranteed within (in fact, it will only become more likely with more people). In other words: .
We note that there is no monochromatic triangle in the above -colored .
For a given the least such number is called the diagonal Ramsey number . While such numbers are guaranteed to exist by Ramsey’s theorem, actually finding them is hard indeed. It is trivial to see that and . Our proof above illustrates that . It has also been proven that . However all efforts to find out the exact value of any other diagonal Ramsey number have failed. It is one of those problems, which are easily stated but extremely difficult to attack.
Regarding , Joel Spencer comments in his book, Ten lectures on the Probabilistic Method:
Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for . In that case, he believes, we should attempt to destroy the aliens.
In closing it may be remarked that the Ramsey number is defined to be the least positive integer such that any -coloring of in two colors, say red and blue, contains either a red or a blue . This definition also has the natural generalization for more then two colors. Although the existence of all Ramsey numbers is guaranteed by Ramsey’s theorem, only few have been discovered so far.