Past exam of the mathematics course of the University of Cambridge / 2017 / iii / Paper 130 / 1

Write $\mathbb{N}=\{1,2,\dots \}$ and let $\chi$ be the given finite coloring of the edges of the complete graph on the positive integers. Construct an increasing sequence $(v_i)$ and nested infinite sets $A_0\supset A_1\supset \cdots$ as follows. Set $A_0=\mathbb{N}$. Having chosen $A_{i-1}$, take $v_i=\min A_{i-1}$, partition $A_{i-1}\setminus \{v_i\}$ by the color of $\{v_i,w\}$, and use the infinite pigeonhole principle to choose an infinite set $A_i$ on which this color is constant, say $r_i$. Every element of $A_i$ exceeds $v_i$.

The infinite pigeonhole principle applied again to $(r_i)$ gives an infinite set of indices $I$ and a color $r$ such that $r_i=r$ for all $i\in I$. For $i<j$ in $I$, nesting gives $v_j\in A_i$, so $\chi (\{v_i,v_j\})=r$. Thus the infinite set $X=\{v_i:i\in I\}$ is a monochromatic complete graph:This proves the required infinite case of Ramsey's theorem; finiteness of the color set is used at both applications of the infinite pigeonhole principle.

Pull the given finite coloring $\chi :\mathbb{N}\to [k]$ back to a finite coloring of unordered pairs by puttingThe ordering $a<b$ makes this a well-defined function on the edges of a complete graph. By Ramsey's theorem, some infinite set $X=\{x_1<x_2<\cdots \}$ has all its pairs of one color $r$ under $\tilde{\chi }$. ConsequentlyPossible coincidences between these products cause no difficulty, since the original finite coloring assigns each positive integer a single color.

Use the cyclic logarithmic coloringHere the floor function places $x$ in the unique half-open real interval $[(3/2{)}^j,(3/2{)}^{j+1})$. If $y/x\in [1.9,2]$, thenbecause $3/2<1.9\le 2<(3/2{)}^2$. For any real $t$ and $1<u<2$, $\lfloor t+u\rfloor -\lfloor t\rfloor$ is either $1$ or $2$. Applying this to the logarithms of $x$ and $y$ shows that their bin indices differ by $1$ or $2$, and hence have different residues in modular arithmetic modulo $3$. This proves the required separation, including both endpoints of the prescribed ratio interval. The half-open bins remove any ambiguity at their boundaries.

Let $\rho$ be the cyclic logarithmic coloring from part (iii). Define a finite coloring of the positive integers byThe inner logarithm is at least $1$ whenever $n\ge 2$, so this is defined everywhere. Suppose an increasing infinite sequence $(x_i)$ made every product with distinct indices monochromatic. Fix an index $i$ with $x_i\ge 2$ and write $a={\log }_2{x}_i>0$. The sequence is unbounded, so choose $j>i$ with $b={\log }_2{x}_j\ge 28a$. Both ordered products are among the supposedly monochromatic values, but their logarithms satisfyIndeed, the first inequality is equivalent to $b\ge 28a$, and the second uses $a>0$. Part (iii) therefore gives $\chi (x_i{x}_j^2)\ne \chi (x_j{x}_i^2)$, a contradiction. Thus the assertion with all distinct ordered indices is false. The obstruction needs an infinite unbounded sequence; it does not assert that every pair of different positive integers gives different colors.