Skip to main content

Section 2.5 Exercises

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

Write a short essay (300-400 words) on the life and work of Paul Erdős.

Colour each point in the \(xy\) plane having integer coefficients Red or Blue. Then some rectangle has all its vertices the same colour.

Solution

There exists a 3 by 9 grid in the \(xy\)-plane. By the result from Example 2.1.7, there exists a rectangle with monochromatic vertices in the grid and hence in the whole \(xy\)-plane.

If \(a_1, a_2, \dots, a_{n+1} \in [1, 2n]\) are distinct, then there exist \(i ,j\text{,}\) \(i\neq j\text{,}\) such that \(a_i\) divides \(a_j\text{.}\) (This was one of Erdős' favourite questions to ask of an \(\epsilon\text{.}\))

Solution

Choose \(\{ a_1,\ldots, a_{n+1}\}\) from \([1, 2n]\text{,}\) so that they are distinct. We will show that there exists \(i \not= j\) such that \(a_i\) divides \(a_j\) or \(a_j\) divides \(a_i\text{.}\)

For each \(i\text{,}\) we may write ai as follows:

\begin{equation*} a_i = 2^{b_i} q_i \end{equation*}

where \(q_i\) is an odd number. Consider the numbers \(\{q_1,q_2,\ldots, q_{n+1}\}\text{,}\) a set of of \(n + 1\) odd numbers in \([1, 2n]\text{.}\) Since there are only \(n\) odd numbers in the range \([1, n]\text{,}\) we conclude that, for some \(i \not= j\text{,}\) \(q_i = q_j\text{.}\) Let \(q = q_i = q_j\text{.}\) Then

\begin{equation*} a_i = 2^{b_i} q \text{ and } a_j = 2^{b_j} q\text{.} \end{equation*}

Since \(a_i \not= a_j\text{,}\) we have that either \(b_i > b_j\) or \(b_j > b_i\text{.}\) In the former case, we have that \(a_j | a_i\) and in the latter case, \(a_i | a_j\text{,}\) as required.

Place the numbers \(1,2, \dots , 12\) around a circle, in any order. Then there are three consecutive numbers which sum to at least 19.

Solution

Given the number \(1, 2, .\ldots , 12\) placed around a circle, in some order, partition the circle into 4 equal sections, each containing 3 consecutive numbers. Let \(A_1\text{,}\) \(A_2\text{,}\) \(A_3\text{,}\) and \(A_4\) be the four sets of consecutive numbers.

We wish to show that \(\displaystyle \sum_{a\in A_j}a \geq 19\) for some \(j \in \{1,2,3,4\}\text{.}\) Let \(a_j = \sum_{a\in A_j}a\) for \(j=1,2,3,4\text{.}\) We know that

\begin{equation*} a_1 +a_2 +a_3 +a_4 =\sum_{b=1}^{12} b=78\text{.} \end{equation*}

By the generalized pigeon-hole principle, we have that some \(a_i\) for \(i \in \{1, 2, 3, 4\}\) has the property that

\begin{equation*} a_i \geq \left\lfloor \frac{78}{4}\right\rfloor = \lfloor19.5\rfloor = 19\text{,} \end{equation*}

as required.

Show that \(R(3,3,3)\le 17\text{.}\) (This means: Every 3-colouring of the edges of \(K_{17}\) gives a monochromatic \(K_3\text{.}\))

Solution

Consider any \(3\)–edge–colouring \(c\) of \(K_{17}\) with colours \(c_1\text{,}\) \(c_2\text{,}\) \(c_3\text{.}\) (This means that for \(e\text{,}\) an edge of \(K_{17}\text{,}\) \(c(e)\) denotes the colour of the edge \(e\text{.}\)) We will show that there exists a monochromatic \(K_3\text{.}\)

Let \(x\) be any vertex in \(K_{17}\text{.}\) The vertex \(x\) is incident to \(16\) edges, coloured with one of the three colours. By the generalized pigeonhole principle, we have that there is a colour \(c_i\) such that \(x\) is incident to \(6\) edges with colour \(c_i\text{.}\)

Let \(Y =\{y_1, \ldots, y_6\}\) be the six neighbours of \(x\text{,}\) i.e. the six vertices which are joined to \(x\) by an edge of the colour \(c_i\text{.}\) If any edge joining two vertices in \(Y\) is also coloured with colour \(c_i\text{,}\) then they form a monochromatic \(K_3\) with \(x\) as its vertex and we are done.

Otherwise, every edge joining vertices of \(Y\) is not coloured with colour \(c_i\text{.}\) Then, the vertices of \(Y\) induce a subgraph of \(K_{17}\) that is a copy of \(K_6\text{,}\) edge–coloured with two colours. By Ramsey's theorem every \(2\)-colouring of \(K_6\) contains a monochromatic \(K_3\text{,}\) and the result follows.

Let

\begin{equation*} y_1,y_2,y_3, \ldots \end{equation*}

be a sequence of mutually distinct real numbers. Use Ramsey's theorem to prove that the sequence

\begin{equation*} (1,y_1),(2,y_2),(3,y_3), \ldots \end{equation*}

of points in \(\mathbb{R}^2\) contains a subsequence such that the induced function is convex or concave.

Solution

A function is convex if its epigraph (the set of points on or above the graph of the function) is a convex set, i.e., any line segment that connect two points in the epigraph also belongs to the epigraph. A function \(f\) is concave if the function \(-f\) is convex.

Note that any linear function is both convex and concave. For the purpose of this problem we will take a linear function to be convex.

Let \(i,j,k\in \mathbb{N}\) be such that \(i\lt j\lt k\text{.}\) Since \(y_i\not=y_j\text{,}\) \(y_i\not=y_k\text{,}\) and \(y_j\not=y_k\) there are these possibilities:

Figure 2.5.8. The induced function is convex.
Figure 2.5.9. The induced function is concave.

We 2-colour \(\mathbb{N}^{(3)}\) in the following way:

  • Colour \(\{i,j,k\}\text{,}\) \(i\lt j\lt k\text{,}\) blue if the points \((i,y_i),(j,y_j), (k,y_k)\) induce a convex function.

  • Colour \(\{i,j,k\}\text{,}\) \(i\lt j\lt k\text{,}\) red if the points \((i,y_i),(j,y_j), (k,y_k)\) induce a concave function.

By Ramsey's theorem there is an infinite monochromatic set

\begin{equation*} i_1\lt i_2\lt i_3\lt \ldots\text{.} \end{equation*}

This means that that, for any \(p,q,r\in \mathbb{N}\text{,}\) the set \(\{i_p,i_q,i_r\}\) is always of the same colour.

Say that colour is blue. In particular this means that for any \(j\) the function induced by

\begin{equation*} (i_j,y_{i_j}),(i_{j+1},y_{i_{j+1}}), (i_{j+2},y_{i_{j+2}}) \end{equation*}

is convex.

Consider two points \((x,y)\) and \((x',y')\text{,}\) \(x\lt x'\text{,}\) in the epigraph of the function \(f\) induced by the sequence of points

\begin{equation*} (i_1,y_{i_1}),(i_2,y_{i_2}),(i_3,y_{i_3}), \ldots\text{.} \end{equation*}

If there is \(j\in \mathbb{N}\) such that

\begin{equation*} i_j\leq x\lt x'\leq i_{j+1} \end{equation*}

then the line segment with the end points \((x,y)\) and \((x',y')\) is on or above the line segment with the end points \((i_j,y_{i_j}),(i_{j+1},y_{i_{j+1}})\) and thus in the epigraph of the function \(f\text{.}\)

Otherwise, there are \(j\) and \(k\geq 3\) such that

\begin{equation*} i_j\lt x\leq i_{j+1}\lt i_{j+k-1}\leq x'\lt i_{j+k}\text{.} \end{equation*}

Let

\begin{equation*} z_ {i_{j+1}}, z_ {i_{j+2}},\ldots, z_ {i_{j+k-1}} \end{equation*}

be such that, for any \(l\in [1,k-1]\text{,}\) the point \((i_{j+l},z_{i_{j+l}})\) belongs to the line segment with the end points \((x,y)\) and \((x',y')\text{.}\) See Figure 2.5.10.

As above, line segments with the end points \((i_{j+l},z_{i_{j+l}})\) and \((i_{j+l+1},z_{i_{j+l+1}})\text{,}\) \(l\in[1,k-2]\text{,}\) belong to the epigraph of the function \(f\text{.}\) It follows that their union, the line segment with the end points \((i_{j},z_{i_{j}})\) and \((i_{j+k-1},z_{i_{j+k-1}})\) belongs to the epigraph of the function \(f\text{.}\) Finally, if \(x\not= i_{j}\) and/or \(x'\not= i_{j+k-1}\) the segments with end points \((x,y)\) and \((i_j,z_{i_j})\) and with the endpoints \((i_{j+k-1},z_{i_{j+k-1}})\) and \((x',y')\) belong to the epigraph of the function \(f\text{.}\) This implies that the line segment with the end points \((x,y)\) and \((x',y')\) belongs to the epigraph of the function \(f\text{.}\)

Therefore, the function \(f\) is convex.

Now we consider the case that for any \(p,q,r\text{,}\) the set \(\{i_p,i_q,i_r\}\) is always coloured red. In particular this means that for any \(p,q,r\) the function induced by

\begin{equation*} (i_p,y_{i_p}),(i_{q},y_{i_{q}}), (i_{r},y_{i_{r}}) \end{equation*}

is concave. By definition, for any \(p,q,r\) the function induced by

\begin{equation*} (i_p,-y_{i_p}),(i_{q},-y_{i_{q}}), (i_{r},-y_{i_{r}}) \end{equation*}

is convex, and as we have already seen, the function \(g\) induced by by the sequence of points

\begin{equation*} (i_1,-y_{i_1}),(i_2,-y_{i_2}),(i_3,-y_{i_3}), \ldots \end{equation*}

is convex. It follows that the function \(-g\) induced by by the sequence of points

\begin{equation*} (i_1,y_{i_1}),(i_2,y_{i_2}),(i_3,y_{i_3}), \ldots \end{equation*}

is concave.

Figure 2.5.10. It is convex!

Let

\begin{equation*} y_1,y_2,y_3, \ldots \end{equation*}

be a sequence of real numbers. Use Ramsey's theorem to prove that that the sequence

\begin{equation*} (1,y_1),(2,y_2),(3,y_3), \ldots \end{equation*}

of points in \(\mathbb{R}^2\) contains a subsequence such that the induced function is constant, convex or concave.

Solution

Let a 3-colouring of \(\mathbb{N}^{(3)}\) be defined in the following way:

  • Colour \(\{ i,j,k\}\text{,}\) \(i\lt j\lt k\text{,}\) green if \(y_i=y_j=y_k\text{.}\)

  • Colour \(\{i,j,k\}\text{,}\) \(i\lt j\lt k\text{,}\) blue if not all of \(y_i,y_j,y_k\) are not mutually equal and if the points \((i,y_i),(j,y_j), (k,y_k)\) induce a convex function.

  • Colour \(\{i,j,k\}\text{,}\) \(i\lt j\lt k\text{,}\) red if not all of \(y_i,y_j,y_k\) are not mutually equal and if the points \((i,y_i),(j,y_j), (k,y_k)\) induce a concave function.

By Ramsey's theorem there is an infinite monochromatic set:

\begin{equation*} i_1\lt i_2\lt i_3\lt \ldots\text{.} \end{equation*}

This means that, for any \(p,q,r\text{,}\) the set \(\{i_p,i_q,i_r\}\) is always of the same colour.

If {\(\{ i_p,i_q,i_r\}\)} for any \(p,q,r\) then \(y_{i_p}=y_{i_q}=y_{i_r}\) and the induced function is a constant.

If {\(\{ i_p,i_q,i_r\}\)} for any \(p,q,r\) then \(y_p,y_q,y_r\) are not mutually equal and the points \((i_p,y_{i_p}),(i_q,y_{i_q}), (i_r,y_{i_r})\) induce a convex function. By the previous problem the function induce by \(i_1\lt i_2\lt i_3\lt \ldots\) is convex.

If {\(\{ i_p,i_q,i_r\}\)} for any \(p,q,r\) then \(y_p,y_q,y_r\) are not mutually equal and the points \((i_p,y_{i_p}),(i_q,y_{i_q}), (i_r,y_{i_r})\) induce a concave function. By the previous problem the function induce by \(i_1\lt i_2\lt i_3\lt \ldots\) is concave.