Arrows, Ramsey numbers and the Party Problem

Here come the arrows! The notation $\alpha\rightarrow (\beta)^2_r$ means that every $r$-colored complete graph on $\alpha$ vertices contains a monochromatic complete subgraph with $\beta$ vertices. Using the notation $\omega$ for the cardinality of the natural numbers the abridged Ramsey theorems state that $\omega\rightarrow (\omega)^2_r$ and that $\forall n\exists m,m\rightarrow (n)^2_r$.

Now let us take a particular case: $n=3,r=2$. Our objective here is to prove that $6\rightarrow (3)^2_2$. In other words, if the edges of $K_6$ are $2$-colored then there exists a monochromatic $K_3$. Fix a vertex $v$ in $K_6$. From the $5$ edges emanating from $v$, at least three must share a color: call it $c$. Now if all the edges in triangle made by those three vertices are not colored $c$, we are done for we have found a monochromatic $K_3$ in the other color. If even one edge, say $xy$ among the triangle made by those three vertices is of color $c$ then we have a monochromatic $K_3$ colored $c$ with vertices $x,y$ and $v$.

The fact that $6\rightarrow (3)^2_2$ 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: $m\rightarrow (3)^2_2\forall m\ge 6$.

Is six the least such number? Indeed it is as the following graph demonstrates:

We note that there is no monochromatic triangle in the above $2$-colored $K_5$.

For a given $n$ the least such number $m,m\rightarrow (n)^2_r$ is called the diagonal Ramsey number $R(n,n)$. While such numbers are guaranteed to exist by Ramsey’s theorem, actually finding them is hard indeed. It is trivial to see that $R(1,1)=1$ and $R(2,2)=2$. Our proof above illustrates that $R(3,3)=6$. It has also been proven that $R(4,4)=18$. 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 $R(5,5)$, 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 $R(5,5)$ 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 $R(6,6)$. In that case, he believes, we should attempt to destroy the aliens.

In closing it may be remarked that the Ramsey number $R(m,n)$ is defined to be the least positive integer such that any $2$-coloring of $K_{R(m,n)}$ in two colors, say red and blue, contains either a red $K_m$ or a blue $K_n$. 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.