Past exam of the mathematics course of the University of Cambridge / 2001 / iii / Paper 10 (Ramsey Theory)

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.

A combinatorial line in $[k{]}^N$ fixes all coordinates outside a nonempty set $J$ and puts the same variable letter in every coordinate of $J$. The Hales-Jewett theorem asserts that for every $k,r\ge 1$, some $N$ forces a monochromatic combinatorial line in every $r$-colouring of $[k{]}^N$. We prove it by mathematical induction on $k$, using an explicit alphabet insensitivity lemma.

A $d$-dimensional combinatorial subspace fixes some coordinates and has $d$ disjoint nonempty variable blocks. It is $(a,b)$-insensitive if changing any parameter from $a$ to $b$ or back leaves the colour unchanged. For $k\ge 2$, fixed $a\ne b\in [k]$, $r$ colours and any required dimension $d$, we now construct such a subspace without assuming the Hales-Jewett theorem.

Choose consecutive blocks of lengths $L_1,\dots ,L_d$ byProcess blocks from right to left. When processing block $i$, the later blocks already have their variable templates. For each $0\le t\le L_i$, consider $a^t{b}^{L_i-t}$ in block $i$. Record its colour profile for every earlier word in $[k{]}^{P_i}$ and every assignment of the $d-i$ later parameters. There are $k^{P_i+d-i}$ contexts and at most $r^{k^{P_i+d-i}}=L_i$ profiles. The $L_i+1$ chain words therefore contain two equal profiles by the pigeonhole principle.

If their indices are $s<t$, replace the block by the variable templateIts active block is nonempty. The values $v=a,b$ recover those two equal-profile words, so the colour is unchanged by interchanging $a,b$, for every earlier word and every later parameter assignment. Insensitivity already established in a later block persists, since it was established uniformly over all earlier words, including every subsequent restriction of block $i$. Continuing leftward gives the promised $d$-dimensional combinatorial subspace. This proves the explicit block bound for alphabet insensitivity and its required uniformity.

The one-letter case of the Hales-Jewett theorem is immediate: take $N=1$. Suppose it is proved for $k-1$ letters and every number of colours. Let $d$ be a dimension guaranteed for $k-1$ letters and $r$ colours. Obtain a $d$-dimensional $(k-1,k)$-insensitive combinatorial subspace by the lemma. Restrict its parameter alphabet to $[k-1]$ and apply the induction hypothesis. The resulting monochromatic combinatorial line uses some nonempty set of parameters. Its extra $k$-letter point has the same colour as its $(k-1)$-letter point: interchange $k-1,k$ in those parameters one at a time. The union of their active blocks is nonempty, so the extended line is a genuine combinatorial line in the original word space. This completes the letter-merging proof of the Hales-Jewett theorem.

To deduce the Van der Waerden theorem, take alphabet $\{0,\dots ,m-1\}$ and pull a finite colouring of the positive integers back byA monochromatic combinatorial line with active set $J$ maps toThus every finite colouring of the positive integers contains a monochromatic arithmetic progression of each prescribed finite length. Since the map only uses $[1,1+N(m-1)]$, this also gives the finite interval version, with an interval bound $W(r,m)$.

The Strengthened Van der Waerden theorem requires the common difference to have the same colour: for every $r,m$ some finite interval forces a monochromatic setFor $m=1$, take $a=d=1$. For $m\ge 2$, prove the assertion by mathematical induction on $r$, writing $B(r,m)$ for a sufficient interval bound. The one-colour case has $a=d=1$ and $B(1,m)=m$. Suppose $M=B(r-1,m)$ is known. Apply the ordinary Van der Waerden theorem to find a monochromatic progressionin $[N]$, where $N=W(r,L)$; call its colour $\gamma$. As $(L-1)d<N$, every point $td$ with $1\le t\le M$ also lies in $[N]$.

If one such $td$ has colour $\gamma$, the $m$ points $a,a+td,\dots ,a+(m-1)td$ lie in the original progression and have that colour, together with their difference $td$. Otherwise the pulled-back finite colouring $t\mapsto \chi (td)$ on $[M]$ uses at most $r-1$ colours. By the induction hypothesis it contains $\{e,b,b+e,\dots ,b+(m-1)e\}$ of one colour. Multiplication by $d$ gives the required set with starting point $bd$ and common difference $ed$. This proves the strengthened theorem withThis is the colour-count argument behind the Brauer progression theorem.

The Gallai theorem for an integer lattice states that every finite colouring of ${\mathbb{N}}^d$ contains a monochromatic homothetic copy of each finite lattice pattern. More precisely, for finite $S\subseteq {\mathbb{Z}}^d$ there exist $q\in \mathbb{N}$ and $b\in {\mathbb{Z}}^d$ with $b+qS\subseteq {\mathbb{N}}^d$ monochromatic. For $S\subseteq {\mathbb{N}}^d$, the translation vector can also be chosen positive.

The empty pattern is trivial. Otherwise first translate the pattern so its points $v_1,\dots ,v_k$ have nonnegative coordinates. Pull the given finite colouring back to words through the sum map from words to homothetic copiesBy the Hales-Jewett theorem, some combinatorial line with active set $J$ is monochromatic. Its images areThey are a homothetic copy with positive integer dilation $|J|$. Undoing the preliminary translation merely changes the translation vector; the actual copy still lies in the positive lattice. This derives Gallai's theorem from the Hales-Jewett theorem, and justifies the version used in Question 1.

For a rational $\ell \times n$ matrix $A$, write its columns as $c_1,\dots ,c_n$. It is partition regular if every finite colouring of $\mathbb{N}$ admits positive integers $x_1,\dots ,x_n$, all of one colour, with $A\mathbf{x}=0$. Repeated coordinates are allowed. The columns condition is an ordered partitioninto nonempty blocks such thatRado's theorem states that a rational matrix is partition regular if and only if it satisfies the columns condition. We prove both implications.

For necessity, clear denominators so the columns are integral. For every disjoint pair of index sets $I,B$ with $B\ne \varnothing$ andchoose a rational linear functional annihilating all columns in $I$ but not $v_B$. Such a functional exists by extending a basis of the indicated linear span to include $v_B$, prescribing zero on the former and one on the latter. Clearing its denominators produces an integer-coefficient functional $f_{I,B}$ with $f_{I,B}(v_B)$ a nonzero integer. There are only finitely many pairs $I,B$. Choose a prime number $p$ dividing none of these nonzero evaluations; if there are no bad pairs, choose any prime.

Use the last nonzero digit coloring for this prime. Namely, write $x=p^{{\nu }_p(x)}u$ with $p\nmid u$ and colour $x$ by $u\mathrm{mod}p\in \{1,\dots ,p-1\}$. By partition regularity, obtain a positive monochromatic solution. Let the distinct P-adic valuations of its coordinates beand put $B_j=\{i:{\nu }_p(x_i)=v_j\}$. All unit parts $u_i$ have a common nonzero residue $t$ modulo $p$.

For a block $B_j$, let $I=B_1\cup \cdots \cup B_{j-1}$. If its column sum were outside the earlier linear span, apply $f_{I,B_j}$ to the equation ${\sum }_i{c}_i{x}_i=0$. Earlier-block contributions are exactly zero. Divide the remaining equation by $p^{v_j}$ and reduce modulo $p$. Higher-valuation terms vanish, leavingThis contradicts the choice of $p$ and $t\not\equiv 0$. Consequently every block sum lies in the earlier linear span. For $j=1$ that span is $\{0\}$, so its sum is zero. This proves the columns condition by the finite separating-functional proof of the columns condition.

For sufficiency, suppose the blocks satisfy the columns condition. Choose rational coefficients ${\alpha }_{ij}$, for $i\in B_1\cup \cdots \cup B_{j-1}$, such thatTake a positive integer $c$ clearing all their denominators and an integer $p\ge 1$ at least as large as every $|c{\alpha }_{ij}|$. An M-p-c set with generators $z_1,\dots ,z_s$ consists of all valueswith every such value positive. The generators are therefore chosen with $c{z}_h>p{\sum }_{j>h}{z}_j$. Positivity is part of the configuration, not achieved by deleting inconvenient values.

Use the permitted monochromatic m-p-c set theorem to obtain one such monochromatic set. For each $i\in B_h$, putEvery $x_i$ is a positive element of that set, because its non-leading coefficients are integers of magnitude at most $p$. In the sum ${\sum }_i{c}_i{x}_i$, the coefficient of $z_1$ is $c{\sum }_{i\in B_1}{c}_i=0$, and the coefficient of each $z_j$ with $j>1$ isThus $A\mathbf{x}=0$. This is an explicit Rado solution inside an m-p-c set and proves sufficiency.

For the Finite sums theorem, defineTo deduce its monochromaticity from Rado's theorem, introduce variables $z_I$ for all nonempty $I\subseteq [k]$ and equationsLet $A_k$ be their coefficient matrix, and partition its columns by $B_j=\{I:\min I=j\}$. For a fixed $j$, the vector with $I$-coordinate $1$ when $j\in I$, and $0$ otherwise, solves this homogeneous system: in every row both sides count whether $j$ belongs to its indexing set. HenceThe first block sum is zero, and each later block sum lies in the linear span of earlier columns. This proves the columns partition for finite-sums systems. The positive monochromatic solution supplied by Rado's theorem has $x_i=z_{\{i\}}>0$, and its other coordinates are exactly all the nonempty finite sums. Therefore $FS(x_1,\dots ,x_k)$ is monochromatic. For $k=1$ a singleton is immediate. Equivalently, the full positive M-p-c set with $m=k,p=c=1$ directly contains every such sum, by taking its leading index to be the least index in $I$.

Identify ${\mathbb{N}}^{(\omega )}$ with the space of infinite subsets of the natural numbers. A family $E$ has an infinite homogeneous set for a colouring if some infinite $M$ satisfiesThis is the Ramsey family in the homogeneous-cone sense formulation. The relative Ramsey set of infinite subsets formulation asks for such an $M$ inside every prescribed infinite ground set. We prove the stronger completely Ramsey assertion, keeping an arbitrary finite stem fixed.

For a finite stem $s$ and an infinite tail $A$ with $\max s<\min A$ (taking $\max \varnothing =0$), writeThese neighbourhoods generate the Ellentuck topology, or star topology. A star-Borel set belongs to the sigma-algebra generated by the open sets of this topology. It is completely Ramsey if every $[s,A]$ has an infinite $B\subseteq A$ with $[s,B]\subseteq E$ or $[s,B]\cap E=\varnothing$. Taking $s=\varnothing$ gives both preceding Ramsey formulations.

We first prove the fusion proof for open Ellentuck sets. Fix a star-open set $U$ and a starting neighbourhood $[s,A]$. A reservoir $C$ above a finite extension $s\cup t$ accepts $t$ when $[s\cup t,C]\subseteq U$. It rejects $t$ when no infinite subreservoir accepts it. Every infinite reservoir has a refinement deciding $t$: if an accepting subreservoir exists choose one, and otherwise the reservoir already rejects. Both acceptance and rejection persist under further infinite thinning. These are acceptance and rejection of finite stems.

First refine $A$ to decide the empty extension. Choose $d_0$ from the refined reservoir and thin the remaining tail to decide every subset of $\{d_0\}$. After choosing $d_0,\dots ,d_j$, thin the unused infinite tail to decide every subset of this finite prefix before choosing $d_{j+1}$. Only finitely many decisions occur at each stage. Let $D=\{d_0<d_1<\cdots \}$. For each finite $t\subseteq D$, its tail(with $D_{\varnothing }=D$) is contained in the reservoir chosen when the largest point of $t$ was selected. Thus $D_t$ decides $t$. This is deciding all finite stems by fusion.

If $D$ accepts the empty extension, $[s,D]\subseteq U$ and we are done. Otherwise it rejects it. Call a finite $t\subseteq D$ accepted or rejected according to the decision of $D_t$. For each rejected $t$, the setis finite. Indeed, if $G_t$ were infinite, every $X\in [G_t{]}^{\omega }$ would have a least element $a$ with $t\cup \{a\}$ accepted, and its remaining tail lies in $D_{t\cup \{a\}}$. Hence $s\cup t\cup X\in U$ for every such $X$, making $G_t$ an accepting subreservoir for $t$, a contradiction. This proves the finitely many accepting extensions of a rejected stem fact.

Build $B=\{b_0<b_1<\cdots \}\subseteq D$ by choosing each new point outside all the finitely many sets $G_t$ for subsets $t$ of the already selected prefix. Begin with the rejected empty extension. Inductively every finite subset of the new prefix is rejected: the old subsets stay rejected, and each new subset is a rejected $t$ extended by a point outside $G_t$, whose decision must therefore be rejection. Consequently every finite $t\subseteq B$ is rejected.

If a point $X\in [s,B]$ belonged to $U$, star-openness would give a basic neighbourhood $[u,C]\subseteq U$ containing it. Extend $u$ along the increasing enumeration of $X$, if necessary, until its stem is $s\cup t$ for a finite $t\subseteq B$. The infinite tail of $X$ above that stem then provides an accepting subreservoir for $t$, contradicting rejection. Therefore $[s,B]\cap U=\varnothing$. We have proved that every star-open set is completely Ramsey.

A family $N$ is completely Ramsey-null when every $[s,A]$ has a stem-preserving refinement disjoint from $N$. Every star-nowhere dense set has this property. Apply the open-set result to the dense open complement of its star-closure. The disjoint alternative would put an entire basic neighbourhood inside a closure with empty interior, which is impossible. The other alternative gives the required avoidance.

We also need the full Ellentuck meagre-set fusion lemma, not a diagonal argument checking only one prefix. Let $N_0,N_1,\dots$ be completely Ramsey-null, and start inside $[s,A]$. At stage $j$, suppose $b_0,\dots ,b_{j-1}$ have been chosen. Refine the remaining infinite tail successively so thatThe null property permits each refinement with its stem unchanged; previous avoidance survives thinning. There are finitely many $t$ at this stage. Choose $b_j\in C_j$ and continue above it. Let $B=\{b_j:j\ge 0\}$.

For any infinite $Y\subseteq B$ and any fixed $j$, put $t=Y\cap \{b_0,\dots ,b_{j-1}\}$. Its remaining points form an infinite subset of $C_j$, so $s\cup Y\in [s\cup t,C_j]$ and hence $s\cup Y\notin N_j$. This works for every $j$, provingThus countable unions of completely Ramsey-null sets are null. Subsets of null sets are null as well. In particular every star-meagre set, being a countable union of star-nowhere-dense sets, is completely Ramsey-null.

Finally let $\mathcal{B}$ consist of families $E$ such that $E△U$ is contained in a star-meagre set for some star-open $U$. This is the Baire property in the Ellentuck topology. We verify that it forms a sigma-algebra. Open sets belong with empty error. For a countable union, use $U={\bigcup }_j{U}_j$; its error is contained in the countable union of the meagre errors. For complements, replace $U^c$ by its interior. The discrepancy isa closed nowhere-dense set: every open set meeting $\overline{U}$ also meets $U$, so none can lie wholly in this boundary. Adding it to the original meagre error handles complementation. Consequently every star-Borel set belongs to $\mathcal{B}$.

For such an $E$, start with any $[s,A]$. First apply null avoidance to its meagre error to find $[s,B]$ on which $E$ agrees with $U$. Then apply open-set homogeneity to refine it to $[s,C]$ wholly inside or outside $U$, and therefore wholly inside or outside $E$. This is the Baire-property reduction for completely Ramsey families. We concludeAll closures, interiors, openness and meagreness in this argument refer to the star topology; replacing it midway by the ordinary finite-prefix topology would not justify the null-avoidance step.