Skip to main content

Section 4.5 Exercises

These exercises are based on the material covered in Chapter 4.

Write a short essay (300-400 words) on the life and work of Issai Schur.

Write a short essay (300-400 words) on the life and work of Richard Rado.

Show that

\begin{equation*} s(r)\leq R( \underbrace{3,3,\ldots,3}_r)-1\text{,} \end{equation*}

where \(s(r)\) is the Schur number for \(r\) colours.

Solution

Let \(c\) be an \(r\)-colouring of the interval \([1,R( \underbrace{3,3,\ldots,3}_r)-1]\text{.}\) Consider the complete graph on \(R( \underbrace{3,3,\ldots,3}_r)\) vertices denoted by \(1,2,\ldots, R( \underbrace{3,3,\ldots,3}_r)\text{.}\) Define an \(r\)-colouring \(c'\) of the edges of this complete graph by

\begin{equation*} c'(\{a,b\})=c(|a-b|) \end{equation*}

where \(\{a,b\}\) is the edge between the vertices \(a\) and \(b\text{.}\) We observe that, for any \(a,b\in [1,R( \underbrace{3,3,\ldots,3}_r)]\text{,}\)

\begin{equation*} |a-b|\leq R( \underbrace{3,3,\ldots,3}_r)-1 \end{equation*}

and hence the colouring \(c'\) is well-defined. By definition of \(R( \underbrace{3,3,\ldots,3}_r)\) the complete graph contains a monochromatic triangle, i.e., there are \(i,j,k\text{,}\) \(i\lt j\lt k\text{,}\) such that

\begin{equation*} c'(\{i,j\})=c'(\{i,k\})=c'(\{j,k\}) \end{equation*}

which is the same as

\begin{equation*} c(j-i)=c(k-i)=c(k-j)\text{.} \end{equation*}

Setting \(x=j-i\text{,}\) \(y=k-j\text{,}\) and \(z=k-i\) we observe that

\begin{equation*} x,y,z \in [1,R( \underbrace{3,3,\ldots,3}_r)-1], \ x+y=z,\mbox{ and } c(x)=x(y)=c(z)\text{.} \end{equation*}

Therefore \(x,y,z\) is a \(c\)-monochromatic Schur triple.

This proofs that any \(r\)-colouring of \([1,R( \underbrace{3,3,\ldots,3}_r)-1]\) contains a monochromatic Schur triple. Therefore

\begin{equation*} s(r)\leq R( \underbrace{3,3,\ldots,3}_r)-1\text{.} \end{equation*}

  1. Find a red/blue colouring of \(\{1,2,3,4,5,6,7\}\) that contains neither a red Schur triple nor a blue 3-term arithmetic progression.

  2. Show that any red/blue colouring of \(\{1,2,3,4,5,6,7,8\}\) contains a red Schur triple or a blue 3-term arithmetic progression.

Solution

  1. Consider the positive numbers from 1 to 7.

    Figure 4.5.5. Positive numbers from 1 to 7.

    Colour the number 1 red:

    Figure 4.5.6. Colour 1 red.

    We try to colour \([1,7]\) to avoid red Schur triples and blue 3-term arithmetic progressions. Note that 2 must be blue. (Figure 4.5.7.)

    Figure 4.5.7. Colour 1 red and 2 blue.

    Suppose that 3 is red. Then 6 must blue. This forces 4 to be red, but then there is a red Schur triple \(1,3,4\text{.}\) (Figure 4.5.8.)

    Figure 4.5.8. Colour 3 red.

    Suppose that 3 is blue. Then 4 must red, 5 must be blue, 7 must be red, and 6 must be blue. (Figure 4.5.9.)

    Figure 4.5.9. Colouring R-B-B-R-B-B-R.

    Colour 1 blue and 2 red. Then 4 must be blue, 7 must be red, 5 must be blue. None of 3 and 6 can be blue, but if both of them are red, then there is a red Schur triple \(3,3,6\text{.}\) (Figure 4.5.10.)

    Figure 4.5.10. Colour 1 blue and 2 red.

    Colour 1 and 2 blue. Then 3 must be red, 6 must be blue, 4 must be red, 7 must be blue, and 5 must be red. (Figure 4.5.11.)

    Figure 4.5.11. Colouring B-B-R-R-R-B-B.

    Hence there are only two blue-red colourings of \([1,7]\) that avoid red Schur triples and blue 3-term arithmetic progressions: R-B-B-R-B-B-R and B-B-R-R-R-B-B.

  2. Consider the R-B-B-R-B-B-R colouring of \([1,7]\text{.}\) If we colour 8 red then there is a red Schur triple \(1,7,8\text{.}\) If we colour 8 blue then there is able 3-term arithmetic progression \(3,5,8\text{.}\)

    Consider the B-B-R-R-R-B-B colouring of \([1,7]\text{.}\) If we colour 8 red then there is a red Schur triple \(3,5,8\text{.}\) If we colour 8 blue then there is a blue 3-term arithmetic progression \(6,7,8\text{.}\)

    Therefore any blue/red-colouring of \([1,8]\) contains a red Schur triple or a blue 3-term arithmetic progression.

Is the following equation partition regular over \(\mathbb{N}\text{:}\)

\begin{equation*} \frac{1}{3}x_1-\frac{1}{4}x_2+2x_3-\frac{1}{12}x_4=0? \end{equation*}

Justify your answer.

Solution

Notice that the given equation is equivalent to the equation

\begin{equation*} 4x_1-3x_2+24x_3-x_4=0\text{.} \end{equation*}

Since \(a_1+a_2+a_4=4-3-1=0\text{,}\) by Rado's theorem this equation is partition regular over \(\mathbb{N}\text{,}\) i.e., any finite colouring of positive integers contains a monochromatic solution of this equation. But that implies that any finite colouring of positive integers contains a monochromatic solution of the original equation. Therefore, the given equation is partition regular over \(\mathbb{N}\text{.}\)

Let the equation

\begin{equation*} x_1+x_2-4x_3=0 \end{equation*}

be given. Is it possible to find a finite colouring that does not contain monochromatic solutions of the given equation? If it is, find such a colouring. If it is not, justify your answer.

Solution

Here \(a_1=a-2=1\) and \(a_3=-4\text{.}\) From \(a_1+a_2=2\text{,}\) \(a_1+a_3=-3\text{,}\) \(a_2+a_3=-3\text{,}\) and \(a_1+a_2+a_3=-2\) we conclude, via Rado's theorem, that the given equation is not partition regular over \(\mathbb{N}\text{.}\) Therefore, there is a finite colouring of positive integers that does not contain a monochromatic solution of the given equation. By the proof of Rado's theorem that was demonstrated in the class, the following colouring would do.

Note that \(|a_1|+|a_2|+|a_3|=1+1+4=6\text{.}\) We take \(p=7\text{,}\) a prime number greater than \(|a_1|+|a_2|+|a_3|\text{,}\) and defined a 6-colouring \(c:\mathbb{N}\to [1,6]\) in the following way.

For \(n\in \mathbb{N}\) we find \(k,l\in \{ 0,1,2\ldots\}\) and \(i\in \{1,2,3,4,5,6\}\) such that \(n=7^k(7\cdot l+i)\text{.}\) Then, by definition,

\begin{equation*} c(n)=c(7^k(7\cdot l+i))=i\text{.} \end{equation*}

Now if there is a \(c\)-monochromatic solution of the given equation then

\begin{equation*} x_1=7^k(7\cdot l+i), x_2=7^m(7\cdot n+i), x_3=7^r(7\cdot s+i)\text{,} \end{equation*}

for some \(k,l,m,n,r,s\in \{ 0,1,2\ldots\}\) and \(i\in \{1,2,3,4,5,6\}\text{.}\) Hence

\begin{align*} 0\amp =\amp 7^k(7\cdot l+i)+7^m(7\cdot n+i)-4\cdot 7^r(7\cdot s+i) \end{align*}

If \(k=m=r\) then it follows that

\begin{align*} 0\amp =\amp (7\cdot l+i)+(7\cdot n+i)-4\cdot (7\cdot s+i)\\ \amp =\amp 7\cdot (l+n+s)-2i\text{.} \end{align*}

This would imply that \(2i\) is divisible by 7, what is impossible because \(i\in \{1,2,3,4,5,6\}\text{.}\)

Other cases, lead to a contradiction in a similar way.