Introduction to Ramsey Theory: Students' Projects

Proof by induction. The base case is \(n_0(k, 1)=k+1\text{.}\) Next, suppose that \(r\geq 2\) is such that \(n_0(k, r-1)\) exists. We prove that that we can take

Suppose that \(n \geq n_0(k, r)\text{.}\) Let \(c\) be a \(k\)–colouring of the set \(\{1, \ldots, n\}\text{.}\) For each \(1 \leq p \leq k^{n_0(k, r-1)}+1\text{,}\) let \(c_p\) be the \(k\)-colouring of the set \(\{0,1,\ldots, n_0(k, r-1)-1\}\) defined by, for \(j\in \{0,1,\ldots, n_0(k, r-1)-1\}\text{,}\) \(c_p(j)=c(p+j)\text{.}\)

Since there are \(k^{n_0(k, r-1)}\) different \(k\)–colourings of the set \(\{0,1,\ldots, n_0(k, r-1)-1\}\text{,}\) by the Pigeonhole Principle there are \(1\leq p_1\lt p_2\leq k^{n_0(k, r-1)}+1\) such that, for each \(0 \leq j \leq n_0(k, r-1)-1\text{,}\) \(c(p_1+j)=c_{p_1}(j)=c_{p_2}(j)=c(p_2+j)\text{.}\)

By induction, there is a natural number \(a\text{,}\) \(p_1 \leq a \leq p_1+n_0(k, r-1)-1\text{,}\) and integers \(d_1, \ldots, d_{r-1}\) such that the set \(\{a+d_{i_1}+\ldots+d_{i_\nu}: 1 \leq i_1\lt \ldots\lt i_\nu \leq r-1\}\) is \(c\)–monochromatic. Set \(d_r=p_2-p_1\text{,}\) then, by the choice of \(p_1\) and \(p_j\text{,}\) the set

is \(c\)–monochromatic, which completes the induction step.

Let \(n=R(k;3,3)\) be the Ramsey number, i.e., the smallest positive integer that guaranties that any edge \(k\)–colouring of the complete graph with the vertex set \(\{1,2,\ldots,n\}\) yields a monochromatic triangle.

Let \(c\) be a \(k\)–colouring of the set of all non–empty subsets of the set \(\{1,2,\ldots,n\}\text{.}\) Let \(c^\prime\) be an edge \(k\)–colouring of the complete graph with the vertex set \(\{1,2,\ldots,n\}\) defined by, for \(1\leq i\lt j\leq n\text{,}\) \(c^\prime(\{i,j\}=c(\{i,\ldots,j-1\})\text{.}\)

Let \(p,q,r\in \{1,2,\ldots,n\) be such that \(p\lt q\lt r\) and \(c^\prime(\{p,q\})=c^\prime(\{p,r\})=c^\prime(\{q,r\})\text{.}\)

It follows that for \(X=\{p,\ldots, q-1\}\text{,}\) \(Y=\{q,\ldots, r-1\}\text{,}\) and \(X\cup Y=\{p,\ldots, q,\ldots, r-1\}\text{,}\)

By Problem 46.3.2, the number \(n \geq N(k,1)\) exists for all \(k\in \mathbb{N}\text{,}\) which establishes the base case of induction.

Let \(t\geq 1\) be such that the number \(N(k,t)\) exists for all \(k\in \mathbb{N}\text{.}\)

Let \(a=N(k^2,t)\) and \(N=N(k^{2^a},1)+a\text{.}\) Let \(c\) be a \(k\)–colouring of the set of all subsets of \(N\)–element set \(S\text{.}\)

Let \(T\subset S\) be such that \(|T|=a\text{.}\) Let \(\{T_1,T_2,\ldots,T_{2^a}\}\) be the set of all subset ot the set \(T\text{.}\) We define \(c^\prime\text{,}\) a \(k^{2^a}\)– colouring of the set of all subsets \(S\backslash T\text{,}\) by

Since \(|S\backslash T|=N-=N(k^{2^a},1)\text{,}\) by Problem 46.3.2, there exist two disjoint sets \(A_1,B_1\subseteq S\backslash T\) such that \(c^\prime(A_1)=c^\prime(B_1)=c^\prime(A_1\cup B_1)\text{,}\) and by definition of the colouring \(c^\prime\text{,}\) we have

for each \(X\subseteq T\text{.}\)

Next we define \(c^{\prime\prime}\text{,}\) a \(k^2\)–colouring of the set of all subsets of \(T\text{,}\) by

By definition of \(a\text{,}\) there are \(2t\) disjoint sets \(A_2,B_2,\dots,A_{t+1},B_{t+1}\) such that for each sequence \(1\leq i_1\lt \cdots\lt i_{\nu}\text{,}\) \(c^{\prime\prime}(C_{i_1}\cup \cdots \cup C_{i_\nu})\) is same for any choice of \(C_j=A_j,B_j\) or \(A_j\cup B_j\text{.}\)

Thus, for \(A_1,B_1,\dots,A_{t+1},B_{t+1}\) and any sequence \(1\leq i_1\lt \cdots\lt i_{\nu}\text{,}\) \(c(C_{i_1}\cup \cdots \cup C_{i_\nu})\) is same for any choice of \(C_j=A_j,B_j\) or \(A_j\cup B_j\text{.}\)

Hence, we may take \(N(k,t+1)=N\text{,}\) which completes the induction step.

We induct on \(r\text{.}\) The base case \(r=2\) is established by Problem 46.3.3.

Let \(r\geq 2\) be such that \(t=n(k,r)\) exists for any \(n\in \mathbb{N}\text{.}\) Let \(N=N(k,n(k,r))=N(k,t)\text{,}\) where \(N=N(k,t)\) is the number established in Problem 46.3.3.

Let \(c\) be a \(k\)–colouring of the set of all subsets of a \(N\)– element set \(S\text{.}\) By Problem 46.3.3, there exists disjoint sets \(A_1,B_1,\ldots,A_t,B_t\) such that for each sequence \(1\leq i_1\lt \cdots\lt i_v\leq t\text{,}\) all sets of the form \(C_{i_1}\cup\cdots\cup C_{i_v}\) have the same colour, where \(C_j=A_j,B_j \text{ or }A_j\cup B_j\text{.}\)

Let a \(k\)–colouring \(c^\prime\) of the set of the subsets of the set \(\{1,\dots,t\}\) be defined by

By our choice of \(t\text{,}\) there are disjoint subsets \(I_1,\cdots,I_r\subseteq \{1,\cdots,t\}\) such that the colouring \(c\) colours any non–empty union of them, say, red. Let

Then, \(X_1,\cdots,X_r\) and \(Y_1,\cdots,Y_r\) are disjoint sets, and any of their non–empty union is also coloured red.

Let \(V,W\subseteq \{1,\cdots,r\}\) and let

It follows

By our choice of \(A_i,B_i\text{,}\)

is also coloured red.

Since the number of sets \(X_1,\ldots,X_r\) and \(Y_1,\cdots,Y_r\) is \(2r\geq r+1\text{,}\) we can take $n(k,r+1)=N$, which completes the induction step.

Let \(n=n(k,r)\text{,}\) where \(n(k,r)\) is a function established in Problem 46.3.4. Suppose that \(c\) is a \(k\)–colouring of the set \(\{1,\dots ,n\}\text{.}\) Let \(c^\prime\) be a \(k\)–colouring of the set of all subsets subsets of \(S=\{1,\dots,n\}\text{,}\) defined by

By Problem 46.3.4, there are disjoint sets \(X_1,\dots,X_r \in S\) such that the set \(\{ X_{i_1}\cup\cdots\cup X_{i_\mu}:\emptyset\not= \{i_1\lt \ldots \lt i_\mu\}\subset \{1,\ldots,r\}\}\) is \(c^\prime\)–monochromatic. By definition of the colouring \(c^\prime\text{,}\) numbers \(d_{1}=|X_1|,\ldots,d_{r}=|X_r|\) are such that the set \(\{ d_{i_1}+\cdots + d_{i_\mu}:\emptyset\not= \{i_1\lt \ldots \lt i_\mu\}\subset \{1,\ldots,r\}\}\) is \(c\)–monochromatic.

Suppose that such \(N\) does not exist, i.e., suppose that for every \(N\in \mathbb{N}\) there is a \(k\)–colouring \(c_N\) of \(\{1,\dots,N\}\) for which no subset has property \(P\text{.}\) For each \(\ell \in \mathbb{N}\) consider the colours \(c_N(\ell)\text{,}\) for all \(N\geq \ell\text{.}\) Since we use \(k\text{,}\) a finite number of colours, there will be a sequence of natural numbers \(S_1=\{N_i^{(1)}\}_{i\in \mathbf{N}}\) such that

Denote this common colour by \(c(1)\text{.}\)

Now consider the colours \(\alpha _{N_i^1}(2)\text{,}\) \(i\in \mathbb{N}\text{.}\) There is a sequence of natural numbers \(S_2=\{N_i^{(2)}\}_{i\in \mathbf{N}}\text{,}\) a subsequence of the sequence \(S_1\text{,}\) such that

Denote this common colour by \(c(2)\text{.}\)

In general, if the sequence \(S_n=\{N_i^{(n)}\}_{i\in \mathbf{N}}\text{,}\) a subsequence of each of \(S_\ell\text{,}\) \(1\leq \ell\leq n-1\text{,}\) then \(S_{n+1}=\{N_i^{(n+1)}\}_{i\in \mathbf{N}}\) a subsequence of the sequence \(S_n\text{,}\) is such that

We denote this common colour by \(c(n+1)\text{.}\)

By continuing this process, we define \(c\text{,}\) a \(k\)–colouring of the set of natural numbers. Observe that for each \(m\in \mathbb{N}\) and each \(\ell\in \{1,\ldots, m\}\text{,}\) by the fact that each sequence is a subsequence of the sequence obtained in the previous step, we have \(c(\ell)=c_{N_1^{(m)}} (\ell)\text{.}\)

We claim that the colouring \(c\) is such that no finite subset has the property \(P\text{.}\)

Assume that this is not true, i.e., assume that a finite set \(T\) has the property \(P\text{.}\) Let the natural number \(m\in\mathbb{N}\) be such that \(S \subseteq \{1,\ldots, m\}\text{.}\) Then, for any \(\ell\in T\text{,}\)

which implies that \(T\) has property \(P\) in the colouring \(c_{N_1^{(m)}}\) too. This contradicts our choice of the colouring \(c_{N_1^{(m)}}\text{.}\) Hence the colouring \(c\) is such that there is no finite subset with the propert \(P\text{,}\) which contradicts the assumption about the property \(P\text{,}\) which completes the proof of the claim.

1. We represent each natural number \(m\) in base \(5\text{,}\) i.e., we write \(m = 5^{A_m} (5{B_m} + Y_m)\text{,}\) \(1 \leq Y_m \leq 4\text{.}\) Let \(c\text{,}\) a \(4\)–colouring of the set of natural numbers be defined by \(c(m)=Y_m\text{.}\)

Suppose that there is a \(c\)–monochromatic solution of the equation, i.e., suppose that for for some \(Y\in\{1,2,3,4\}\text{,}\) there are \(A_x,B_x,A_y,B_y,A_z,B_z\) such that

We divide the equality above by \(5^A\text{,}\) where \(A = \min\{A_x, A_y, A_z\}\text{,}\) and consider the identity modulo \(5\text{.}\) It follows, for some \(E_x,E_y,E_z\in \{0,1,2,3,4\}\text{,}\)

Notice that \(E_x = 1\text{,}\) if \(A = A_x\text{,}\) or \(E_x = 0\text{,}\) if \(A \lt A_x\text{.}\) The same is true for \(E_y\) and \(E_z\text{.}\) By dividing the identity by \(Y\text{,}\) we obtain

which, since \(E_x, E_y, E_z \in \{0,1\}\) implies \(E_X = E_y = E_z = 0\text{,}\) and therefore \(A \lt \min\{A_x,A_y,A_z\}\text{.}\) This contradicts the definition of \(A\) and proves our claim tha the equation has no a \(c\)– monochromatic solution.

2. Let \(k\in \mathbb{N}\) and let \(c\) be a \(k\)–colouring of the natural numbers. We prove by induction on \(k\) that \(x+2y = z\) has a \(c\)–monochromatic solution.

For \(k=1\text{,}\) this is obvious. Suppose that the claim holds for all \(k - 1\)–colourings of \(\mathbf{N}\text{,}\) where \(k\geq 2\) is a fixed integer.

It follows that there is a natural number \(N\) with the property that if we \((k -1)\)–colour the numbers \(\{1,\ldots, N\}\text{,}\) then one of the colour classes will contain a solution of \(x + 2y= z\text{.}\)

By van der Warden's theorem, there is \(c\)–monochromatic (say red) arithmetic progression

If there is \(p\in \{1,\ldots,N\}\) such that \(pd\) is red then for \(x = a\text{,}\) \(y = pd\text{,}\) \(z = a + 2pd\) we have \(x+2y=z\) and \(c(x)=c(y)=c(z)=\text{ red}\text{,}\) i,.e, we have a \(c\)–monochromatic solution of the equation.

If there is no a red \(pd\text{,}\) we define \(c^\prime\text{,}\) a \((k -1)\)–colouring of the set \(\{1,\ldots,N\}\text{,}\) by \(c^\prime(p)=c(pd)\text{.}\)

By the definition of \(N\) there is a \(c^\prime\)– monochromatic solution of the equation \(x_1, y_1, z_1\text{,}\) i.e., \(x_1 + 2y_1 = z_1\) and \(c^\prime(x_1)=c^\prime(y_1)=c^\prime(z_1)\text{.}\) But this implies that \((dx_1) + 2(dy_1) = (dz_1)\) and \(c(dx_1)=c(dy_1)=c(dz_1)\text{,}\) i.e., \(x=dx_1,y=y_1, z=dz_1\) is a \(c\)–monochromatic solution of the equation.

By the Principle of Mathematical Induction, the claim is true.

Supposed that a function \(f(k)\) with the required property exists and that a set \(S\) is such that \(|S|\gt f(k)\text{.}\)

We \(k\)–colour the set of integers randomly, i.e., integers are coloured independently of each other with the probability of giving an integer a particular colour \(\frac{1}{k}\text{.}\) If \(A_j\) is an event that \(S+j\) does not meet one of the colours, then

We form a graph \(G\) on the set of integers by connecting \(j_1\) to \(j_2\) such that \((S+j_1)\cap (S+j_2)\neq \emptyset\text{,}\) then \(A_j\) is independent of \(\{A_\ell:(j,\ell)\not\in E(G)\}\text{.}\) Observe that the degree of each vertex is \

If \(k(1-\frac{1}{k})^{f(k)}\leq \frac{1}{4f(k)^2}\text{,}\) we have \(P(A_j)\leq \frac{1}{4d}\text{.}\) By Remark 46.3.9, \(\mathbf{P}(\bar{A_0}\dots\bar{A}_N)\gt 0\) for any positive integer \(N\text{.}\)

Observe that we have established that for any positive integer \(N\) and any \(j\in\{0,\ldots, N\}\text{,}\) in a random \(k\)–colouring of integers, the set \(S+j\) meets all colours.

Here is the construction of a \(k\)–colouring with the property that \(\mathbf{P}(\sum_{-\infty}^{\infty}\bar{A_j})\gt 0\text{.}\)

Let \(r\) be the diameter of \(S\text{,}\) with \(r=\max(S)-\min(S)\text{.}\) Let \(N\gt k^{r+1}\) be an even integer such that \(S\subseteq \left\{-\frac{N}{2},-\frac{N}{2}+1,\ldots, \frac{N}{2}-1,\frac{N}{2}\right\}\text{.}\) Observe that each translate of \(S\) contained in \(\left\{\frac{N}{2}+1,\ldots,\frac{3N}{2}\right\}\) is of the form \(j+S\text{,}\) for some \(j\in \{r,\ldots,2N-r\}\text{.}\)

Let \(c\) be a \(k\)–colouring of integers for which \(\bar{A_0}\cdots\bar{A}_{2N}\not=\emptyset\) holds.

Since \(N\gt k^{r+1}\text{,}\) by the Pigeonhole Principle, the set \(\left\{\frac{N}{2}+1,\ldots,\frac{3N}{2}\right\}\) contains two segments \(\{u,u+1,\ldots,u+r\}\) and \(\{v,v+1,\ldots,v+r\}\text{,}\) with \(u\lt v\text{,}\) that are coloured identically, i.e., for all \(\ell\in\{0,1\ldots,r\}\text{,}\) \(c(u+\ell)=c(v+\ell)\text{.}\)

We define a new \(k\)–colouring \(c^\prime\) of integers in the following way:

• The colouring \(c^\prime\) is periodic with a period \(T=v-u\text{.}\)

• For each \(\ell \in \{u,u+1,\ldots,v-1\}\text{,}\) \(c^\prime(\ell)=c(\ell)\text{.}\)

• For an integer \(n\) let \(m\) be the unique integer such that \(n+mT \in \{u,u+1,\ldots,v-1\}\text{.}\) Then, by definition, \(c^\prime(n)=c(n+mT)\text{.}\)

Observe that for each \(\ell\in\{0,1\ldots,r\}\text{,}\) \(u+\ell+T=v+\ell\text{.}\) Moreover, for any \(n\in \{u, u+1,\ldots, v, v+r\}\text{,}\) \(c^\prime(n)=c(n)\text{.}\) Finally, observe that for each \(m\in \{u, u+1,\ldots, v-1\}\) and each \(\ell\in\{0,1\ldots,r\}\text{,}\) \(m+\ell \in \{u, u+1,\ldots, v, v+r\}\text{,}\) i.e., \(c^\prime(m+\ell)=c(m+\ell)\text{.}\)

Let \(s_m=\min S\) and \(s_M=\max S\text{.}\) For \(j\in\mathbb{Z}\text{,}\) let \(m\in \mathbb{Z}\) be such that \(j+mT+s_m\in \{u,u+1,\ldots,v-1\}\text{.}\) But then \(j+mT+s_M\lt v+r\text{,}\) which implies that \(j+mT+S\subset m+\ell \in \{u, u+1,\ldots, v, v+r\}\text{.}\) Hence, for all \(s\in S\text{,}\) \(c^\prime(j+s)=c(j+mT+s)\text{.}\)

Since there is \(i\in \{1,\ldots,2N\}\) such that \(i+S=j+mT+S\text{,}\) it follows that \(c^\prime\) is a \(k\)–colouring such that \(S+j= \{s+j : s \in S\}\) meets all the colours for every integer \(j\text{.}\)

It turns out that, for a large enough \(c\text{,}\) \(f(k)=\lfloor ck\log k\rfloor\) is the appropriate function. Indeed,

together with

is all what is needed.