Skip to main content

Section 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. As noted in Section 1.3, this branch of combinatorics is named for Frank Plumpton Ramsey (1903—1930). 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.

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\text{.}\) 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\text{,}\) \(v u_2\text{,}\) and \(v u_3\) are all red.

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

Definition 14.2.2.

Let \(k,\ell \in \natural^+\text{.}\)

  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,\ldots,u_k\text{,}\) 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,\ldots,v_\ell\text{,}\) 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\text{,}\) such that whenever each edge of \(K_n\) is coloured either red or blue, there is always either a red copy of \(K_k\text{,}\) or a blue copy of \(K_\ell\text{.}\)

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

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

  3. We have \(R(3,3) = 6\text{.}\) To see this, note that Example 14.2.1 shows \(R(3,3) \le 6\text{,}\) while there is no monochromatic triangle in the edge-colouring of \(K_5\) pictured below (because the only monochromatic cycles are of length \(5\)), so \(R(3,3) > 5\text{.}\)

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

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

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\text{.}\) Fortunately, the following extension of the proof of Example 14.2.1 implies that \(R(k,\ell)\) does exist for all \(k\) and \(\ell\text{.}\) In fact, it provides a bound on how large \(R(k,\ell)\) can be (see Exercise 14.2.5.3 below).

Let \(n = R(k-1,\ell) + R(k, \ell-1)\text{,}\) 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\text{.}\)

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

\begin{equation*} n - 1 = R(k-1,\ell) + R(k, \ell-1) - 1 > \bigl( R(k-1,\ell) - 1 \bigr) + \bigl( R(k, \ell-1) -1 \bigr)\text{,} \end{equation*}

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,\ldots, vu_r\) are all blue, where \(r = R(k,\ell-1)\text{.}\) Now, \(u_1, u_2,\ldots,u_r\) are the vertices of a copy of \(K_r\) that is inside \(K_n\text{.}\) Since \(r = R(k,\ell-1)\text{,}\) we know that this \(K_r\) contains either a red \(K_k\) or a blue \(K_{\ell-1}\text{.}\)

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

⬛

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

  2. Using Proposition 14.2.4 and the values of \(R(k,\ell)\) given in Example 14.2.3, find the best upper bound you can on \(R(k,\ell)\) for \(3 \le k \le \ell \le 6\text{.}\)

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

    Use Proposition 14.2.4 and induction on \(k + \ell\text{.}\)

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

  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.

Remark 14.2.6.
The exact value of \(R(k,\ell)\) seems to be extremely difficult to find, except for very small values of \(k\) and \(\ell\text{.}\) For example, although it has been proved that \(R(4,4) = 18\) and \(R(4,5) = 25\text{,}\) 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\text{.}\) The legendary combinatorist Pál Erdős (1913—1996) said that it would be hopeless to try to calculate the exact value of \(R(6,6)\text{,}\) 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\text{.}\)) For more information about the values that have been calculated, see the Wikipedia article on Ramsey's theorem.

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

  1. Show that 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)\text{,}\) 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.

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

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

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\text{.}\) 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\text{,}\) or a blue \(K_i\text{.}\)

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 \ge 1\text{.}\) A \(K_1\) has no edges, so vacuously its edges have whichever colour we desire. Thus if \(n_1=1\) or \(n_2=1\text{,}\) we have \(r=R(n_1, n_2)=1\text{,}\) since for any \(2\)-edge-colouring of \(K_1\text{,}\) there is a red \(K_1\) and a blue \(K_1\text{.}\)

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

Let \(n_1, n_2 \ge 1\) such that \(n_1+n_2 =k+1\text{.}\) If either \(n_1=1\) or \(n_2=1\text{,}\) then this was one of our base cases and the proof is complete, so we may assume that \(n_1, n_2 \ge 2\text{.}\) Therefore, \(n_1-1, n_2-1 \ge 1\text{,}\) and \(n_1+n_2-1=k\text{.}\) Now, by our inductive hypothesis, there is some integer \(r_1=R(n_1,n_2-1)\) such that for any 2-edge-colouring of the edges of \(K_{r_1}\text{,}\) there is a subgraph that is either a red \(K_{n_1}\) or a blue \(K_{n_2-1}\text{.}\) 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}\text{,}\) there is a subgraph that is either a red \(K_{n_1-1}\) or a blue \(K_{n_2}\text{.}\)

We claim that \(R(n_1, n_2) \le r_1+r_2\text{.}\) 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}\text{.}\)

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

\begin{equation*} r_1+r_2=|V_1|+|V_2|+1 \end{equation*}

vertices, we must have either \(|V_1|\ge r_2\text{,}\) or \(|V_2|\ge r_1\text{.}\)

Suppose first that \(|V_1|\ge r_2\text{.}\) Since \(r_2=R(n_1-1,n_2)\text{,}\) 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}\text{.}\) 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\cup\{v\}\) has a red \(K_{n_1}\) and we are done.

Suppose now that \(|V_2|\ge r_1\) (the proof is similar). Since \(r_1=R(n_1,n_2-1)\text{,}\) 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}\text{.}\) 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\cup\{v\}\) has a blue \(K_{n_2}\) and we are done.

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

This second proof by induction completes the proof of the second base case for our original induction on \(c\text{,}\) 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 \ge 2\) be arbitrary. Assume that for every \(k_1, \ldots, k_m\ge 1\text{,}\) there is an integer \(r=R(k_1, \ldots, k_m)\) such that for any \(m\)-colouring of the edges of \(K_r\text{,}\) there must be some \(i \in \{1, \ldots, m\}\) such that \(K_r\) has a subgraph isomorphic to \(K_{k_i}\text{,}\) all of whose edges have been coloured with colour \(i\text{.}\)

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

\begin{equation*} r=R(n_1, \ldots, n_{m-1}, R(n_m,n_{m+1})) \end{equation*}

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 \in \{1, \ldots, m-1\}\) such that our \(K_r\) has a subgraph isomorphic to \(K_{n_i}\text{,}\) all of whose edges have been coloured with colour \(i\text{,}\) 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\)th colour (where this \(m\)th colour is really the combination of the colours \(m\) and \(m+1\)).

If there is some \(i \in \{1, \ldots, m-1\}\) such that our \(K_r\) has a subgraph isomorphic to \(K_{n_i}\text{,}\) all of whose edges have been coloured with colour \(i\text{,}\) 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\text{.}\) But by our base case for \(c=2\text{,}\) this graph must have either a subgraph isomorphic to \(K_{n_m}\) all of whose edges have been coloured with colour \(m\text{,}\) or a subgraph isomorphic to \(K_{n_{m+1}}\) all of whose edges have been coloured with colour \(m+1\text{.}\) This completes the inductive step.

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

⬛

  1. Find \(R(2,2,3)\text{.}\)

  2. Find \(R(2,4)\text{.}\)

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

Let \(c \in \natural^+\text{,}\) and let \(N = R(3, \ldots, 3)\) where there are \(c\) entries (all equal to \(3\)). If \(\{A_1,A_2,\ldots,A_c\}\) is any partition of \(\{1,2,\ldots,N\}\) into \(c\) subsets, show that some \(A_i\) contains three integers \(x\text{,}\) \(y\text{,}\) and \(z\text{,}\) such that \(x + y = z\text{.}\) This result is known as Schur's Theorem, named for Issai Schur (1875—1941).
Hint

The vertices of \(K_N\) are \(1,2,\ldots,N\text{.}\) Put colour \(i\) on each edge \(uv\) with \(|u-v| \in A_i\text{.}\) If \(u,v,w\) are the vertices of a monochromatic triangle of colour \(i\text{,}\) with \(u > v > w\text{,}\) then \(\{u - v, v - w, u - w\} \subseteq A_i\text{,}\) and we have \((u-v) + (v-w) = u-w\text{.}\)

To provide a somewhat broader perspective on Ramsey theory, we conclude this section with a couple of results on other problems that are related to this branch of combinatorics. We begin with a theorem from the \(1930\)s.

Eszter Klein (1910—2005) asked the more general question: how many points in the plane are required (assuming that no three are collinear) to ensure that some subset of \(n\) of them form the corners of a convex \(n\)-gon? She solved this question for the case \(n=4\) in the above theorem, but in the more general context only upper (and lower) bounds are known; Erdős and György Szekeres (1911—2005) were the first to publish such bounds. Erdős dubbed this the “Happy Ending” problem (and the special case is sometimes known as the Happy Ending Theorem) because this collaboration developed Klein's relationship with Szekeres, who she later married. The Erdős-Szekeres bounds for Klein's general question used Ramsey's Theorem, together with the Happy Ending Theorem.

We show in the following example that four points would not be sufficient.

Recall that in order for a polygon to be convex, the straight line segment connecting any points that lie within or on the boundary of the polygon cannot pass outside the polygon. A convex quadrilateral therefore cannot include a corner that lies in the interior of the triangle formed by the other three corners, as in this configuration:

The remainder of the proof of the Happy Ending Theorem consists of showing that \(5\) points suffices. There are only three possible configurations for \(5\) points in the plane: they may form a convex \(5\)-gon; four of them may form a convex quadrilateral with the remaining point in the interior; or three of them may form a triangle with the remaining two points in the interior. These configurations and the convex quadrilaterals that can be found in each case are drawn below. Our final drawing is in fact the only way the last configuration can arise. This means that there is always a convex quadrilateral, but determining exactly how the points can lie in this final configuration requires some additional consideration of the geometry involved. We will not include further details here.

The other result we present here looks more similar to Ramsey's Theorem. It arises from the general question posed by Kazimierz Zarankiewicz (1902—1959): Given integers \(m,n,s,\) and \(t\text{,}\) what is the largest number of edges that a bipartite graph whose bipartition sets contain \(m\) and \(n\) vertices, without containing a complete bipartite \(K_{s,t}\) subgraph? The value of the answer to this question is denoted by \(z(m,n;s,t)\text{.}\)

In about \(1951\) (published in \(1954\)), Tamás Kővári (1930—2010), Vera Sós (1930—), and Pál Turán (1910—1976) proved the following upper bound on this value.