Past exam of the mathematics course of the University of Cambridge / 2001 / iii / Paper 10 / 1 / Solution

Write $\chi$ for the red-blue finite colouring of unordered pairs. The two alternatives concern one arithmetic progression or a pair of disjoint arithmetic progressions; they need not be mutually exclusive. For $m=1$, a singleton already has no non-blue edge, so the first alternative holds. Assume henceforth $m\ge 2$.

If the first alternative fails, every $m$-term arithmetic progression contains a red pair. Label each $(a,d)\in {\mathbb{N}}^2$ by one such pair's positions $0\le r<s<m$, choosing the first in a fixed ordering when there are several. This is a finite colouring with at most $\left(\genfrac{}{}{0ex}{}{m}{2}\right)$ colours. The following two branches establish the arithmetic-progression bipartite Ramsey dichotomy.