Ramsey's Theorem

One remarkable and easily stated result from combinatorics is Ramsey's Theorem. Expressed roughly, it tells us that complete disorder (in certain situations) is impossible. No matter how jumbled and chaotic you try to arrange certain objects, you will find yourself creating a very highly organized and structured object within it.

Here's an example. Suppose that you invite 6 random friends to a party. Although you know all of your friends, if you pick out two of the invited friends, they may or may not have been introduced. Surprisingly, no matter which 6 friends you invite, you will always be able to find 3 friends on the list such that among these 3, either:
1) All have been introduced to each other
2) None have been introduced to each other

That was a mouthful, so let's rephrase the problem in a different, more abstract, setting. Suppose that you place 6 pegs on a board, and you connect each pair of pegs with either a red piece of string or a green piece of string (you can use different colors for different pairs). Another way to state the above result is that no matter how you connect the pegs, you can always find either a red triangle (i.e. 3 pegs such that each is connected to the others via red string) or a green triangle.

Stop for a minute and think about how this formulation connects to the above situation. If you think of your 6 friends as pegs, a red string connecting 2 pegs representing the fact that the 2 corresponding friends have been introduced, and a green string connected 2 pegs representing the fact that the 2 corresponding friends have not been introduced, then both formulations say the same thing.

How can we convince ourselves of this result? Suppose that you have 6 pegs in front of you, and that each pair is connected by either a red string or a green string. Choose any peg that you like. Call it A. Now A is connected to the other 5 pegs with either red string or green string, so among these 5, we may choose 3 pegs, call them B,C, and D, such that AB, AC, and AD all have the same color (by AB I mean the string connecting pegs A and B) by the Pigeonhole Principle. Now if any of BC, BD, or CD have the same color as AB, then we are done (Suppose that BC has the same color as AB. Then the triangle ABC consists of just one color). Otherwise, each of BC, BD, and CD must have the same color (the color different from that of AB), and so the triangle BCD works.

Exercise: Find an arrangement of 5 pegs such that each pair is connected by either red or green string which contains no single-colored triangle. Hence, 6 is the smallest number we can use above.

What's going on here? Imagine that you were trying to connect 6 pegs without forming a single-colored triangle. As we start connecting with our string, we don't want to use one color too much, because after placing enough red string we would certainly guarantee the creation of a red triangle. Similarly, we don't want to place too much green string, or else we would certainly make a green triangle. When we are allowed to use both, we have to balance our use, and the above arguments show that 6 pegs is the breaking point.

Can we generalize this beyond single-colored triangles? In the parlance of Ramsey's Theorem, these single-colored triangles are called homogeneous (meaning of uniform structure or composition) or monochromatic (meaning of one color). Thus, we may say that 3 pegs form a monochromatic collection if the triangle formed by the three consists of just one color. What about a monochromatic collection of 4 pegs? Given 4 pegs, there are 6 strings that connect them to each other. Hence, they don't form just a 4-sided object, but actually a 4-sided object with 2 diagonals. We say that 4 pegs form a monochromatic collection if each of these 6 strings have the same color. Similarly, we say that k pegs forms a monochromatic collection if each of the strings connecting 2 pegs in the collection have the same color.

By similar reasoning (although quite a bit more complicated), one can argue that no matter how you connect up 18 pegs with red and green string, you can find a monochromatic collection of 4 pegs. Stated in our original formulation, we can express this by saying that if you invite 18 friends to a party, then you can be sure that you can pick out 4 friends such that among these 4, either they all have been introduced to each other, or none of them have been introduced to each other. Furthermore, 18 is the threshold, meaning that you can find an arrangement of 17 pegs without a monochromatic collection of 4 pegs.

One version of Ramsey's Theorem states that no matter which number k you choose, you can find a number n such that given any arrangement of n pegs, there must exist a monochromatic collection of k pegs. We will denote the smallest such n that works for a given k by R(k). The above results can be stated more succinctly by saying that R(3)=6 and R(4)=18. It is easy to see that R(1)=1 (given only 1 peg, there are no pieces of string, so it forms a monochromatic collection for vacuous reasons) and R(2)=2 (If you only have 2 pegs, there is only piece of string, so the 2 pegs form a monochramtic collection). Perhaps surprisingly, nobody knows the value of R(k) for any k larger than 4. The best results currently known state that R(5) is somewhere between 43 and 49 (inclusive) and R(6) is somewhere between 102 and 165. You might wonder why, given the incredible computing power at our disposal, we can not simply search through all arrangements of string for 43 pegs through 49 pegs to find the actual value of R(5). However, one can calculate that there are 2^903 (a number that has 272 decimal digits!) ways to arrange red and green string among 43 pegs, which is a number beyond ordinary comprehension (scientists estimate that there are about 80 digits in the number of electrons in the universe). By using symmetry, one can drastically lower the number of such arrangements a computer would have to look at, but even if we only had to examine 1 out of every 1 trillion configurations, we would still be left with over 2^864 arrangements (a number that has 261 digits!). Estimating the values of R(k) requires mathematical ingenuity in addition to brute force calculations.

Paul Erdos, one of the great mathematcians of the twentieth century, once quipped that if an alien being demanded that we tell it the value of R(5) or suffer the destruction of the Earth, then we should immediately set all mathematicians and computers to the task of calculating the value. However, if it demanded the value of R(6), then we should try to destroy it before it destroyed us.


Return to the Table of Contents.