Past exam of the mathematics course of the University of Cambridge / 2004 / iii / Paper 12 (Ramsey Theory)

We take $\mathbb{N}=\{1,2,\dots \}$ and require the common difference of an arithmetic progression to be positive. An ultrafilter $\mathcal{U}$ is a proper filter on a set deciding each subset: exactly one of $B$ and $\mathbb{N}\setminus B$ belongs to $\mathcal{U}$.

For the fixed length $m$, let ${\mathcal{B}}_m$ be the family of sets containing no m-term arithmetic progression. Any acceptable ultrafilter must contain every complement $\mathbb{N}\setminus B$ with $B\in {\mathcal{B}}_m$. These mandatory sets have the finite intersection property. Otherwise finitely many $B_1,\dots ,B_r\in {\mathcal{B}}_m$ would cover $\mathbb{N}$. Colour an integer by the first $i$ for which it belongs to $B_i$. The Van der Waerden theorem gives a monochromatic m-term arithmetic progression, contained in the corresponding $B_i$, a contradiction.

Generate a proper filter from those complements and extend it by the ultrafilter lemma. If some $B\in \mathcal{U}$ were in ${\mathcal{B}}_m$, its complement would also belong to $\mathcal{U}$, forcing the empty set into the filter. ThusNotice that sets avoiding one fixed length need not be closed under finite unions; the argument uses the finite intersection property, not an unsupported ideal claim.

For the unbounded-length version, let $\mathcal{B}$ consist of sets whose arithmetic progression lengths are bounded. Each $B_i\in \mathcal{B}$ fails to contain a progression of some length $m_i$, and hence of every greater length. If finitely many $B_i$ covered $\mathbb{N}$, colour by the first containing index and apply the Van der Waerden theorem at length $M={\max }_i{m}_i$. Again a contradiction results. The complements of all members of $\mathcal{B}$ therefore have the finite intersection property. Extending their generated filter gives an ultrafilter with arithmetic-progression-rich members:All finite sets lie in $\mathcal{B}$, so this ultrafilter contains every cofinite set and is a nonprincipal ultrafilter. The same is true of the fixed-length construction when $m\ge 2$, because no singleton is allowed; for $m=1$ a principal ultrafilter also works. These constructions illustrate ultrafilter selection from a partition-rich family.

The infinite-length answer is no. Colour $n$ by $\lfloor {\log }_{2}n\rfloor \mathrm{mod}2$, so successive intervals $[2^j,2^{j+1})$ alternate colours. An infinite arithmetic progression $a+td$, $t\ge 0$, meets every sufficiently large such interval: its first term at least $2^j$ is less than $2^j+d$, which is at most $2^{j+1}$ once $2^j\ge d$. It therefore has terms of both colours. Neither colour class contains an infinite arithmetic progression, but every ultrafilter contains one of the two colour classes. This dyadic block obstruction to infinite arithmetic progressions rules out the proposed ultrafilter.

For a finite alphabet $K$, a combinatorial line in $K^N$ has a nonempty active set $J\subseteq \{1,\dots ,N\}$, fixed letters outside $J$, and the same variable letter at every coordinate in $J$. The Hales-Jewett theorem states that for every alphabet size $k\ge 1$ and number of colours $r\ge 1$, some $N$ makes every r-colouring of $\{1,\dots ,k{\}}^N$ contain a monochromatic combinatorial line.

We first prove the alphabet insensitivity lemma with a concrete bound. Fix two distinct letters $a,b$, a desired dimension $d$, and a colouring $\chi :K^N\to \{1,\dots ,r\}$. A combinatorial subspace of dimension $d$ has disjoint nonempty active blocks $J_1,\dots ,J_d$ and fixed other coordinates. It is $(a,b)$-insensitive when exchanging $a,b$ in any one variable leaves the colour unchanged, whatever the other variable letters are.

Choose consecutive blocks of lengths $L_1,\dots ,L_d$ recursively byProcess these blocks from right to left. When block $i$ is reached, the later blocks already have one variable each; the earlier $P_i$ coordinates are still entirely unrestricted. For each of the $L_i+1$ words $a^t{b}^{L_i-t}$ in block $i$, form its complete colour profile over all $k^{P_i}$ earlier words and all $k^{d-i}$ assignments to the later variables. There are at most $r^{k^{P_i+d-i}}=L_i$ profiles. The pigeonhole principle gives $s<t$ with equal profiles. Fix the first $s$ coordinates of this block to $a$, the coordinates after $t$ to $b$, and make the interval from $s+1$ to $t$ variable. Substitution of $b$ gives the chain word indexed by $s$, and substitution of $a$ gives the one indexed by $t$; they have identical profiles. Thus this variable is insensitive to $a,b$ for every remaining context. Previously constructed later variables remain insensitive, because their colour equalities held for every possible earlier word. After all $d$ blocks, we have the required insensitive combinatorial subspace. This proves the explicit block bound for alphabet insensitivity.

Now induct on $k$, simultaneously for every $r$. The case $k=1$ is immediate with $N=1$. For $k\ge 2$, assume the Hales-Jewett theorem for the alphabet of size $k-1$, and take $d$ large enough for that theorem with $r$ colours. Apply the proved alphabet insensitivity lemma to the letters $k-1,k$, obtaining a d-dimensional combinatorial subspace $\varphi :K^d\to K^N$. On $\{1,\dots ,k-1{\}}^d$, the induced colouring $\chi \circ \varphi$ has a monochromatic combinatorial line. Its value at letter $k$ has the same colour as its value at $k-1$: change the active variables one at a time and use insensitivity. The union of their nonempty active blocks is the active set of a combinatorial line in the original word space. All its k points have one colour, completing the induction and the proof.

To deduce the Van der Waerden theorem, take $K=\{0,\dots ,m-1\}$ and pull a colouring of the positive integers back throughA combinatorial line with active set $J$ maps toHence every finite colouring has a monochromatic arithmetic progression of every prescribed finite length. In finite form, if $H(k,r)$ is a word-length bound for the Hales-Jewett theorem, then $W(r,m)\le 1+(m-1)H(m,r)$ is a valid interval bound.

The Strengthened Van der Waerden theorem also puts the common difference in the colour class:Here is a finite proof by induction on the number $r$ of colours. For $m=1$ choose $a=d=1$. For $r=1$ choose $a=d=1$ in $[m]$. For $m\ge 2,r\ge 2$, let $M$ be a bound for the strengthened theorem with $r-1$ colours, put $L=(m-1)M+1$, and let $W=W(r,L)$ be an ordinary Van der Waerden theorem bound. Work in $[MW]$. Its first $W$ points contain a monochromatic progressionof colour $c$. Every $jd$, $1\le j\le M$, lies in $[MW]$. If some $jd$ has colour $c$, then $a,a+jd,\dots ,a+(m-1)jd$, together with its difference $jd$, gives the answer. Otherwise the colouring of $\{d,2d,\dots ,Md\}$ uses only $r-1$ colours. Pull it back to $[M]$ and apply the induction hypothesis to get a monochromatic set $\{e,b,b+e,\dots ,b+(m-1)e\}$. Multiplication by $d$ gives the required configuration in the original colouring. This proves the strengthened theorem, including finite bounds.

The Gallai theorem for an integer lattice states that every finite colouring of ${\mathbb{Z}}^h$ contains a monochromatic homothetic copy $u+tF$ of every prescribed finite nonempty pattern $F\subseteq {\mathbb{Z}}^h$, where $t$ is a positive integer. The positive-lattice version holds for finite $F\subseteq {\mathbb{N}}^h$ as well. Write $F=\{v_1,\dots ,v_k\}$ and colour $w\in \{1,\dots ,k{\}}^N$ by the colour ofA monochromatic combinatorial line maps to $u+|J|F$, with $u=b+{\sum }_{j\notin J}{v}_{w_j}$. Thus the Hales-Jewett theorem supplies the copy, with nonzero dilation $|J|$. Choosing $b$ large and positive places all these word sums in the positive lattice if required. This sum map from words to homothetic copies also proves the real-vector-space version: replace ${\mathbb{Z}}^h$ by ${\mathbb{R}}^h$ and allow an arbitrary finite real pattern, while retaining positive integer dilations.

For a rational matrix $A$ with columns $a_1,\dots ,a_n$, partition regularity means that every finite colouring of the positive integers admits a positive monochromatic vector $x$ with $Ax=0$. Repeated coordinates are allowed. The columns condition is an ordered partition $\{1,\dots ,n\}=B_1\bigsqcup \cdots \bigsqcup B_s$ into nonempty blocks such thatRado's theorem says that $A$ is partition regular if and only if it satisfies the columns condition. We prove both directions.

For necessity, clear denominators so the columns are integer vectors. For every pair of disjoint index sets $I,B$ with $B\ne \varnothing$ for which ${\sum }_{i\in B}{a}_i$ is not in the rational linear span of the I-columns, choose an integer linear functional ${\ell }_{I,B}$ that vanishes on those I-columns but not on that sum. Such a functional exists by finite-dimensional linear algebra; clear its rational denominators. There are only finitely many pairs, so choose a prime number $p$ dividing none of the nonzero integersIf there are no offending pairs, any prime number suffices.

Colour a positive integer $x=p^{v_p(x)}u$, $p\nmid u$, by $u\mathrm{mod}p$. This is the last nonzero digit coloring, using $p-1$ colours. Partition regularity gives a positive monochromatic solution. Group its coordinate indices by their distinct P-adic valuations $e_1<\cdots <e_s$, writing $B_j=\{i:v_p(x_i)=e_j\}$. All units $x_i/p^{e_j}$ have the same nonzero residue $\alpha$ modulo $p$.

For each $j$, let $I=B_1\cup \cdots \cup B_{j-1}$. If its block sum failed the required span condition, apply the chosen ${\ell }_{I,B_j}$ to ${\sum }_i{a}_i{x}_i=0$. The earlier terms vanish exactly, not just modulo a power of $p$. Divide by $p^{e_j}$; terms with later valuations are still divisible by $p$. Reduction modulo $p$ then yieldscontrary to the choice of $p$. Thus every required span relation holds, and with $I=\varnothing$ the first block sum is zero. This is the finite separating-functional proof of the columns condition; it avoids an unjustified passage from congruences to rational equality.

For sufficiency, assume the columns condition. Choose rational coefficients ${\lambda }_{ij}$, for $j\ge 2$ and $i\in B_1\cup \cdots \cup B_{j-1}$, such thatChoose a positive integer $c$ clearing every denominator, and a positive integer $p\ge \max |c{\lambda }_{ij}|$, taking $p=1$ if the list is empty. By the allowed monochromatic m-p-c set theorem, there are positive generators $z_1,\dots ,z_s$ such that all numbersare positive and have one colour. This is a full m-p-c set; positivity is part of its definition, not a rule discarding negative expressions. For $i\in B_h$, putThese coordinates all belong to that monochromatic m-p-c set. Collecting coefficients of $z_j$ givesThus the Rado solution inside an m-p-c set proves partition regularity and completes the theorem.

To obtain the Finite sums theorem from Rado's theorem, introduce a positive variable $y_F$ for every nonempty $F\subseteq \{1,\dots ,k\}$ and imposePartition the columns of this system into $B_j=\{F:\min F=j\}$. The $B_1$-column sum is zero: in a row indexed by $F$ containing $1$, the contributions of $y_F$ and $y_{\{1\}}$ cancel, and other rows receive neither. For $j>1$, the $B_j$-column sum iswhere $a_F$ is the column of $y_F$. Those columns lie in earlier blocks. Hence the columns condition holds. A monochromatic positive solution gives $x_i=y_{\{i\}}$ and $y_F={\sum }_{i\in F}{x}_i$, provingFor $k=1$ the system has no rows and the conclusion is immediate. The construction is also visible directly in the sufficiency proof: a monochromatic $(k,1,1)$-set contains every nonempty sum of its generators, classified by the smallest chosen index.

Write $[\mathbb{N}{]}^{\omega }$ for the space of infinite subsets of the natural numbers, with each subset identified with its increasing enumeration. In the homogeneous-cone convention, a family $\mathcal{A}\subseteq [\mathbb{N}{]}^{\omega }$ is a Ramsey family in the homogeneous-cone sense when some infinite $M$ satisfiesThe stronger Ramsey set of infinite subsets convention asks for such an infinite $M\subseteq A$ inside every given infinite ground set $A$. We will prove the open-set assertion in this stronger form, and our Ramsey-but-not-completely-Ramsey example will satisfy it as well. Thus the distinction in conventions does not affect any of the conclusions below.

For a non-Ramsey example, declare $X\sim Y$ if their symmetric difference is finite, and choose a representative $R$ from each equivalence class using the axiom of choice. Setfor the representative of the class of $X$. Removing one point reverses this colour, because its symmetric difference with $R$ changes by exactly one point. Consequently every cone $[M{]}^{\omega }$ contains the oppositely coloured sets $M$ and $M\setminus \{\min M\}$. Either colour class of this finite-symmetric-difference parity colouring is not a Ramsey family in the homogeneous-cone sense. No definability is claimed for the representative selection.

The ordinary topology on infinite subsets, denoted $\tau$, has basic cylinders $[s]=\{X:s⊏X\}$, where $s$ is a finite stem of the increasing enumeration. Let $O$ be a $\tau$-open family and fix an arbitrary infinite ground set $A$. We give a complete fusion proof of a homogeneous cone inside $A$.

Use the convention $\max \varnothing =0$. For finite $s$ and an infinite reservoir $B$ above $\max s$, say that $B$ accepts $s$ if $[s,B]\subseteq O$, whereSay that $B$ rejects $s$ if no infinite subset of $B$ accepts $s$. There is always a refinement deciding $s$: choose an accepting subreservoir if one exists, and otherwise retain $B$, which rejects. Both decisions persist under further thinning.

A first fusion produces an infinite $H\subseteq A$ deciding every finite $s\subseteq H$ on its tail $H/s=\{h\in H:h>\max s\}$. First decide the empty stem. Choose the first point, and thin the remaining reservoir successively to decide every subset of the selected prefix. Repeat after choosing each new point. There are finitely many subsets to decide at each stage. The diagonal sequence of chosen points has the required property, since its tail after the largest point of any stem lies in the reservoir where that stem was decided. The empty-stem decision persists too. This is deciding all finite stems by fusion.

If $H$ accepts the empty stem, $[H{]}^{\omega }\subseteq O$ and we are done. Suppose it rejects. For a rejected finite $s\subseteq H$, only finitely many $h\in H/s$ can have $H/h$ accepting $s\cup \{h\}$. Otherwise let $D$ be their infinite set. Every infinite $X\subseteq D$ starts with some such $h$, and its remaining tail lies in $H/h$, so $s\cup X\in O$. Then $D$ accepts $s$, contradicting rejection. This proves finitely many accepting extensions of a rejected stem.

A second fusion constructs $K\subseteq H$ whose every finite subset is rejected. If a finite prefix of chosen points has been selected, all its subsets are rejected by induction. Avoid the union of their finitely many accepting successor sets when choosing the next point. The first fusion already decides every successor, so every new subset is rejected. An infinite reservoir remains after each finite exclusion.

If some $X\in [K{]}^{\omega }$ belonged to $O$, openness would give an initial segment $s⊏X$ with $[s]\subseteq O$. Its reservoir $H/s$ would then accept $s$, contradicting the second fusion. Therefore $[K{]}^{\omega }\cap O=\varnothing$. In either case we have a homogeneous cone inside the arbitrary ground set $A$. Every $\tau$-open family is a Ramsey set of infinite subsets, under both conventions.

A completely Ramsey set requires more: for every finite $s$ and infinite reservoir $A$ above $\max s$, there is an infinite $B\subseteq A$ such thatThe finite stem must be kept fixed. These $[s,A]$ are the basic neighbourhoods of the Ellentuck topology, also called the star topology.

Let $E$ be the even positive integers, and construct the finite-symmetric-difference parity colouring $\epsilon$ on $[E{]}^{\omega }$. DefineFor any infinite ground set $A$, the set $A\setminus \{1\}$ is still infinite and its whole cone misses $\mathcal{R}$. Thus $\mathcal{R}$ is a Ramsey set of infinite subsets even in the stronger convention. But inside $[\{1\},E]$, every infinite refinement $B\subseteq E$ gives the two sets $\{1\}\cup B$ and $\{1\}\cup (B\setminus \{\min B\})$ of opposite colours. Hence no such refinement is homogeneous. The family $\mathcal{R}$ is Ramsey but not completely Ramsey. The stem-supported Ramsey family need not be completely Ramsey construction explains this example: forgetting the stem $\{1\}$ is precisely what loses the obstruction.

Finally take $D=[E{]}^{\omega }$. It is nonempty and star-open, since it equals $[\varnothing ,E]$. It is $\tau$-closed: if an infinite set contains an odd integer, an initial segment witnessing that integer has a cylinder disjoint from $D$. Its $\tau$-interior is empty: after any finite stem of even integers, append an arbitrarily large odd integer and then infinitely many further points. ThusThis is the cone on an infinite coinfinite ground set. Choose its subset $Y=\{X\in [E{]}^{\omega }:\epsilon (X)=0\}$. Since ${\overline{Y}}^{\tau }\subseteq D$, $Y$ is also $\tau$-nowhere dense. Nevertheless every $[\varnothing ,B]$ with infinite $B\subseteq E$ contains both $B$ and $B\setminus \{\min B\}$, of opposite colours. Hence $Y$ is not completely Ramsey. We have proved explicitly that ordinarily nowhere-dense sets need not be completely Ramsey; the topology in the nowhere-dense hypothesis cannot be silently changed to the star topology.