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.

Advertisements

1 Comment

Filed under Combinatorics, Miscellaneous, Ramsey theory

One response to “Arrows, Ramsey numbers and the Party Problem

  1. Pingback: On unabridged versions of Ramsey’s theorem | Notes on Mathematics

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s