## Section 46.3 Ramsey Property

###### Problem 46.3.1.

Let \(k,r \geq 1\) be given. Then there is an \(n_0(k,r)\) such that if \(n\geq n_0(k,r)\) and \(\{1,\ldots,n\}\) is \(k\)–coloured, then we can find natural numbers \(a,d_1,\dots,d_r\) such that all sums

have the same coluor (and, of course, \(a+d_1+\cdots+d_r\leq n\)).

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.

###### Problem 46.3.2.

Let us \(k\)–color all non–empty subsets of an \(n\)–element set. Prove that if \(n\) is large enough, there are two disjoint non–empty subsets \(X\) and \(Y\) such that \(X,Y\text{,}\) and \(X \cup Y\) have the same colour.

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{,}\)

###### Problem 46.3.3.

Suppose that the set of all subsets of an \(n\)–element set \(S\) is \(k\)–coloured, where \(n \geq N(k,t)\text{.}\) Find disjoint sets \(A_{1},B_{1},\ldots,A_{t},B_{t}\) such that for any fixed sequence \(1 \leq i_{1} \lt\ldots \lt i_{v} \leq t\text{,}\) all unions of the form

have the same colour.

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.

###### Problem 46.3.4.

Prove that for any given \(k\) and \(r\) there is an \(n = n(k,r)\) with the following property: whenever the set of all subsets of an \(n\)–element set \(S\) is \(k\)–coloured, then there exist non–empty disjoint subsets \(X_{1},\ldots,X_{r} \subseteq S \) such that all non–empty unions of any of them have the same colour.

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.

###### Problem 46.3.5.

Strengthen Problem 46.3.3 as follows: For any \(k\) and \(r\) there exists a natural number \(n\) such that, if \(\{1,\ldots,n\}\) is \(k\)–coloured, then there always exist natural numbers \(d_{1},\ldots,d_{r}\) such that \(d_{1}+\dots+d_{r}\leq n\) and all sums \(d_{i_{1}}+\dots+d_{i_{v}} (1 \leq i_{1} \lt \dots \lt i_{v} \leq r, v \geq 1)\) have the same colour.

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.

###### Problem 46.3.6.

Let \(P\) be any property of \(k\)–coloured finite sets of natural numbers (for example, a set has property \(P\) if it is monochromatic and forms an arithmetic progression). Suppose that, \(k\)–colouring all natural numbers in any way, some finite subset will have property \(P\text{.}\) Then there exists a natural number \(N\) such that \(k\)–colouring the set \(\{ 1,\dots,N \}\) arbitrarily, some subset of it will have property \(P\text{.}\)

Note: This statement is a very special case of a general principle called compactness.

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.

###### Problem 46.3.7.

Decide whether the following assertion is true: If the set of all natural numbers is \(k\)–coloured, one of the classes contains \(x, y, z\) with

\(x + y = 3z\text{,}\)

\(x + 2y = z\text{.}\)

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.

###### Problem 46.3.8.

Prove that there exists a function \(f(k)\) with the property that, if \(S\) is any set of integers with \(|S| \geq f(k)\text{,}\) then the set of all integers can be \(k\)–coloured so that \(S+j= \{s+j : s \in S\}\) meets all the colours for every integer \(j\text{.}\) The \(k\)–colouring can even be required to be periodic.

###### Remark 46.3.9.

The solution uses the following fact established in Problem 2.18 in Lovas'z book “Combinatorial Problems and Exercises:”

Let \(G\) be a simple graph on \(V(G)=\{1,\ldots,n\}\) with all degrees at most \(d\) and \(A_i\) be associated with each point \(i\text{.}\) Suppose that

\(\mathbf{P}(A_i)\leq \frac{1}{4d}\text{,}\) and

every \(A_i\) is independent of the set of all \(A_j\)'s for which \(j\) is not adjacent to \(i\text{.}\)

Then \(\mathbf{P}(\overline{A}_1\cdots\overline{A}_n)>0\text{.}\)

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.