Introduction to Ramsey Theory: Lecture notes for undergraduate course

Let \(\chi:\mathbb{N}\to \{0,1\}\) be a 2-colouring of positive integers and let \(k\in \mathbb{N}\text{.}\) We define a new colouring \(\chi':\mathbb{N}\to \{0,1\}\) by

By van der Waerden's theorem there are \(a,d\in \mathbb{N}\) such that

By definition of the 2-colouring \(\chi'\) this implies that

Therefore the \(k\)-term monochromatic progression

is \(\chi\)-monochromatic. Note that the common difference of this arithmetic progression is \(3d\text{,}\) a number divisible by 3.

1. Let \(k\in \mathbb{N}\) and let \(n\in \mathbb{N}\) be such that \(k\lt 2^n\text{.}\) By definition, the above colouring contains \(2^n\) consecutive integers coloured by 1. Therefore, there is positive integer \(a\) such that all terms of the \(k\)-term arithmetic progression

   \begin{equation*} a,a+1,a+2,\ldots,a+(k-1) \end{equation*}

   are coloured by the colour 1.

2. Let

   \begin{equation*} a,a+d,a+2d,\ldots,a+kd,\ldots \end{equation*}

   be an infinite arithmetic progression with the common difference \(d\) and let \(n\in \mathbb{N}\) be such that

   \begin{equation*} d\lt 2^{n}\text{.} \end{equation*}

   Since \(d\lt 2^n\text{,}\) any interval of consecutive integers with at least \(2^n\) elements must contain a term from the infinite arithmetic progression with the common difference \(d\text{.}\)

   On the other hand, by definition of the colouring we have

   \begin{equation*} \underbrace{11\cdots 1}_{2^n}\underbrace{00\cdots 0}_{2^{n+1}} \mbox {\ or }\underbrace{00\cdots 0}_{2^n}\underbrace{11\cdots 1}_{2^{n+1}}\text{.} \end{equation*}

   Hence

   \begin{equation*} a,a+d,a+2d,\ldots,a+kd,\ldots \end{equation*}

   is not monochromatic.

Let \(c\) be a 3-colouring of the interval \([1,18]\text{.}\) Say that the first colour is red, the second colour is blue, and the third colour is green. If there are at least two elements coloured red, then there is a red 2-term arithmetic progression.

Suppose that there is only one element \(i\in [1,18]\) coloured red. If \(i\in [1,9]\) then \([i+1,18]\) contains at least nine consecutive integers coloured blue or green. Since \(w(3,3)=9\) there is monochromatic 3-term arithmetic progression contained in \([i+1,18]\text{.}\) If \(i\in [10,18]\) then \([1,i-1]\) contains at least nine consecutive integers coloured blue or green. Since \(w(3,3)=9\) there is monochromatic 3-term arithmetic progression contained in \([1,i-1]\text{.}\)

If there is no element coloured red, then the interval \([1,18]\) is 2-coloured. Since \(w(3,3)=9\) there is monochromatic 3-term arithmetic progression contained in \([1,18]\text{.}\)

Therefore any 3-colouring of \([1,18]\) contains a 2-term arithmetic progression in the first colour or a 3-term arithmetic progression in the second or third colour.

In 1974 Tom Brown proved that \(w(3;2,3,3)=14\text{.}\)

1. Note that

   \begin{equation*} 0\lt a_{i+1}-a_i\leq 2, \mbox{ for all } i\in \mathbb{N} \end{equation*}

   implies that for \(a_i\) and \(a_{i+1}\) one of the following must be true:

   • \(a_{i+1}-a_i=1\) which means that \(a_i\) and \(a_{i+1}\) are consecutive integers

   • \(a_{i+1}-a_i=2\) which means that \(a_i\) and \(a_{i+1}\) are consecutive even integers or consecutive odd integers.

   Therefore, for any \(k\in \mathbb{N}\)

   \begin{equation*} A\cap \{2k-1,2k\}\not= \emptyset\text{.} \end{equation*}

   Hence for a chosen even integer \(n\text{,}\) the set \(A\) intersects each of \(n/2\) sets

   \begin{equation*} \{ 1,2\}, \{3,4\},\ldots, \{2n-1,n\} \end{equation*}

   which implies that

   \begin{equation*} |A\cap [1,n]|\geq \frac{n}{2}\text{.} \end{equation*}

   Therefore for any even \(n\in \mathbb{N}\)

   \begin{equation*} \frac{|A\cap [1,n]|}{n}\geq\frac{1}{2}\text{.} \end{equation*}

2. From (a) it follows that there is an infinite sequence \(\{x_i=\frac{|A\cap [1,2i]|}{2i}\}_{i\in \mathbb{N}}\) such that

   \begin{equation*} \frac{1}{2}\leq x_i\leq 1 \text{ for all } i\in \mathbb{N}\text{.} \end{equation*}

   The limit of any convergent subsequence of this sequence is greater than \(\frac{1}{2}\) and hence

   \begin{equation*} \overline{d}(A)=\limsup \frac{|A\cap [1,n]|}{n}\geq\frac{1}{2}\text{.} \end{equation*}

   Therefore the upper density of \(A\) is at least \(1/2\text{.}\)

3. Since the upper density of the set \(A\) is positive, by Szemerédi's theorem the set \(A\) contains arithmetic progressions of any finite length.

Suppose that \(i,j,k\in \mathbb{N}\text{,}\) \(i\lt j\lt k\text{,}\) are such that \(2^i\text{,}\) \(2^j\text{,}\) \(2^k\) form a 3-term arithmetic progression. This means that

It follows that

and

But this is impossible since \(2^{j-i}-1\) is an odd integer and \(2^{j-1}(2^{k-j}-1)\) is an even integer.

Therefore he set

does not contain any 3-term arithmetic progressions.

1. Colour every integer differently.

2. Consider the colouring

   \begin{equation*} c(i)=\left\{ \begin{array}{lcl} \mbox{red} \amp \text{ if } \amp i\equiv 0\pmod 3\\ \mbox{blue} \amp \text{ if } \amp i\equiv 1\pmod 3\\ \mbox{green} \amp \text{ if } \amp i\equiv 2\pmod 3. \end{array} \right. \end{equation*}

   It follows that if \(a\) and \(b\) are of the same colour then \(a\equiv b\pmod 3\text{.}\) Therefore the colouring \(c\) avoids 2-term arithmetic progressions with a common difference that is equal 1 (mod 3).