Introduction to Ramsey Theory: Students' Projects

Let \(j\) be the number of people with no friends. If \(j\geq 2\) then there are at least two people who have the same number (\(0\)) of friends.

If \(j\in\{0,1\}\) then there are \(n-j\gt 0\) people who have between 1 and \(n-j-1\) friends.

By the Pigeonhole Principle there must be at least two people with the same number of friends.

If there are 11 pigeons (shoes) sitting in 10 pigeonholes (one for each pair of shoes), at least one pigeonhole has 2 pigeons (so a pair of shoes) by the pigeonhole principle.

Observe that each vertical line of the stacked bracelets has three beads, and there are two colours, so each vertical line has a dominant colour by the pigeonhole principle, which means one colour appears a least twice in the vertical line.

Next recall that there are \(2^3=8\) possible colour different configurations of three beads stacked vertically.

By the pigeonhole principle there must be at least two (out of ten) vertical lines with the same colour configurations. In two of those identically configured vertical lines we chose four beads coloured by the dominant colour that form a rectangle.

We consider three cases.

• Case 1: Suppose that the five vertices form a convex pentagon. Then any four of them form a convex quadrilateral.

  There are five convex quadrilaterals in this case.

• Case 2: Suppose that four points form a convex quadrilateral (say \(A_1, A_2, A_3\text{,}\) and \(A_4\) in clockwise order) which contains the fifth point \(A_5\) in its interior. Let \(S\) be the intersection of the diagonals \(\overline{A_1A_3}\) and \(\overline{A_2A_4}\) . Then the point \(A_5\) lies in one of the four triangles into which diagonals dissect the quadrilateral, say \(\triangle SA_1A2\text{.}\) Observe that the quadrilaterals \(A_1A_5A_3A_4\) and \(A_2A_3A_4A_5\) are convex but the other two are not.

  There are three convex quadrilaterals in this case.

• Case 3: Suppose that three points (say \(A_1, A_2, A_3\)) form a triangle with \(A_4\) and \(A_5\) in its interior. The line \(A_4A_5\) intersects two of the three sides, say \(\overline{A_1A_2}\) and \(\overline{A_1A_3}\text{.}\) Then \(A_2,A_3 A_4A_5\) is the only convex quadrilateral.

Recall (Section 2.3) that, for any \(s,t\geq 3\text{,}\) \(\displaystyle {s+t - 2 \choose t - 1}\text{.}\) Hence, for \(s=t\)

\(\textbf{Note:}\) For the latest developments (as of December 2020) regarding the upper bounds for a diagonal Ramsey number see this article by Ashwin Sah, an undergraduate student from MIT: “Diagonal Ramsey via effective quasirandomness”.

Suppose that \(k\equiv \pm 1(\mbox{mod } 6)\text{.}\) The claim is obviously true for \(k=1\text{.}\) Hence suppose that \(k\geq 5\text{.}\) Let \(l\geq 1\) be such that \(k=6l+1\) or \(k=6l-1\text{.}\) Observe that \(k\) is an odd number.

To show that \(w(k,2,2;3)=3k\text{,}\) it is sufficient to prove that \(w(k,2,2;3)\leq 3k\) and \(w(k,2,2;3)\geq 3k\text{.}\)

To prove that \(w(k,2,2;3)\leq 3k\) we need to show that any \(3\)-colouring (say, red, blue, and green) of the interval \([1,3k]\) will yield a red \(k\)-term arithmetic progression or a blue \(2\)-term arithmetic progression or a green \(2\)-term arithmetic progression.

Clearly, any colouring of \([1,3k]\) that contains two blue or two green elements will yield a blue \(2\)-term arithmetic progression or a green \(2\)-term arithmetic progression.

Hence we consider a three colouring \(c:[1,3k]\to\{\mbox{red, blue, green}\}\) that colours at most one element of \([1,3k]\) blue and at most one element green.

Observe that if one of the colours blue or green is not used then there is a sequence of at least \(k\) consecutive red elements. Clearly, in this case there is a red \(k\)-term arithmetic progression.

Hence assume that \(c:[1,3k]\to\{\mbox{red, blue, green}\}\) is a colouring such that there is a unique \(x\in[1,3k]\) such that \(c(x)=\mbox{blue}\) and a unique \(y\in[1,3k]\) such that \(c(y)=\mbox{green}\text{.}\)

Suppose that \(y\lt x\text{.}\)

If \(y\gt k\) or \(x\lt 2k\) then there is a sequence of at least \(k\) consecutive red elements between \([1,y-1]\) or between \([x+1,3k]\text{,}\) i.e. there is a red \(k\)-term arithmetic progression.

Suppose that \(1\leq y\leq k\lt 2k\leq x\leq 3k\text{.}\) Observe that the number of elements between \(x\) and \(y\) is given by \(d=(x-1)-(y+1)+1=x-y-1\text{.}\)

Note that if \(y\lt k\) or \(x\gt 2k\) then \(d\geq k\text{,}\) which means that there is a sequence of at least \(k\) consecutive red elements between \(y\) and \(x\text{.}\)

Hence the only remaining case is if \(y=k\) and \(x=2k\text{.}\) Observe that, since \(k\equiv \pm 1(\mbox{mod } 6)\text{,}\) neither \(k\) nor \(2k\) is divisible by 3.This implies that all elements of the \(k\)-term arithmetic progression

are coloured red.

Therefore \(w(k,2,2;3)\leq 3k\) .

To prove \(w(k,2,2;3)\geq 3k\text{,}\) we must show that there is a \(3\)-colouring of \([1, 3k-1]\) which does not produce a red \(k\)-term arithmetic progression or a blue \(2\)-term arithmetic progression or a green \(2\)-term arithmetic progression.

Let the colouring \(c:[1,3k-1]\to\{\mbox{red, blue, green}\}\) be defined in the following way:

Let

be a \(k\)-term arithmetic progression contained in \([1,3k-1]\text{.}\)

Observe that \(d\in\{1,2,3\}\text{.}\) Otherwise \(a+(k-1)d\geq 1+4(k-1)=4k-3\) which is greater than \(3k-1\) for \(k\geq 5\text{.}\)

Since any set of \(k\) consecutive integers in \([1,3k-1]\) must contain the integer \(k\) or the integer \(2k\) we conclude that an arithmetic progression contained in \([1,3k]\) with the step \(d=1\) cannot be \(c\)-monochromatic.

If the arithmetic progression \(a,a+2,\ldots,a+2i,\ldots, a+2(k-1)\) is contained in \([1,3k-1]\) then \(a+2(k-1)\leq 3k-1\) implies that \(a\leq k+1\text{.}\)

If \(a\) is an odd number then, for some \(i\in\{0,1,\ldots,k-1\}\text{,}\) \(a+2i=k\) and the corresponding \(k\)-term arithmetic progression is not \(c\)-monochromatic.

If \(a\) is an even number then, for some \(i\in\{0,1,\ldots,k-1\}\text{,}\) \(a+2i=2k\) and the corresponding \(k\)-term arithmetic progression is not \(c\)-monochromatic.

If the arithmetic progression \(a,a+3,\ldots,a+2i,\ldots, a+3(k-1)\) is contained in \([1,3k-1]\) then \(a+3(k-1)\leq 3k-1\) implies that \(a\leq 2\text{.}\)

If \(a=1\) and \(k=6l+1\) then \(1+3\cdot(2l)=k\) and the corresponding \(k\)-term arithmetic progression is not \(c\)-monochromatic.

If \(a=1\) and \(k=6l-1\) then \(1+3\cdot(4l-1)=12l-2=2(6l-1)=2k\) and the corresponding \(k\)-term arithmetic progression is not \(c\)-monochromatic.

If \(a=2\) and \(k=6l+1\) then \(2+3\cdot(4l)=12l+2=2\cdot(6l+1)=2k\) and the corresponding \(k\)-term arithmetic progression is not \(c\)-monochromatic.

If \(a=2\) and \(k=6l-1\) then \(1+3\cdot(2l)=6l+1=k\) and the corresponding \(k\)-term arithmetic progression is not \(c\)-monochromatic.

Hence, the colouring \(c\) of \([1,3k-1]\) does not produce a red \(k\)-term arithmetic progression or a blue \(2\)-term arithmetic progression or a green \(2\)-term arithmetic progression which proves that \(w(k,2,2;3)\geq 3k\text{.}\)

Therefore, \(k=\pm 1(\mbox{mod } 6)\) implies \(w(k,2,2;3)=3k\text{.}\)

1. • Since there are only two red (\(R\)) elements, \(1\) and \(6\text{,}\) there is no a red \(3\)-term arithmetic progression.

   • There are four blue (\(B\)) elements, \(2,3,9\) and \(12\text{.}\) Clearly this set does not contain a \(3\)-term arithmetic progression.

   • There are three green (\(G\)) elements, \(4,8\) and \(13\text{.}\) These three elements do not form a \(3\)-term arithmetic progression.

   • There are four yellow (\(Y\)) elements, \(5,7,10\) and \(11\text{.}\) This set does not contain a \(3\)-term arithmetic progression.

2. For example,

   \begin{equation*} R \ \underline{B} \ B \ G \ Y \ R \ Y \ G \ \underline{B} \ Y \ Y \ B \ G \ Y \ B\ \underline{B}. \end{equation*}

Consider the set of all powers of 3, i.e. consider the set \(A=\{1,3,9,27,\ldots \}\text{.}\)

Let \(n \in \mathbb{N}\) and let \(k \in \mathbb{N}\cup\{0\}\) be such that \(3^k \leq n\lt 3^{k+1}\text{.}\) This is the same as

It follows that

By definition,

We prove the claim by mathematical induction on \(k\text{,}\) the number of colours.

For \(k=1\) and any \(l\in\mathbb{N}\) we take \(S(1, l) = l\text{.}\)

Assume that the claim is true for a fixed \(k\geq 1\) and any \(l\in \mathbb{N}\text{.}\) We fix \(l \in\mathbb{N}\) and denote by \(S(k,l)\) the corresponding number.

Next we define

where \(w(\ast, \ast)\) denotes a van der Waerden number.

Let the set of integers \([1,S(k+1, l)]\) be \((k+1)\)-coloured. Then, by van der Waerden's Theorem, there is a \(((l-1)S(k, l) + 1)\)-term monochromatic arithmetic progression

For every \(x = 1, 2, \ldots, S(k, l)d\) this monochromatic arithmetic progression contains the following \(l\)-term arithmetic progression:

If for one of the numbers \(x\text{,}\) the difference \(xd\) is coloured by the same colour as the original progression, we have concluded the proof of our induction step.

Otherwise, the \(S(k,l)\)-term arithmetic progression

is coloured in only \(k\) colours. Now we apply the inductive hypothesis to conclude that the \(k\)-coloured set \(\{d, 2d, \ldots S(k, l)d\}\subset [1,S(k+1,l)]\) contains a monochromatic arithmetic progression of length \(l\) together with its difference.

The question is to show that any red/blue colouring of \([1,10]\) must contain a red solution to \(x+y=z\) (of distinct integers) or a blue solution to \(x+y=2z\text{.}\)

We also need to show that there is a red/blue colouring of \([1,9]\) with no red solution to \(x+y=z\) (of distinct integers) or a blue solution to \(x+y=2z\text{.}\) The following colouring of \([1,9]\) achieves this:

Next we try to build a red/blue colouring of \([1,10]\) that avoids a red (\(R\)) solution to \(x+y=z\) (of distinct integers) or a blue (\(B\)) solution to \(x+y=2z\text{.}\)

We start by observing that such a colouring has to avoid monochromatic triples \(\{1,2,3\}\text{,}\) \(\{2,4,6\}\text{,}\) and \(\{3,6,9\}\) because these triples are both \(3\)-term arithmetic progressions and Schur's triples.

In our attempt to avoid a red solution to \(x+y=z\) (of distinct integers) or a blue solution to \(x+y=2z\text{,}\) we consider all possible colourings of the triple \(\{2,4,6\}\) with two colours, \(R\) and \(B\text{:}\)

• Case 1: If \(2=R,4=B,6=B\) then \(5=R\) (because of the arithmetic progression \(4,5,6\)). This implies \(7=B\) (because of \(2+5=7\)) and \(8=R\) (because of the arithmetic progression \(6,7,8\)) and \(10=R\) (because of the arithmetic progression \(4,7,10\)), But now, \(2,8,10\) is a red Schur's triple.

• Case 2: If \(2=B,4=R,6=B\) then \(10=R\) (because of the arithmetic progression \(2,6,10\)).

  Now, if \(3=B\) then \(1=R\) (because of the arithmetic progression \(1,2,3\)) and \(9=B\) (because of \(1+9=10\text{.}\)) But then \(3,6,9\) is a blue arithmetic progression.

  If \(3=R\) then \(7=B\) (because of \(3+4=7\)) and \(5=R\) (because of the arithmetic progression \(5,6,7\)) and \(8=R\) (because of the arithmetic progression \(6,7,8\)). But then \(3+5=8\) is a red Schur's triple.

• Case 3: If \(2=B,4=B,6=R\) then \(3=R\) (because of the arithmetic progression \(2,3,4\)). It follows that \(9=B\) (because of \(3+6=9\)).

  Now, if \(1=R\) then \(5=B\) (because of \(1+5=6\)) and \(7=B\) (because of \(1+6=7\text{.}\)) But then \(5,7,9\) is a blue arithmetic progression.

  If \(1=B\) then \(5=R\) (because of the arithmetic progression \(1,5,9\)) and \(7=B\) (because of \(1+6=7\text{.}\)) Also, \(8=B\) (because of \(3+5=8\)). This implies \(7=R\) (because of the arithmetic progression \(7,8,9\)) and then \(10=R\) (because of the arithmetic progression \(8,9,10\)). Now, \(3+7=10\) is a red Schur's triple.

• Case 4: Let \(2=R,4=R,6=B\text{.}\)

  Now, if \(3=R\) then \(5=B\) (because of \(2+3=5\)) and \(7=B\) (because of \(3+4=7\text{.}\)) But then \(5,6,7\) is a blue arithmetic progression.

  If \(3=B\) then \(9=R\) (because of the arithmetic progression \(3,6,9\)) and \(5=B\) (because of \(4+5=9\)) and \(7=B\) (because of \(2+7=9\)). Now, \(5,6,7\) is a blue arithmetic progression.

• Case 5: If \(2=R,4=B,6=R\) then \(8=B\) (because of \(2+6=8\)).

  Now, if \(5=R\) then \(1=B\) (because of \(1+5=6\)), \(3=B\) (because of \(2+3=5\text{.}\) and \(7=B\) (because of \(2+5=7\text{.}\)) But then \(1,4,7\) is a blue arithmetic progression.

  If \(5=B\) then \(3=R\) (because of the arithmetic progression \(3,4,5\)) and \(1=B\) (because of \(1+2=3\)) and \(7=R\) (because of the arithmetic progression \(1,4,7\)). Now, if \(9=B\) (because of \(2+7=9\)), then \(1,5,9\) is a blue arithmetic progression.

• Case 5: If \(2=B,4=R,6=R\) then \(10=B\) (because of \(4+6=10\)).

  Now, if \(3=R\) then \(1=B\) (because of \(1+3=4\)), \(7=B\) (because of \(3+4=7\text{.}\) and \(9=B\) (because of \(3+6=9\text{.}\)) It follows that \(8=R\) (because of the arithmetic progression \(8,9,10\)) and \(5=B\) (because of \(3+5=8\)). But then \(1,5,9\) is a blue arithmetic progression.

  If \(3=B\) then \(1=R\) (because of the arithmetic progression \(1,2,3\)) and \(5=B\) (because of \(1+4=5\)) and \(7=B\) (because of \(1+6=7\)) . But then \(3,5,7\) is a blue arithmetic progression.

Yes, the given equation is partition regular over \(\mathbb{N}\text{.}\) If we look at all the coefficients: \(c_1=1,c_2=-1,c_3=5,c_4=-3\text{,}\) the sum of the coefficients \(c_1\) and \(c_2\) turns out to be equal to 0. Hence, by Rado's theorem this equation is partition regular, i.e it has a monochromatic solution for any finite colouring of the set of natural numbers.

On the Rado graph, vertex 3 will be connected to vertices that have a non-zero 3rd bit of the binary representation. Vertex 9 in binary representation is \(1001\text{.}\) The 3rd bit of \(1001\) is 0, therefore vertex 3 will not be connected to vertex 9.

1. Each word on the 2-dimensional cube corresponds to a position on the tic-tac-toe board.

   

2. Below is the list of all the roots in \(A^2\) together with the corresponding combinatorial line:

   \begin{equation*} \tau_1 = * 1 \implies L_{\tau_1}=\{1\:1, 2\:1, 3\:1\} \end{equation*}
   \begin{equation*} \tau_2 = * 2 \implies L_{\tau_2}=\{1\:2, 2\:2, 3\:2\} \end{equation*}
   \begin{equation*} \tau_3 = * 3 \implies L_{\tau_3}=\{1\:3, 2\:3, 3\:3\} \end{equation*}
   \begin{equation*} \tau_4 = 1 * \implies L_{\tau_4}=\{1\:1, 1\:2, 1\:3\} \end{equation*}
   \begin{equation*} \tau_5 = 2 * \implies L_{\tau_5}=\{2\:1, 2\:2, 2\:3\} \end{equation*}
   \begin{equation*} \tau_6 = 3 * \implies L_{\tau_6}=\{3\:1, 3\:2, 3\:3\} \end{equation*}
   \begin{equation*} \tau_7 = * * \implies L_{\tau_7}=\{1\:1, 2\:2, 3\:3\} \end{equation*}

   Based on the tic-tac-toe board, we can see that \(\tau_1, \tau_2, \tau_3\) correspond to a horizontal winning line in each row, \(\tau_4, \tau_5, \tau_6\) correspond to a vertical winning line in each column, and \(\tau_7\) is the diagonal winning line starting at \(1\:1\) and finishing at \(3\:3\text{.}\)

   One winning line that cannot be represented by a combinatorial line is \(\{3\:1, 2\:2, 1\:3\}\text{.}\) This is because there is no root to represent this line. We can see that each word is changing in more than one position and to different letters.

3. We can see that \(L_2\) is not a combinatorial line. Observe that the line \(L_2\) begins at \((1,2,4)\) and ends at \((4,2,1)\text{.}\) This means \(L_2\) contains the points \(\{1\:2\:4, 2\:2\:3, 3\:2\:2, 4\:2\:1 \}\text{.}\) Since the first and third letter in each word change to different letters at different times, this set of words cannot be obtained from a root. It follows that \(L_2\) is not a combinatorial line.

   The corresponding roots and lines for the rest are:

   \begin{equation*} \tau_1 = *32 \implies L_{\tau_1}=L_1=\{1\:3\:2, 2\:3\:2, 3\:3\:2, 4\:3\:2 \} \end{equation*}
   \begin{equation*} \tau_3 = *** \implies L_{\tau_3}=L_3=\{1\:1\:1, 2\:2\:2, 3\:3\:3, 4\:4\:4 \} \end{equation*}
   \begin{equation*} \tau_4 = 24* \implies L_{\tau_4}=L_4==\{2\:4\:1, 2\:4\:2, 2\:4\:3, 2\:4\:4 \} \end{equation*}

Let \(A=\{1,2\}\text{.}\) Observe that \(A^2=\{1\;1,1\;2,2\;1,2\;2\}\text{.}\)

Let \(c\) be any \(2\)-colouring of \(A^2\text{.}\) Consider the set \(A^\prime=\{1\;1,1\;2,2\;2\}\subset A^2\text{.}\) By the pigeonhole principle, there are at least two elements in \(A^\prime\) that are coloured by the same colour. Observe that those two elements form a \(c\)-monochromatic combinatorial line in \(A^2\text{.}\)

Hence \(HJ(2,2)=2\text{.}\)

In Exercise 47.1.16 we have established that this is true for \(n=2\text{.}\)

Let \(n\geq 3\) and let \(A=\{1,2,\ldots,n\}\) be an alphabet. Let \(c\) be a \(2\)-colouring of \(A^2\) defined in the following way:

Recall that all combinatorial lines is \(A^2\) are determined by one of the roots \(\ast\; i\text{,}\) \(i\; \ast\text{,}\) where \(i\in [1,n]\text{,}\) and \(\ast\; \ast\text{.}\)

Since, for any \(i\in [1,n]\text{,}\) the words \(2\; i\) and \(n\; i\) are of different colours, the combinatorial line generated by the root \(\ast\; i\) is not \(c\)-monochromatic. Similarly, for any \(i\in [1,n]\) the combinatorial line generated by the root \(i\; \ast \) is not \(c\)-monochromatic.

Finally, the combinatorial linedetermined by the root \(\ast\; \ast\) is not \(c\)-monochromatic because the words \(1\; 1\) and \(n\; n\) are not of the same colour.

Therefore, only if \(n=2\text{,}\) any \(2\)-colouring of \([1, n]^2\) will always contains a monochromatic combinatorial line with length \(n\)