14.2: Ramsey Theory

Although Ramsey Theory is an important part of Combinatorics (along with Enumeration, Graph Theory, and Design Theory), this course will touch on it only very lightly. The basic idea is that if a very large object is cut into two pieces (or a small number of pieces), then at least one of the pieces must contain a very nice subset. Here is an illustration.

Example \(\PageIndex{1}\)

Suppose each edge of \(K_6\) is coloured either red or blue. Show that either there is a triangle whose edges are all red, or there is a triangle whose edges are all blue. That is, \(K_6\) contains a copy of \(K_3\) that has all of its edges of the same colour. For short, we say that \(K_6\) contains a monochromatic triangle.

Solution

Choose some vertex \(v\). Since the \(5\) edges incident with \(v\) are coloured with only two colours, the generalized Pigeonhole Principle implies that three of these edges are the same colour. For definiteness, let us say that three edges \(vu_1\), \(vu_2\), and \(vu_3\) are all red.

Now, \(u_1\), \(u_2\), and \(u_3\) are the vertices of a copy of \(K_3\) that is inside \(K_6\). If all three edges of this \(K_3\) are blue, then we have our desired monochromatic triangle (namely, a blue triangle). So we may assume that one of the edges is red; say, \(u_1u_2\) is red. Since the edges \(vu_1\) and \(vu_2\) are also red, we see that \(v\), \(u_1\), and \(u_2\) are the vertices of a monochromatic triangle (namely, a red triangle).

Definition: Ramsey Number

Let \(k\), \(\ell ∈ \mathbb{N}^+\).

1) Suppose each edge of \(K_n\) is coloured either red or blue. We say there is a red copy of \(K_k\) if there exist \(k\) vertices \(u_1, . . . , u_k\), such that the edge \(u_iu_j\) is red for all \(i\) and \(j\) (with \(i \neq j\)). Similarly, we say there is a blue copy of \(K_{\ell}\) if there exist \(\ell\) vertices \(v_1, . . . , v_{\ell}\), such that the edge \(v_iv_j\) is blue for all \(i\) and \(j\) (with \(i \neq j\)).

2) The Ramsey number \(R(k, \ell)\) is the smallest number \(n\), such that whenever each edge of \(K_n\) is coloured either red or blue, there is always either a red copy of \(K_k\), or a blue copy of \(K_{\ell}\).

Example \(\PageIndex{2}\)

1) We have \(R(k, 1) = 1\) for all \(k\). This is because \(K_1\) has no edges, so, for any colouring of any \(K_n\), it is true (vacuously) that all of the edges of \(K_1\) are blue.

2) We have \(R(k, 2) = k\) for all \(k\). Namely, if some edge is blue, then there is a blue \(K_2\), while if there are no blue edges, then the entire graph is a red \(K_k\).

3) We have \(R(3, 3) = 6\). To see this, note that Example 14.2.1 shows \(R(3, 3) ≤ 6\), while the edge-colouring of \(K_5\) at right has no monochromatic triangle (because the only monochromatic cycles are of length \(5\)), so \(R(3, 3) > 5\).

4) We have \(R(k, \ell) = R(\ell, k)\) for all \(k\) and \(\ell\). Namely, if every colouring of \(K_n\) has either a red \(K_k\) or a blue \(K_{\ell}\), then we see that every colouring of \(K_n\) must have either a red \(K_{\ell}\) or a blue \(K_k\), just by switching red and blue in the colouring.

5) If \(k ≤ k'\) and \(\ell ≤ \ell'\), then \(R(k, \ell) ≤ R(k' , \ell')\). Namely, we have a colouring of \(K_n\) that contains either a red \(K_{k'}\) or a blue \(K_{\ell'}\). Since \(k ≤ k'\) and \(\ell ≤ \ell'\), we know that any \(K_{k'}\) contains a copy of \(K_k\), and any \(K_{ \ell'}\) contains a copy of \(K_{\ell} \).

It is not at all obvious that \(R(k, \ell)\) exists: theoretically, \(R(4, 4)\) might not exist, because it might be possible to colour the edges of a very large \(K_n\) in such a way that there is no monochromatic \(K_4\). Fortunately, the following extension of the proof of Example 14.2.1 implies that \(R(k, \ell )\) does exist for all \(k\) and \(\ell\). In fact, it provides a bound on how large \(R(k, \ell)\) can be (see Exercise 14.2.1(3) below).

Proposition \(\PageIndex{1}\)

\(R(k, \ell) ≤ R(k − 1, \ell) + R(k, \ell − 1)\) for all \(k\), \( \ell ≥ 2\)

Proof

Let \(n = R(k − 1, \ell) + R(k, \ell − 1)\), and suppose each edge of \(K_n\) is coloured either red or blue. We wish to show there is either a red \(K_k\) or a blue \(K_{ \ell}\).

Choose some vertex \(v\) of \(K_n\). Then the number of edges incident with \(v\) is

\[n − 1 = R(k − 1, \ell) + R(k, \ell − 1) − 1 > (R(k − 1, \ell) − 1) + (R(k, \ell − 1) − 1),\]

so the very generalized Pigeonhole Principle implies that either \(R(k − 1, \ell)\) of these edges are red, or \(R(k, \ell − 1)\) of these edges are blue.

For definiteness, let us assume that the edges \(vu_1, vu_2, . . . , vu_r\) are all blue, where \(r = R(k, \ell − 1)\). Now, \(u_1, u_2, . . . , u_r\) are the vertices of a copy of \(K_r\) that is inside \(K_n\). Since \(r = R(k, \ell − 1)\), we know that this \(K_r\) contains either a red \(K_k\) or a blue \(K_{\ell−1}\).

If it contains a red \(K_k\), then we have the desired red \(K_k\). So we may assume \(u_1, . . . , u_{\ell−1}\) are the vertices of a blue \(K_{\ell-1}\). Since the edges \(vu_1, vu_2, . . . , vu_{\ell−1}\) are also blue, we see that \(v, u_1, u_2, . . . , u_{\ell -1}\) are the vertices of the desired blue \(K_{\ell}\).

Exercise \(\PageIndex{1}\)

1) Show \(R(3, 4) > 6\).

2) Using Proposition 14.2.1 and the values of \(R(k, \ell)\) given in Example 14.2.2, find the best upper bound you can on \(R(k, \ell)\) for \(3 ≤ k ≤ \ell ≤ 6\).

3) Show \(R(k, \ell) ≤ 2^{k+\ell}\) for all \(k\) and \(\ell\).

[Hint: Use Proposition 14.2.1 and induction on \(k + \ell\).]

4) It is known that \(40 ≤ R(3, 10) ≤ 42\). Using this information, what can you say about \(R(3, 11)\)?

5) Show there are at least two monochromatic triangles in every colouring of the edges of \(K_6\) with two colours.

[Hint: Show that there must either be two red (say) triangles, or a red triangle and a blue edge whose endvertices are not in the triangle. Then show that any colouring of the edges joining the red triangle with the blue edge creates either a blue triangle or a second red triangle.

Note

The exact value of \(R(k, \ell)\) seems to be extremely difficult to find, except for very small values of \(k\) and \(\ell\). For example, although it has been proved that \(R(4, 4) = 18\) and \(R(4, 5) = 25\), no one has been able to determine the precise value of \(R(k, \ell)\) for any situation in which \(k\) and \(\ell\) are both at least \(5\). The legendary combinatorist Paul Erdös (\(1913\)–\(1996\)) said that it would be hopeless to try to calculate the exact value of \(R(6, 6)\), even with all of the computer resources and brightest minds in the whole world working on the problem for a year. (We do know that \(R(6, 6)\) is somewhere between \(102\) and \(165\).) For more information about the values that have been calculated, see the Wikipedia article on Ramsey’s theorem.

Exercise \(\PageIndex{2}\)

The edges of \(K_n\) can also be coloured with more than two colours.

1) Show every colouring of the edges of \(K_{17}\) with \(3\) colours has a monochromatic triangle.

2) Suppose there is a monochromatic triangle in every colouring of the edges of \(K_n\) with \(c\) colours. Show that if \(N −1 > (c+ 1)(n−1)\), then every colouring of the edges of \(K_N\) with \(c + 1\) colours has a monochromatic triangle.

Similar arguments (combined with induction on the number of colours) establish the following very general result.

Theorem \(\PageIndex{1}\): Ramsey's Theorem

Given \(c\) colours and fixed sizes \(n_1, . . . , n_c ≥ 1\), there is an integer

\[r = R(n_1, . . . , n_c)\]

such that for any \(c\)-colouring of the edges of \(K_r\), there must be some \(i ∈ \{1, . . . , c\}\) such that \(K_r\) has a subgraph isomorphic to \(K_{ni}\) all of whose edges have been coloured with colour \(i\).

Proof

We will prove this result by induction on \(c\), the number of colours.

Base cases: When \(c = 1\), all edges of \(K_r\) are coloured with our single colour, so if we let \(r = R(n_1) = n_1\), the whole graph is the \(K_{n_1}\) all of whose edges have been coloured with colour \(1\).

We will also require \(c = 2\) to be a base case in our induction. In order to prove this second base case, we perform a second proof by induction, this time on \(n_1 + n_2\). To make the proof easier to read, we’ll call the two colours in any \(2\)-edge-colouring red and blue, and if all of the edges of a \(K_i\) have been coloured with one colour, we’ll simply call it a red \(K_i\), or a blue \(K_i\).

Base case for the second induction: We’ll actually prove a lot of base cases all at once. Since \(n_1\) and \(n_2\) are the number of vertices of a complete graph, we must have \(n_1\), \(n_2 ≥ 1\). A \(K_1\) has no edges, so vacuously its edges have whichever colour we desire. Thus if \(n_1 = 1\) or \(n_2 = 1\), we have \(r = R(n_1, n_2) = 1\), since for any \(2\)-edge-colouring of \(K_1\), there is a red \(K_1\) and a blue \(K_1\).

Inductive step for the second induction: We begin with the inductive hypothesis. Let \(k ≥ 2\) be arbitrary. Assume that for every \(k_1, k_2 ≥ 1\) such that \(k_1 + k_2 = k\), there is some integer \(r = R(k_1, k_2)\) such that for any \(2\)-edge-colouring of the edges of \(K_r\), there is a subgraph that is either a red \(K_{k_1}\) or a blue \(K_{k_2}\).

Let \(n_1\), \(n_2 ≥ 1\) such that \(n_1 + n_2 = k + 1\). If either \(n_1 = 1\) or \(n_2 = 1\), then this was one of our base cases and the proof is complete, so we may assume that \(n_1\), \(n_2 ≥ 2\). Therefore, \(n_1 −1\), \(n_2 −1 ≥ 1\), and \(n_1 +n_2 −1 = k\). Now, by our inductive hypothesis, there is some integer \(r1 = R(n_1, n_2 − 1)\) such that for any \(2\)-edge-colouring of the edges of \(K_{r_1}\), there is a subgraph that is either a red \(K_{n_1}\) or a blue \(K_{n_2−1}\). We can also use our inductive hypothesis to conclude that there is some integer \(r_2 = R(n_1 − 1, n_2)\) such that for any \(2\)-edge-colouring of the edges of \(K_{r_2}\), there is a subgraph that is either a red \(K_{n_1−1}\) or a blue \(K_{n_2}\).

We claim that \(R(n_1, n_2) ≤ r_1 + r_2\). We will show this by proving that any \(2\)-edge-colouring of the edges of \(K_{r_1}+r_2\) must have a subgraph that is either a red \(K_{n_1}\) or a blue \(K_{n_2}\).

Consider a complete graph on \(r_1 +r_2\) vertices whose edges have been coloured with red and blue. Choose a vertex \(v\), and divide the remaining vertices into two sets: \(u ∈ V_1\) if the edge \(uv\) has been coloured red, and \(u ∈ V_2\) if the edge \(uv\) has been coloured blue. Since this graph has

\[r_1 + r_2 = |V_1| + |V_2| + 1\]

vertices, we must have either \(|V_1| ≥ r_2\), or \(|V_2| ≥ r_1\).

Suppose first that \(|V_1| ≥ r_2\). Since \(r_2 = R(n_1 − 1, n_2)\), the subgraph whose vertices are the elements of \(V_1\) has a subgraph that is either a red \(K_{n_1−1}\) or a blue \(K_{n_2}\). In the latter case, this subgraph is also in our original \(K_{r_1+r_2}\) and we are done. In the former case, the subgraph whose vertices are the elements of \(V_1 ∪ \{v\}\) has a red \(K_{n_1}\) and we are done.

Suppose now that \(|V_2| ≥ r_1\) (the proof is similar). Since \(r_1 = R(n_1, n_2 − 1)\), the subgraph whose vertices are the elements of \(V_2\) has a subgraph that is either a red \(K_{n_1}\) or a blue \(K_{n_2−1}\). In the former case, this subgraph is also in our original \(K_{r_1+r_2}\) and we are done. In the latter case, the subgraph whose vertices are the elements of \(V_2 ∪ \{v\}\) has a blue \(K_{n_2}\) and we are done.

By the Principle of Mathematical Induction, for every \(n_1\), \(n_2 ≥ 1\), there is some integer \(r = R(n_1, n_2)\) such that for any colouring of the edges of \(K_r\), there is a subgraph that is either a red \(K_{n_1}\) or a blue \(K_{n_2}\).

This second proof by induction completes the proof of the second base case for our original induction on \(c\), the number of colours. We are now ready for the inductive step for our original proof by induction.

Inductive step: We begin with the inductive hypothesis. Let \(m ≥ 2\) be arbitrary. Assume that for every \(k_1, . . . , k_m ≥ 1\), there is an integer \(r = R(k_1, . . . , k_m)\) such that for any mcolouring of the edges of \(K_r\), there must be some \(i ∈ \{1, . . . , m\}\) such that \(K_r\) has a subgraph isomorphic to \(K_{k_i}\), all of whose edges have been coloured with colour \(i\).

Let \(n_1, . . . , n_{m+1}\) be arbitrary. Take a complete graph on

\[r = R(n_1, . . . , n_{m−1}, R(n_m, n_{m+1}))\]

vertices, and colour its edges with \(m + 1\) colours. Temporarily consider the colours \(m\) and \(m + 1\) to be the same, resulting in a colouring of the edges with \(m\) colours. By our inductive hypothesis, there must either be some \(i ∈ \{1, . . . , m − 1\}\) such that our \(K_r\) has a subgraph isomorphic to \(K_{n_i}\), all of whose edges have been coloured with colour \(i\), or \(K_r\) has a subgraph isomorphic to \(K_{R(n_m,n_{m+1})}\) all of whose edges have been coloured with the \(m^{\text{th}}\) colour (where this \(m^{\text{th}}\) colour is really the combination of the colours \(m\) and \(m + 1\)).

If there is some \(i ∈ \{1, . . . , m − 1\}\) such that our \(K_r\) has a subgraph isomorphic to \(K_{n_i}\), all of whose edges have been coloured with colour \(i\), then we are done. The possibility remains that our \(K_r\) has a subgraph isomorphic to \(K_{R(n_m,n_{m+1})}\) all of whose edges have been coloured with either colour \(m\) or colour \(m + 1\). But by our base case for \(c = 2\), this graph must have either a subgraph isomorphic to \(K_{n_m}\) all of whose edges have been coloured with colour \(m\), or a subgraph isomorphic to \(K_{n_{m+1}}\) all of whose edges have been coloured with colour \(m + 1\). This completes the inductive step.

By the Principle of Mathematical Induction, for every \(c ≥ 1\) and fixed sizes \(n_1, . . . , n_c ≥ 1\), there is an integer \(r = R(n_1, . . . , n_c)\) such that for any \(c\)-colouring of the edges of \(K_r\), there must be some \(i ∈ \{1, . . . , c\}\) such that \(K_r\) has a subgraph isomorphic to \(K_{n_i}\) all of whose edges have been coloured with colour \(i\).

Exercise \(\PageIndex{3}\)

1. Find \(R(2, 2, 3)\).
2. Find \(R(2, 4)\).
3. Find a \(2\)-edge-colouring of \(K_6\) that does not have a \(K_4\) of either colour.

Exercise \(\PageIndex{4}\)

(Schur’s Theorem) Let \(c ∈ \mathbb{N}^+\), and let \(N = R(3, . . . , 3)\) where there are \(c\) entries (all equal to \(3\)). If \(\{A_1, A_2, . . . , A_c\}\) is any partition of \(\{1, 2, . . . , N\}\) into \(c\) subsets, show that some \(A_i\) contains three integers \(x\), \(y\), and \(z\), such that \(x + y = z\).

[Hint: The vertices of \(K_N\) are \(1, 2, . . . , N\). Put colour \(i\) on each edge \(uv\) with \(|u − v| ∈ A_i\). If \(u\), \(v\), \(w\) are the vertices of a monochromatic triangle of colour \(i\), with \(u > v > w\), then \(\{u − v, v − w, u − w\} ⊆ A_i\), and we have \((u − v) + (v − w) = u − w\).]