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

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.

If an $m$-term arithmetic progression contains no red pair, all of its unordered pairs are blue, since there are only two colours. This gives the first alternative, including the vacuous singleton case. Otherwise the position-pair finite colouring in the root solution is defined everywhere, and the construction below forces the second alternative.

Apply the Gallai theorem for an integer lattice to the finite patternAlthough some coordinates are negative, translating $F$ into the positive quadrant and applying the positive-lattice theorem produces a monochromatic copy $F_0=(a_0,d_0)+qF\subseteq {\mathbb{N}}^2$, with integer $q>0$. The translation is absorbed into $(a_0,d_0)$. Let $(r,s)$ be the common position-pair label on this copy.

For each $0\le u,v<m$, the starting point and steplabel the red edge at positions $r,s$. Its endpoints simplify toThus the two arithmetic progressionshave a positive common difference $q(s-r)$, and every cross-pair is red. Their entries are positive because they occur as endpoints of the positive-start, positive-step progressions represented in $F_0$.

It remains to check disjointness, rather than infer it merely from distinct starting points. The pattern contains points whose second coordinate is $-(m-1)$. Since all of $F_0$ lies in ${\mathbb{N}}^2$,ConsequentlyTherefore $A$ and $B$ are disjoint $m$-term arithmetic progressions with every cross-edge red. Combined with the first branch, this proves the dichotomy.