Ramsey Theory: Foundations, Generalizations, Key Results

Ramsey theory has its origins in a very nice riddle

Consider a party of 6 people. Any two of these six will either be meeting each other for the first time (in which case they are strangers) or they will know each other (in which case they are friends). Show that in this party of 6 people there are either 3 who are mutual strangers or 3 who are mutual friends. Show that the same does not hold in a party of 5 people.

Try to prove this riddle yourself

Then we can do what mathematicians do best: generalize. This generalization was done by Ramsey. We say that $R(m,n) = v$ if, in a party of $v$ people, there are at least $m$ people who are mutual friends or at least $n$ people who are mutual strangers, while the same does not hold in a party with $v-1$ people. Our riddle at the start states that $R(3,3)=6$.

But why should there be a number $v$ such that $R(m,n) = v$? Why should this have a solution at all? Why should there exist a party size where 100 people are mutual friends or 1000 people are mutual strangers? These existence statements are proved in Ramsey’s theorem. Ramsey also gives an upper bound on $v$.

Proof of the basic recurrence

The key inequality is

$R(m,n)\leq R(m-1,n) + R(m,n-1)$.

Using this recurrence and a simple induction yields Ramsey’s theorem. To prove the recurrence, take a party with $R(m-1,n) + R(m,n-1)$ guests and pick an arbitrary guest, whom we call Mister T. For every other guest, either Mister T knows that person or Mister T does not know that person. Thus the remaining guests split into two groups: those who know Mister T and those who do not know Mister T.

Write

$$R(m-1,n) + R(m,n-1) = \text{number of people knowing Mister T} + \text{number of people not knowing Mister T} + 1$$

Therefore either the number of people knowing Mister T is at least $R(m-1,n)$ or the number of people not knowing Mister T is at least $R(m,n-1)$.

If the first group has at least $R(m-1,n)$ people, then among them there are either $m-1$ mutual friends or $n$ mutual strangers. In the latter case we have $n$ mutual strangers in the whole party. In the former case those $m-1$ friends together with Mister T form $m$ mutual friends.

Analogously, if the second group has at least $R(m,n-1)$ people, then among them there are either $m$ mutual friends or $n-1$ mutual strangers. In the first case we have $m$ friends in the party. In the second case those $n-1$ strangers together with Mister T form $n$ mutual strangers. This completes the proof of the recurrence.

Three labels and the multicolor formulation

Ramsey proved a more general result when there are more than two relations. For example, people can be friends, strangers, or enemies. If in a party with $v$ people there are at least $m$ friends, or at least $n$ strangers, or at least $k$ enemies, and this does not hold in a party with $v-1$ people, then we write $R(m,n,k) = v$. The crucial inequality is

$$R(m,n,k) \leq R(m,R(n,k)).$$

Indeed, in a party with $R(m,R(n,k))$ people there are either $m$ friends or $R(n,k)$ non-friends. In the latter case the non-friends among themselves give either $n$ strangers or $k$ enemies. In either case one of the desired monochromatic groups exists.

More generally, consider the standard graph formulation: every unordered pair of $v$ vertices is colored with one of $c$ colors. We write $v = R(n_1,\dots,n_c)$ if any coloring of the edges of the complete graph on $v$ vertices with $c$ colors yields, for some color $i$, a monochromatic complete subgraph on $n_i$ vertices, while this property fails for $v-1$. One can show that for any finite list of positive integers $n_1,\dots,n_c$ there exists such a finite $v$.

Known values and computational results

Not many exact Ramsey numbers are known. We have $R(1,n)=R(n,1)=1$ for every $n$ and $R(2,n)=R(n,2)=n$ for every $n$; these are straightforward to verify. Aside from these trivial cases, only a few values are known exactly. For example, $R(3,3)=6$ (the party riddle) and $R(4,4)=18$. The value $R(5,5)$ is not known exactly, but it is known to lie between $43$ and $49$.

Heuristically illustrating the difficulty, a widely quoted anecdote attributed to a contemporary of Erdős states:

“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.”

For three or more colors the situation is even harder; apart from trivial cases, only very few exact multicolor Ramsey numbers are known. For example, $R(3,3,3)=17$.

Infinite Ramsey theory

There is also infinite Ramsey theory. For instance, consider a countably infinite set of vertices and color each unordered pair with one of $c$ colors. Then there exists an infinite subset of vertices all of whose pairs receive the same color. More generally, if every $n$-tuple of vertices is colored with one of finitely many colors, then there is an infinite subset on which all $n$-tuples have the same color. These infinite versions admit natural extensions to larger cardinalities.

From Ramsey to the Boolean Pythagorean triples problem

Ramsey-type questions ask: given a structure partitioned into finitely many pieces, how large must the whole structure be to guarantee that one piece contains a specified substructure? A striking modern example is the Boolean Pythagorean triples problem, resolved in May 2016.

Three integers form a Pythagorean triple if they are the side lengths of a right triangle. Consider coloring each natural number either red (Trump) or blue (Clinton). Is it possible to color the naturals so that no Pythagorean triple $(a,b,c)$ is monochromatic? Heule, Kullman, and Marek showed that it is not possible: any 2-coloring of the naturals yields a monochromatic Pythagorean triple. They also showed that a 2-coloring of {1,…,7824} avoiding monochromatic triples exists, while every 2-coloring of {1,…,7825} contains a monochromatic triple.

The proof was obtained by reducing the problem to about one trillion cases and then checking these cases with a supercomputer for roughly two days. If written out in full, this would be one of the largest explicit proofs known.

Computer-assisted proofs remain philosophically controversial. Such proofs settle truth values definitively, but they often provide little human-understandable insight into why a statement holds. Thus one can say the Boolean Pythagorean triples problem is solved in the sense that its truth value is settled, while the conceptual explanation for the threshold at 7825 remains elusive.