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

Use $[m]=\{1,\dots ,m\}$. A combinatorial line in $[m{]}^n$ has one nonempty active set of coordinates, all carrying the same variable letter, with every other coordinate fixed. The Hales-Jewett theorem states that for every finite alphabet size $m$ and number of colours $k$, some $n$ makes every $k$-finite colouring of $[m{]}^n$ contain a monochromatic combinatorial line.

Here is a complete proof through the alphabet insensitivity lemma. A $d$-dimensional combinatorial subspace is obtained from $d$ pairwise disjoint nonempty coordinate blocks, one independently variable letter on each block, and fixed letters elsewhere. For two distinct letters $a,b$, a colouring restricted to such a combinatorial subspace is $(a,b)$-insensitive if switching $a$ and $b$ in any of its parameter coordinates leaves the colour unchanged, with all other letters and coordinates arbitrary.

We first prove that any desired dimension $d$ admits such an insensitive combinatorial subspace, using only the pigeonhole principle. Define finite bounds recursively bySplit the ambient coordinates into a prefix of length $L$ and a suffix of length $N$. For $0\le j\le L$, let the prefix $p_j$ consist of $j$ copies of $b$ followed by $L-j$ copies of $a$. Give it the entire colour profileThere are at most $k^{m^N}=L$ such profiles, but $L+1$ prefixes. Hence two prefixes $p_s,p_t$, $s<t$, have the same profile. Replace their differing coordinates $s+1,\dots ,t$ by one variable letter, obtaining a prefix word $v(x)$ with $v(a)=p_s$ and $v(b)=p_t$. Then $c(v(a)u)=c(v(b)u)$ for every suffix $u$.

Colour the suffixes by the vectorwhich has at most $k^m$ colours. By the dimension-$d-1$ induction hypothesis, there is a $(d-1)$-dimensional suffix combinatorial subspace on which this vector colouring is $(a,b)$-insensitive. Combining it with the variable block of $v$ gives dimension $d$. Switching the first parameter between $a,b$ preserves colour by the equal prefix profiles; switching any other parameter preserves every entry of $c^{\prime }$ by induction. This proves the alphabet insensitivity lemma, including $d=1$, where the suffix is empty.

Now induct on $m$ to prove the Hales-Jewett theorem. For $m=1$, any one-variable word gives a one-point monochromatic combinatorial line. Suppose the theorem holds for $m-1$, and let $d$ be a sufficient dimension for $k$ colours on $[m-1{]}^d$. The lemma supplies a $d$-dimensional combinatorial subspace insensitive to $(m-1,m)$. Restrict its parameter colouring to $[m-1{]}^d$. By the alphabet induction hypothesis it contains a monochromatic combinatorial line. Its $m$th point has the same colour as its $(m-1)$st point: switch the active parameter coordinates from $m-1$ to $m$, one at a time. Therefore the full line over $[m]$ is monochromatic. Its actual active coordinate set is the nonempty union of the active parameter blocks. This completes both inductions.

To deduce the Van der Waerden theorem, choose the dimension $n$ for alphabet size $m$ and pull back a colouring of a sufficiently long integer interval alongAll images lie in $[N]$ for $N=m{\sum }_{j=1}^n{m}^{j-1}$. A combinatorial line with active coordinates $D$ maps towhere $a$ is the contribution of the fixed coordinates. Thus every finite colouring of the positive integers contains monochromatic arithmetic progressions of every finite length. The argument also provides the finite-interval version. Length one is immediate.

The Strengthened Van der Waerden theorem requires the common difference itself to have the progression's colour. We prove a useful stronger, scaled version, the Brauer progression theorem: for every $k,t,\ell \ge 1$, a finite bound $B(k,t,\ell )$ guarantees a monochromatic setThe desired strengthening is $t=1$. For $\ell =1$ choose $a=t,d=1$; for one colour any interval covering the displayed configuration suffices. For the induction on $k$, assume $M=B(k-1,t,\ell )$ and $\ell \ge 2$. Put $L=(\ell -1)M+1$, let $W$ be a Van der Waerden theorem bound for $k$ colours and length $L$, and take $B(k,t,\ell )=tMW$. Inside $[W]$, obtain a one-colour progression $a+j\delta$ for $0\le j<L$, of colour $c$.

All numbers $tj\delta$, $1\le j\le M$, lie in the larger interval because $\delta \le W$. If one has colour $c$, then the subsequence $a,a+j\delta ,\dots ,a+(\ell -1)j\delta$, together with $tj\delta$, is the desired configuration with $d=j\delta$. Otherwise the colouring $j\mapsto c(t\delta j)$ of $[M]$ uses at most $k-1$ colours. Apply the induction hypothesis to obtain a one-colour configuration $\{te,b,b+e,\dots ,b+(\ell -1)e\}$ there. Multiplication by $t\delta$ gives common difference $d=t\delta e$ and distinguished point $td=t^2\delta e$, all of the same original colour. This proves the scaled theorem using only the Van der Waerden theorem.

The fixed-active-size strengthening is false. It already fails for $m=k=2$. For any proposed positive $n,d$, if $d>n$ there is no eligible line. Otherwise colour a word byThe two points of a line with exactly $d$ active coordinates have counts $q$ and $q+d$ of the letter $2$. Their quotient floors differ by exactly one, so their colours differ. This fixed-active-size obstruction for combinatorial lines is valid for every proposed $n,d$. The colouring may depend on $d$, since the assertion chooses $n,d$ before demanding the conclusion for every colouring.

Clear a common denominator first, so that all coefficients are nonzero integers. This changes neither the solutions nor partition regularity. We prove the one-equation criterion directly; no form of Rado's theorem is used as an assumption.

For necessity, choose a prime number $p>{\sum }_i|a_i|$. Colour a positive integer by its first nonzero base-$p$ digit: writing $x=p^{v_p(x)}u$ with $p\nmid u$, use the colour $u(\mathrm{mod}p)\in \{1,\dots ,p-1\}$. Suppose the equation has a monochromatic solution. Let $v$ be the smallest P-adic valuation of its entries and put $I=\{i:v_p(x_i)=v\}$, a nonempty set. Divide the equation by $p^v$ and reduce modulo $p$. All entries indexed by $I$ contribute the same nonzero digit $u$, and all other terms vanish. HenceIt follows that $p$ divides ${\sum }_{i\in I}{a}_i$. The absolute value of this sum is less than $p$, so $\boxed{\sum _{i\in I}{a}_i=0}$.

For sufficiency, take a nonempty zero-sum index set $I$ and put $S={\sum }_{i\notin I}{a}_i$. If $S=0$, the full coefficient sum is zero and the constant vector $(1,\dots ,1)$ is already a monochromatic solution in every colouring. Otherwise choose $j\in I$, put $t=|a_j|$, and set $b_j=-\mathrm{sgn}(a_j)S$, $b_i=0$ for $i\in I\setminus \{j\}$. ThenAdd the same sufficiently large nonnegative integer $H$ to all the $b_i$, obtaining $c_i=b_i+H\ge 0$. The sum is unchanged because ${\sum }_{i\in I}{a}_i=0$. Let $K={\max }_{i\in I}{c}_i$.

Apply the scaled Brauer progression theorem, proved above from the permitted Van der Waerden theorem, to obtain one-colour numbers $td$ and $a,a+d,\dots ,a+Kd$. DefineAll entries are positive and monochromatic, andTherefore the row is partition regular exactly when some nonempty coefficient subset sums to zero. Repetition of entries is allowed by the definition of partition regularity.

The two versions of partition regularity are equivalent. If the row is partition regular on all positive integers, pull a colouring of the even positive integers back by $n\mapsto 2n$. A monochromatic solution $\mathbf{y}$ for this pulled-back colouring gives the even solution $\mathbf{x}=2\mathbf{y}$ in the original colouring, since the equation is homogeneous.

Conversely, restrict any colouring of all positive integers to its even members. A monochromatic solution supplied by regularity on the even integers is already a valid solution in the full domain. This argument is an instance of scaling invariance of homogeneous partition regularity and does not require a new coefficient criterion.

Again use integer coefficients after clearing denominators and put $S={\sum }_i{a}_i$. If $S=0$, choose any odd positive integer $u$ and take all $x_i=u$. This gives a monochromatic solution in any colouring.

For necessity, suppose $S\ne 0$ and choose $K$ with $2^K>|S|$. Colour the odd positive integers by their residue classes modulo $2^K$. In any monochromatic candidate, $x_i\equiv u(\mathrm{mod}{2}^K)$ for a common odd $u$. The equation would imply $uS\equiv 0(\mathrm{mod}{2}^K)$. Since $u$ is coprime to $2^K$, this forces $2^K\mid S$, impossible for nonzero $S$ with $|S|<2^K$. Thus $\boxed{\text{regular over odd positive integers}⟺\sum _i{a}_i=0}$. This is one-equation partition regularity over odd integers; its obstruction concerns the full coefficient sum rather than just a zero-sum subset.

Take $\mathbb{N}=\{1,2,\dots \}$. We first prove the Ellis–Numakura lemma in the one-sided continuity convention needed here. Let $S$ be a nonempty compact Hausdorff space with an associative multiplication for which each map $x\mapsto xa$ is continuous. Among its nonempty closed subsemigroups, there is an inclusion-minimal one, $M$: a decreasing chain has nonempty intersection by compactness, and that intersection is a closed subsemigroup, so Zorn's lemma applies.

Fix $a\in M$. The set $Ma$ is nonempty and compact, hence closed in the Hausdorff space, and is a subsemigroup becauseMinimality gives $Ma=M$. Thus the set $T=\{x\in M:xa=a\}$ is nonempty. It is closed by the stated continuity, and it is a subsemigroup, since $(xy)a=x(ya)=xa=a$ for $x,y\in T$. Minimality again gives $T=M$, so $a\in T$ and $\boxed{a^2=a}$, giving a semigroup idempotent. If one instead uses the opposite one-sided continuity convention, the same proof uses $aM$ and $\{x:ax=a\}$; no joint continuity is required.

Apply this lemma to the Stone-Čech compactification of the natural numbers with its given addition. In the addition on the Stone-Čech compactification of the natural numbers convention,The continuous variable is $p$ when $q$ is fixed. The granted compactness, Hausdorff property and associativity therefore imply there exists an idempotent ultrafilter $p$ with $p+p=p$.

On the positive integers such a $p$ is nonprincipal: a principal ultrafilter at $n$ adds to itself to give the one at $2n$, which is different. Hence every cofinite set belongs to $p$. If zero is included in one's convention for $\mathbb{N}$, use the same compact semigroup argument on the closed space of nonprincipal ultrafilters: it is nonempty by compactness of the infinite discrete set's compactification, and the displayed addition sends two free ultrafilters to a free ultrafilter. This avoids the trivial principal idempotent at zero.

To deduce Hindman's theorem, let $A$ be the unique colour class belonging to $p$. DefineIdempotence gives $A^{\ast }\in p$. The idempotent-ultrafilter star-set lemma also gives $A^{\ast }-n\in p$ whenever $n\in A^{\ast }$. Here is its proof: $A-n\in p$, and applying idempotence to $A-n$ givesIntersecting this set with $A-n$ produces exactly $A^{\ast }-n$.

Choose $x_1\in A^{\ast }$. Suppose $x_1<\cdots <x_r$ have been chosen with every nonempty finite sum in $A^{\ast }$. The finite intersectionbelongs to $p$, and is therefore nonempty. Choose $x_{r+1}$ from it. The new sums are $x_{r+1}$ and $s+x_{r+1}$, and they all lie in $A^{\ast }$. Induction yieldsThis proves every finite colouring of the positive integers admits a monochromatic finite-sums set generated by a strictly increasing infinite sequence, the required Hindman theorem.

No. The ten residue classes modulo $10$ form a finite partition, so an ultrafilter $p$ contains exactly one class $C_r$. The addition formula shows that $p+p$ contains $C_{2r}$: for $n\in C_r$, the translate $C_{2r}-n$ is $C_r$ and belongs to $p$. If $p$ is an idempotent ultrafilter, uniqueness of its selected class gives $2r\equiv r(\mathrm{mod}10)$, hence $r=0$.

Thus every idempotent ultrafilter contains the multiples of $10$, and cannot also contain their complement. This is the zero-residue constraint for idempotent ultrafilters, valid for every finite modulus.

Yes. Use the sequence $x_j=2\cdot 10^{j-1}$, $j\ge 1$. Every nonempty finite sum has only digits $0$ and $2$ in decimal notation, with leading digit $2$, so none is a power of $10$, including $10^0=1$.

We still need an idempotent ultrafilter containing these sums; merely exhibiting an infinite set is insufficient. PutThe nonempty clopen sets $\overline{F_r}$ are nested, so compactness gives a nonempty compact $K$. This is the tail finite-sums semigroup. To verify closure under addition, take $p,q\in K$ and fix $r$. For any $s\in F_r$, choose a finite representation of $s$ and then an index $t$ beyond every index in that representation. Disjointness of supports gives $F_t\subseteq F_r-s$, so $F_r-s\in q$. Consequentlyand $F_r\in p+q$. This holds for every $r$, proving $p+q\in K$. The Ellis–Numakura lemma now supplies an idempotent ultrafilter in $K$. It contains $F_1$, a subset of the non-powers of $10$, so by upward closure it contains the whole set of non-powers of $10$.

Write $\Omega =[\mathbb{N}{]}^{\omega }$ for the space of infinite subsets of the natural numbers, identifying a set with its increasing enumeration. If $s$ is finite and $A$ is infinite with every element of $A$ above $\max s$, setFor the empty stem there is no lower-bound restriction. These sets form the basis of the Ellentuck topology, also called the star topology. The stem $s$ is fixed, while the infinite tail may be thinned.

A completely Ramsey set $E\subseteq \Omega$ is one for which every $[s,A]$ admits an infinite $B\subseteq A$ with $[s,B]\subseteq E$ or $[s,B]\cap E=\varnothing$. This keeps the same stem. A Ramsey set of infinite subsets requires that every infinite $A$ admit an infinite $B\subseteq A$ with a homogeneous empty-stem cone $[B{]}^{\omega }$. It does not require preserving a nonempty finite stem.

A set is a star-Baire set if it differs from a star-open set by a star-meagre set, equivalently $E△U$ is star-meagre for some star-open $U$. A nowhere dense set has closure with empty interior, and a meagre set is a countable union of such sets, with both notions interpreted in the specified topology.

For a non-Ramsey example, put $M=\{2,3,\dots \}$ and well-order all infinite subsets of $M$ as $(A_{\alpha }{)}_{\alpha <\mathfrak{c}}$, where $\mathfrak{c}=2^{{\aleph }_0}$. Recursively choose two fresh points $X_{\alpha },Y_{\alpha }\in [A_{\alpha }{]}^{\omega }$, not used at earlier stages. This is possible because each cone has cardinality $\mathfrak{c}$ and fewer than $\mathfrak{c}$ points have been used before any stage. Letkeeping all the $Y_{\alpha }$ outside $C$. Every infinite-subset cone on $M$ meets both $C$ and its complement. Thus $C$ is not Ramsey, even when regarded as a subset of $\Omega$: any infinite set can first be thinned to avoid $1$. This uses the axiom of choice, rather than claiming a Borel counterexample.

Now setEvery infinite $A$ has an infinite subset $B$ avoiding $1$, and then $[B{]}^{\omega }\cap E=\varnothing$. Hence $E$ is Ramsey. But no stem-preserving thinning of $[\{1\},M]$ is homogeneous for $E$, because $C$ splits every tail cone. Hence $E$ is not completely Ramsey.

To prove the topological equivalence, we first establish the Ellentuck meagre-set fusion lemma: every star-meagre set can be avoided in a refinement $[s,B]$ with the original stem. Call a set completely Ramsey-null if this avoidance holds in every $[s,A]$.

If $N$ is star-nowhere dense, then $U=\Omega \setminus \overline{N}$ is star-open and dense. By the granted complete-Ramsey property of star-open sets, every $[s,A]$ has a refinement $[s,B]$ either contained in $U$ or disjoint from $U$. The latter alternative would put a nonempty open set inside $\overline{N}$, contradicting density of $U$. Thus $N$ is completely Ramsey-null.

For a countable union ${\bigcup }_j{N}_j$ of completely Ramsey-null sets, use fusion, taking care of every possible finite stem. Starting with $A_0=A$, at stage $j$ choose $b_j\in A_{j-1}$ above all previous choices. From the part of $A_{j-1}$ above $b_j$, successively thin an infinite tail for each of the finitely many subsets $t\subseteq \{b_1,\dots ,b_j\}$ so thatEach thinning keeps the stem $s\cup t$ fixed; subsequent thinnings preserve earlier avoidance. Let $B=\{b_1,b_2,\dots \}$. For any $X\in [s,B]$ and fixed $j$, put $t=(X\setminus s)\cap \{b_1,\dots ,b_j\}$. The rest of $X$ lies in $A_j$, because all later selected points do. Therefore $X\in [s\cup t,A_j]$ and $X\notin N_j$. Since $j$ was arbitrary,This proves the fusion lemma. Considering all subsets $t$, not merely the single selected prefix, is essential: elements of $[s,B]$ need not use every $b_i$.

Suppose first that $E$ is star-Baire, with $E△U$ star-meagre and $U$ star-open. Thin $[s,A]$ to $[s,B]$ avoiding the meagre difference by the lemma. Then apply the granted complete-Ramsey property of $U$ to find $[s,D]$ homogeneous for $U$, with $D\subseteq B$. On this refinement $E$ and $U$ agree, so it is homogeneous for $E$. Thus $E$ is completely Ramsey.

Conversely, let $E$ be completely Ramsey and let $U$ be the union of all basic neighborhoods wholly contained in $E$, namely its star-interior. Every $[s,A]$ has a homogeneous refinement. If that refinement lies in $E$, it lies in $U$; if it avoids $E$, it also avoids $E\setminus U$. Consequently every basic neighborhood contains a nonempty open refinement disjoint from $E\setminus U$. Since such a refinement is also disjoint from the closure of $E\setminus U$, this difference is star-nowhere dense. Thus $E△U=E\setminus U$ is star-meagre, and $E$ is star-Baire. We have provedFinally, $\Omega$ is not star-meagre: otherwise apply the fusion lemma to its purported meagre cover inside any nonempty basic neighborhood, obtaining a nonempty $[s,B]$ disjoint from $\Omega$, a contradiction.

The printed paper does not define $\tau$. In the coarser Ramsey cone topology, whose basic open sets are $[A{]}^{\omega }$ without finite stems, $\Omega$ is $\tau$-meagre. To prove this, let $D_j=\{X:\min X=j\}$. Its cone-topology closure is $H_j=\{X:j\in X\}$: every cone neighborhood of a point containing $j$ has a subset with least element $j$, whereas if $j\notin X$ the neighborhood $[X{]}^{\omega }$ avoids $D_j$. No nonempty cone lies in $H_j$, since its infinite ground set can be thinned to remove $j$. Therefore each $D_j$ is nowhere dense, but $\Omega ={\bigcup }_{j\ge 1}{D}_j$. This proves meagreness of the Ramsey cone topology and exhibits the contrast with the star topology.

If $\tau$ instead denotes the ordinary topology on infinite subsets, with basic cylinders $[s]=\{X:s\text{ is an initial segment of }X\}$, the answer is not $\tau$-meagre. Indeed, given countably many nowhere dense sets, extend a finite increasing prefix successively so that its cylinder avoids the closure of the next set. Make the prefix longer at each step. Their union is an infinite increasing enumeration belonging to every chosen cylinder and avoiding the whole proposed cover. The same construction starts inside any nonempty cylinder, so this alternative product topology is also a Baire space. The two conventions have different answers, so the distinction must be made explicitly rather than inferred from the symbol alone.