Ramsey's Theorem: Two Colours

Section 2.3 Ramsey's Theorem: Two Colours

To see things in the seed, that is genius. — Laozi, Chinese philosopher, 6th century BC

Recall:

\(\displaystyle R(3,3)=6\)

Figure 2.3.1. \(K_6\) - a complete graph on six vertices
\(\displaystyle R(4,3)=R(3,4)=9\)

Figure 2.3.2. \(K_9\) - a complete graph on nine vertices
\(R(4,4)=18\text{:}\) Consider a blue-red edge colouring of a \(K_{18}\text{.}\) See Figures 2.3.3 and Figure 2.2.19.

Figure 2.3.3. Step 1: Observe that each vertex \(\color{blue}{\blacksquare}\) is adjacent to 9 edges of the same colour - say red

Figure 2.3.4. Step 2 — Two cases

Jeopardy!

There are only two 2-colourings of \(K_{16}\) without a monochromatic \(K_4\text{.}\)
There is only one 2-colouring of \(K_{17}\) without a monochromatic \(K_4\text{.}\)

Definition 2.3.5.

The Ramsey number \(R(s, t)\) is the minimum number \(n\) for which any edge 2-coloring of \(K_n\text{,}\) a complete graph on \(n\) vertices, in red and blue contains a red \(K_s\) or a blue \(K_t\text{.}\)

Three BIG Questions:

Does the Ramsey number \(R(s, t)\) exist for any choice of natural numbers \(s\geq 2\) and \(t\geq 2\text{?}\)
If \(R(s,t)\) exists, can we find the exact value of \(R(s,t)\text{?}\)
If \(R(s,t)\) exists and if we cannot find the exact value of \(R(s,t)\text{,}\) what are the best known bounds for \(R(s,t)\text{?}\)

What About...

\(R(s,2)\text{?}\)
\(R(2,t)\text{?}\)

Theorem 2.3.6.

Ramsey's Theorem, Two Colours. For any \(s,t\in \mathbb{N}\backslash \{ 1\}\) the Ramsey number \(R(s,t)\) exists and, for \(s,t\geq 3\text{,}\)

\begin{equation*} R(s,t)\leq R(s-1,t)+R(s,t-1)\text{.} \end{equation*}

Observation 2.3.7.

\(R(2,2)=2, \ R(3,2)=R(2,3)=3, \ R(3,3)=6, \ R(4,2)=R(2,4)=4\text{.}\)

Observation 2.3.8.

If \(s,t\in \mathbb{N}\backslash \{ 1\}\) are such that

\begin{equation*} s+t=4 \text{ or } s+t=5 \text{ or } s+t=6 \end{equation*}

then \(R(s,t)\) exists!

Observation 2.3.9.

Since, for any \(s\geq 2\text{,}\) \(R(s,2)=R(2,s)=s\text{,}\) we are interested only in the question if \(R(s,t)\) exists for \(s,t\geq 3\text{.}\)

Observation 2.3.10.

\((s-1)+t=s+(t-1)=(s+t)-1\text{.}\)

Observation 2.3.11.

To prove that \(R(s,t)\text{,}\) \(s,t\geq 3\text{,}\) exists it is enough to prove that any 2-colouring of a complete graph \(K_M\) where

\begin{equation*} M=R(s-1,t)+R(s,t-1) \end{equation*}

yields a monochromatic \(K_s\) or a monochromatic \(K_t\text{.}\) Why?

Strategy: We prove that any 2-colouring of a complete graph \(K_M\) where

\begin{equation*} M=R(s-1,t)+R(s,t-1) \end{equation*}

yields a monochromatic \(K_s\) or a monochromatic \(K_t\) via induction on the sum \(s+t\text{.}\)

Proof.

(Ramsey's Theorem, Two Colours.) Let \(s,t\geq 3\text{.}\) We use mathematical induction on the sum \(s+t\) to prove that \(R(s,t)\) exists.

The base case of induction, \(s+t=6\text{,}\) follows from the fact that \(R(3,3)=6\text{.}\)

Suppose that \(n\geq 6\) is such that for any \(u,v\geq 3\) such that \(u+v=n\) the Ramsey number \(R(u,v)\) exists.

Let \(s,t\geq 3\) by such that

\begin{equation*} s+t=n+1\text{.} \end{equation*}

Then, since

\begin{equation*} (s-1)+t=s+(t-1)=n\text{,} \end{equation*}

by the induction hypothesis \(R(s-1,t)\) and \(R(s,t-1)\) exist. Let

\begin{equation*} M=R(s-1,t)+R(s,t-1) \end{equation*}

and we consider a 2-colouring of \(K_M\text{.}\) See Figure 2.3.12.

Figure 2.3.12. \(K_{M}\text{:}\) Each vertex is incident to \(M-1=R(s-1,t)+R(s-1,t)-1\) edges

Fix a vertex. There are two possibilities. See Figure 2.3.13.

Figure 2.3.13. Pigeonhole principle: Two cases

Suppose that there are at least \(R(s-1,t) \) red edges. See Figure 2.3.14.

Figure 2.3.14. Recall the definition of \(R(s-1,t)\)

Hence, any red/blue 2-colouring of \(K_M\) yields a red \(K_s\) or a blue \(K_t\text{.}\) Therefore \(R(s,t)\) exists and

\begin{equation*} R(s,t)\leq R(s-1,t)+R(s,t-1)\text{.} \end{equation*}

Table 2.3.15. Known Ramsey Numbers

\(s\)	\(t \)	\(R(s,t)\)	Who and When
\(3\)	\(3\)	\(6\)	Greenwood and Gleason, 1955
\(3\)	\(4\)	\(9\)	Greenwood and Gleason, 1955
\(3\)	\(5\)	\(14\)	Greenwood and Gleason, 1955
\(3\)	\(6\)	\(18\)	Graver and Yackel, 1968
\(3\)	\(7\)	\(23\)	Kalbfleisch, 1966
\(3\)	\(8\)	\(28\)	McKay and Min, 1992
\(3\)	\(9\)	\(36\)	Grinstead and Roberts, 1982
\(4\)	\(4\)	\(18\)	Greenwood and Gleason, 1955
\(4\)	\(5\)	\(25\)	McKay and Radziszowski, 1995

Table 2.3.16. More Known Facts

\(s\)	\(t \)	\(R(s,t)\)	Who and When
\(3\)	\(10\)	\([40, 42] \)	Exoo 1989, Radziszowski and Kreher 1988
\(3\)	\(11\)	\([46, 51] \)	Radziszowski and Kreher 1988
\(4\)	\(6\)	\([35, 41]\)	Exoo, McKay and Radziszowski 1995
\(4\)	\(7\)	\([49, 61] \)	Exoo 1989, Mackey 1994
\(5\)	\(5\)	\([43, 48] \)	Exoo 1989, McKay and Radziszowski 1995
\(5\)	\(6\)	\([58, 87] \)	Exoo 1993, Walker 1971
\(6\)	\(6\)	\([102, 165]\)	Kalbfleisch 1965, Mackey 1994
\(6\)	\(7\)	\([113, 298] \)	Exoo and Tatarevic 2015, Xu and Xie 2002

In Erdős' Words.

Suppose aliens invade the earth and threaten to obliterate it in a year's time unless human beings can find the Ramsey number for red five and blue five. We could marshal the world's best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack.

How Big - Upper Bound.

\begin{equation*} R(s,t)\le \binom{s+t-2}{t-1}\text{.} \end{equation*}

Proof.

(Via double induction on \(s\) and \(t\text{.}\))

How Big - Lower Bound. For \(s\geq 3\text{,}\)

\begin{equation*} R(s,s)>2^{s/2}\text{.} \end{equation*}

Proof.

Let \(s\geq 3\) and \(n=2^{s/2}\text{.}\) Consider a random colouring of \(K_n\) where each edge is coloured independently red or blue with probability \(0.5\text{.}\)

Choose any \(s\) vertices of \(K_n\) and consider the corresponding \(K_s\text{.}\) What is the probability that such \(K_s\) is monochromatic?
In how many different ways can we choose \(s\) vertices of \(K_n\text{?}\)
The probability that there is at least one monochromatic \(K_s\) is at most

\begin{equation*} \binom{n}{s}\cdot \frac{2}{2^{\binom{s}{2}}}\lt \frac{2n^s}{s!\cdot 2^{\frac{s(s-1)}{2}}}=\frac{2^{1+s/2}}{s!}\lt 1. \end{equation*}

Therefore: For \(s\geq 3\)

\begin{equation*} 2^{s/2}\lt R(s,s)\le \binom{2s-2}{s-1}\text{.} \end{equation*}

Epilogue

Question 2.3.17.

Suppose that we decide to use three colours, say \(\color{blue}{\text{blue}}\text{,}\) \(\color{red}{\text{red}}\text{,}\) and \(\color{green}{\text{green}}\text{.}\) Is there a something like \(R(s,t,u)\text{,}\) for \(s,t,u\in \mathbb{N}\text{?}\) In other words, is it possible to find a number \(n\) so that if the edges of \(K_n\) are coloured by one of the three colours then there will be always possible to find a \(\color{blue}{\text{blue}}\) \(K_s\) or a \(\color{red}{\text{red}}\) \(K_t\) or a \(\color{green}{\text{green}}\) \(K_u\text{?}\)

Definition 2.3.18.

Let \(m\in \mathbb{N}\backslash\{1\}\) and \(s_1,s_2,\ldots, s_m\in \mathbb{N}\backslash\{1\}\) be given. The Ramsey number \(R(s_1, s_2,\ldots, s_m)\) is the minimum number \(n\) for which any edge \(m\)-colouring of \(K_n\text{,}\) a complete graph on \(n\) vertices, contains a monochromatic \(K_{s_i}\) for some \(i\in[1,m]\text{.}\)

Three BIG Questions:

Does the Ramsey number \(R(s_1, s_2,\ldots, s_m)\) exist for any choice of natural numbers \(m, s_1, s_2,\ldots, s_m\geq 2\text{?}\)
If \(R(s_1, s_2,\ldots, s_m)\) exists, can we find the exact value of \(R(s_1, s_2,\ldots, s_m)\text{?}\)
If \(R(s_1, s_2,\ldots, s_m)\) exists and if we cannot find the exact value of \(R(s_1, s_2,\ldots, s_m)\text{,}\) what are the best known bounds for \(R(s_1, s_2,\ldots, s_m)\text{?}\)

Theorem 2.3.19.

Ramsey's Theorem. For any \(, s_1, s_2,\ldots, s_m\in \mathbb{N}\backslash \{ 1\}\) the Ramsey number \(R(s_1, s_2,\ldots, s_m)\) exists.

Resources.