Ramsey's Theorem, Infinite Case

Section 2.4 Ramsey's Theorem, Infinite Case

No finite point has meaning without an infinite reference point. — Jean-Paul Sartre, French philosopher, playwright, novelist, screenwriter, political activist, biographer, and literary critic, 1905 - 1980.

Reminder. 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*}

See Figure 2.4.1

Figure 2.4.1. \(K_{R(s,t)}\text{:}\) There is a red \(\color{red}{K_s}\) or there is a blue \(\color{blue}{K_t}\)

Infinite Case - Notation:

The set of natural numbers: \(\mathbb{N}=\{ 1,2,3,\ldots\}\text{.}\)
For \(r\in \mathbb{N}\) and any set \(X\) we define \(X^{(r)}\) to be the set of all subsets on \(X\) with exactly \(r\) elements:

\begin{equation*} X^{(r)}=\{ A\subset X: |A|=r\}\text{.} \end{equation*}
For \(k\in \mathbb{N}\) we define a \(k\)-colouring of \(\mathbb{N}^{(r)}\) as a function from \(\mathbb{N}^{(r)}\) to \(\{1,2,\ldots,k\}\text{:}\)

\begin{equation*} c:\mathbb{N}^{(r)}\to \{1,2,\ldots,k\}=[1,k]\text{.} \end{equation*}
If \(c\) is a \(k\)-colouring of \(\mathbb{N}^{(r)}\) and \(A\subset \mathbb{N}\) such that, for all \(x,y\in A^{(r)}\text{,}\) \(c(x)=c(y)\text{,}\) we say that the set \(A\) is monochromatic. See Figure 2.4.2.

Figure 2.4.2. \(A\subset \mathbb{N}\) is \(\color{red}{\text{monochromatic}}\text{!}\)

We re-state Theorem 2.3.6 in the following form:

Theorem 2.4.3.

Whenever \(\mathbb{N}^{(2)}\) is 2-coloured, there exist arbitrarily large monochromatic sets.

Observation 2.4.4.

An infinite monochromatic set is much more than having arbitrarily large monochromatic sets.

Example 2.4.5.

Colour

\begin{equation*} \{\color{red}{1,2}\}, \{\color{red}{3,4,5}\}, \{\color{red}{6,7,8,9}\}, \cdots \end{equation*}

i.e., colour red all edges within the sets above. Colour all other edges blue.

For example, is the edge between \(500500\) and \(500501\) red or blue? What about the edge between \(499499\) and \(500500\text{?}\)

What about the existence of an infinite red set in this colouring? In other words, can you find an infinite set \(A\subset \mathbb{N}\) such that the edge between any \(x,y\in A\) is red?

Theorem 2.4.6.

Ramsey Theorem - Two Colours - Infinite Case: Whenever \(\mathbb{N}^{(2)}\) is 2-coloured, there exists an infinite monochromatic set.

Proof.

We colour elements of \(\mathbb{N}^{(2)}\) \(\color{red}{\text{red}}\) and \(\color{blue}{\text{blue}}\text{:}\)

\begin{equation*} c:\mathbb{N}^{(2)}\to \{\color{blue}{\bullet}, \color{red}{\bullet}\}\text{,} \end{equation*}

See Figures 2.4.7– Figure 2.4.10.

Figure 2.4.7. Step 1: Pick \(a_1\in \mathbb{N}\text{.}\) Look at \(\color{red}{\{a_1,x\}}\) and \(\color{blue}{\{a_1,y\}}\text{,}\) \(x,y\in \mathbb{N}\text{.}\)

Figure 2.4.8. Step 2: Say that \(B_1=\{x\in \mathbb{N}:\color{red}{\{a_1,x\}}\}\) is infinite. Pick \(a_2\in B_1\text{.}\) Look at \(\color{red}{\{a_2,x\}}\) and \(\color{blue}{\{a_2,y\}}\text{,}\) \(x,y\in B_1\text{.}\)

Figure 2.4.9. Step 3: Say that \(B_2=\{y\in B_1:\color{blue}{\{a_2,y\}}\}\) is infinite. Pick \(a_3\in B_2\text{.}\) Look at \(\color{red}{\{a_3,x\}}\) and \(\color{blue}{\{a_3,y\}}\text{,}\) \(x,y\in B_2\text{.}\)

Figure 2.4.10. Step 4: Say that \(B_3=\{x\in B_2:\color{red}{\{a_3,x\}}\}\) is infinite. Pick \(a_4\in B_3\text{.}\) Look at \(\color{red}{\{a_4,x\}}\) and \(\color{blue}{\{a_4,y\}}\text{,}\) \(x,y\in B_3\text{.}\) Note that \(\color{red}{\{a_1,a_2\}\ \{a_1,a_3\}\ \{a_1,a_4\}}\text{,}\) \(\color{blue}{\{a_2,a_3\}\ \{a_2,a_4\}}\text{,}\) and \(\color{red}{\{a_3,a_4\}}\text{.}\)

Continue…

Summary: We obtain an infinite sequence of natural numbers

\begin{equation*} a_1,a_2,a_3,\ldots \end{equation*}

and an infinite sequence of sets

\begin{equation*} \mathbb{N}\supseteq B_1\supseteq B_2\supseteq B_3\supseteq \ldots \end{equation*}

with the property that, for any \(i\in \mathbb{N}\)

\(B_i\) is an infinite set
\(\displaystyle a_{i+1}\in B_i\)
\(c(\{a_i,a_{i+1}\})= c(\{a_i,a_{i+2}\})=c(\{a_i,a_{i+3}\})=\ldots\text{.}\)

See Figure 2.4.11.

Figure 2.4.11. Conclusion: There must be an infinite number of \(a_i\)'s that see only \(\color{red}{\text{red}}\) or an infinite number of \(a_i\)'s that see only \(\color{blue}{\text{blue}}\text{.}\)

Example 2.4.12.

Let \(a_1,a_2,a_3, \ldots\) be a sequence of mutually distinct real numbers. Prove that it contains a monotone subsequence.

Challenge. Whenever \(\mathbb{N}^{(2)}\) is \(k\)-coloured, there exists an infinite monochromatic set.

Example 2.4.13.

Let \(a_1,a_2,a_3, \ldots\) be a sequence of real numbers. Prove that it contains either a constant or strictly monotonic subsequence.

Recall Theorem 2.4.6: Whenever \(\mathbb{N}^{(r)}\) is 2-coloured, there exists an infinite monochromatic set.

Theorem 2.4.14.

Ramsey Theorem. Let \(m,r\in \mathbb{N}\text{.}\) Whenever \(\mathbb{N}^{(r)}\) is \(m\)-coloured, there exists an infinite monochromatic set.

Resources.