Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 14 (Ramsey Theory)

Let $c:\mathbb{N}\to \{1,\dots ,r\}$ be the given finite colouring, with $\mathbb{N}=\{1,2,\dots \}$. Give each unordered pair $\{a,b\}$ the colour $c(a+b)$. The infinite Ramsey theorem for r-sets, in its two-element case, gives an infinite homogeneous set for a colouring $X$. Enumerate it as $x_1<x_2<\cdots$. Every distinct-index sum $x_i+x_j$ has the common pair colour, soThis application of the infinite Ramsey theorem for r-sets uses only unordered pairs.

For the finite colouring $c$, colour each unordered pair $\{a,b\}$, written with $a<b$, by $c(a+2b)$. The infinite Ramsey theorem for r-sets again gives an infinite homogeneous set for a colouring. If its increasing enumeration is $x_1<x_2<\cdots$, thenThe ordering in this pair colouring is essential: it assigns the coefficient $2$ to the larger member.

Use the alternating dyadic colouring excludes symmetric weighted pair sums construction:Thus consecutive dyadic intervals $[2^k,2^{k+1})$ have opposite colours. Suppose an increasing infinite sequence $X=(x_j)$ had all its distinct-index weighted sums in one colour class. Set $\delta (y)=2^{\lfloor {\log }_{2}y\rfloor +1}-y$, the distance to the next strictly larger power of $2$.

If $\delta$ is unbounded on $X$, fix a term $x$ and choose a later term $y>2x$ with $\delta (y)>2x$. Put $L=2^{\lfloor {\log }_{2}y\rfloor }$, so $y=2L-\delta (y)$. ThenThese two weighted sums lie in adjacent dyadic intervals and therefore have opposite colours.

If $\delta$ is bounded by $D$ on $X$, choose a term $x>2D$ and a later term $y>2x$. With the same $L$, we haveFor the upper bounds, $y+2x<2y<4L$ and $2y+x<\frac{5}{2}y<5L<8L$. These weighted sums also lie in adjacent dyadic intervals. In both cases they are $x_i+2x_j$ and $x_j+2x_i$ for two distinct indices, contradicting the common colour class. Hence the symmetric distinct-index conclusion is false, even for this two-colour finite colouring.

Every ultrafilter contains exactly one cell of any finite set partition. Indeed, two disjoint cells cannot both belong to a proper filter, while if none belonged to the ultrafilter, all their complements would belong to it and their finite intersection would be empty.

Apply this property to the two colour classes in (iii). One belongs to any proposed ultrafilter, but neither contains a symmetric weighted-pair configuration from an increasing infinite sequence. This contradicts the proposed property of every member. Therefore no such ultrafilter exists.

Van der Waerden theorem says that for every pair of positive integers $r,k$ there is $W(r,k)$ such that every finite colouring of $[W(r,k)]=\{1,\dots ,W(r,k)\}$ using at most $r$ colours contains a monochromatic arithmetic progression of length $k$ and positive common difference. Consequently every finite colouring of $\mathbb{N}$ contains arbitrarily long monochromatic arithmetic progressions.

Here is a colour-focusing proof of Van der Waerden theorem. Induct on $k$, simultaneously for all $r$. For $k=1$, take $W(r,1)=1$. Suppose $W(R,k)$ exists for every number of colours $R$, and fix $r$. We will construct finite bounds $F_t$, $1\le t\le r$, with the following property: every finite colouring of $[F_t]$ using at most $r$ colours contains either a monochromatic length-$(k+1)$ arithmetic progression, or $t$ length-$k$ arithmetic progressions of pairwise distinct colours, all focused at the same point $f\in [F_t]$. Specifically, their terms are“Focused” means that adjoining $f$ completes the corresponding length-$(k+1)$ arithmetic progression if $f$ has its colour.

For $t=1$, put $F_1=2W(r,k)$. Find a monochromatic length-$k$ arithmetic progression in the first $W(r,k)$ points. Its next point is at most $2W(r,k)$ and supplies the focus. For $k=1$, give the selected singleton common difference $1$.

Suppose $F_t=N$ has been constructed. SetDivide $[2NM]$ into $2M$ consecutive blocks of length $N$. Colour the first $M$ block indices by their full colour profiles, that is, the ordered list of their $N$ colours. There are at most $r^N$ profiles, so the induction hypothesis on $k$ gives equally profiled blocks with indicesWhen $k=1$, choose $D=1$. Otherwise $D>0$ and $j_0+kD\le 2M$, since the last selected block is at most $M$ and $D\le M$.

Assume the original finite colouring contains no monochromatic length-$(k+1)$ arithmetic progression. Applying the property of $F_t$ to the common profile gives $t$ focused length-$k$ arithmetic progressions at a position $f$, with common differences $d_i$ and distinct colours $q_i$. The colour $q$ of position $f$ differs from every $q_i$: otherwise the profile already contains a length-$(k+1)$ monochromatic arithmetic progression, and so does any selected block.

Put $j_{\ast }=j_0+kD$ and $F=N(j_{\ast }-1)+f$, a point in the original interval. For $1\le h\le k$, the pointlies in a selected block at profile position $f-h{d}_i$, so has colour $q_i$. Similarly $F-hND$ has colour $q$. Thus $t+1$ length-$k$ arithmetic progressions of distinct colours focus at $F$. This proves the step in $t$. At $t=r$, the focus necessarily has the colour of one of the $r$ progressions, giving a monochromatic length-$(k+1)$ arithmetic progression. Hence $W(r,k+1)$ exists, completing the mathematical induction and the proof of Van der Waerden theorem.

For the partition regularity deduction we first prove a strengthened progression lemma, the Brauer progression theorem: for positive $r,s,L$ with $L\ge 2$, there is $B(r,s,L)$ such that every finite colouring of $[B(r,s,L)]$ using at most $r$ colours contains a monochromatic setInduct on $r$. For $r=1$, take $B(1,s,L)=\max (s,L)$ and $a=d=1$. Given the result for $r-1$, putVan der Waerden theorem supplies a colour-$q$ arithmetic progression $a+j{d}_0$, $0\le j<K$, inside $[W]$. If some $sj{d}_0$, $1\le j\le N$, also has colour $q$, take $d=j{d}_0$ and use the $L$ terms $a,a+j{d}_0,\dots ,a+(L-1)j{d}_0$. They are in the progression because $(L-1)j\le K-1$.

Otherwise the integers $sj{d}_0$, $1\le j\le N$, use at most $r-1$ colours. Colour $j\in [N]$ by the colour of $sj{d}_0$ and apply the induction hypothesis. It supplies a monochromatic set $\{se,b,b+e,\dots ,b+(L-1)e\}$. Multiplying by $s{d}_0$ gives the required configuration with $a=s{d}_{0}b$ and $d=s{d}_{0}e$: its distinguished member is $s^2{d}_{0}e=sd$. All of these points are at most $sN{d}_0\le sNW$, so the finite bound is valid. This proves the Brauer progression theorem using only the just-proved Van der Waerden theorem.

A row is a partition regular matrix over the positive integers if every finite colouring of $\mathbb{N}$ admits a positive vector $x$ whose coordinates have one colour and whose product with the row is zero. Coordinates may repeat. Since the coefficients are rational numbers, multiplying them by a common positive denominator leaves the equation and every zero subset sum unchanged, so write the row as nonzero integer coefficients $b_1,\dots ,b_n$.

To prove necessity, suppose no nonempty subset of the $b_i$ sums to zero. Choose a prime $p>{\sum }_i|b_i|$ and use the last nonzero digit coloringwhere $v_p$ is the P-adic valuation. If positive $x_i$ all had the same colour $u$ and satisfied ${\sum }_i{b}_i{x}_i=0$, let $m={\min }_i{v}_p(x_i)$ and $I=\{i:v_p(x_i)=m\}$. After division by $p^m$ and reduction modulo $p$, the equation becomesAs $u\ne 0$, this says $p\mid {\sum }_{i\in I}{b}_i$. The latter sum is nonzero and has absolute value at most ${\sum }_i|b_i|<p$, a contradiction. This explicitly proves the necessary obstruction without invoking a general partition regularity criterion.

Conversely, suppose $\varnothing \ne I\subseteq \{1,\dots ,n\}$ and ${\sum }_{i\in I}{b}_i=0$. Select an index $j\in I$, and putFor any finite colouring, the Brauer progression theorem gives one-coloured $\{sd,a,a+d,\dots ,a+(L-1)d\}$. The indices $u$ and $u+q$ both lie between $0$ and $L-1$. Define positive, same-coloured coordinates byThenThis also covers $I$ equal to the whole index set and $q=0$. Reversing the clearing of denominators proves the exact criterion:

An ultrafilter on $\mathbb{N}=\{1,2,\dots \}$ is a family $p\subseteq \mathcal{P}(\mathbb{N})$ satisfying the proper filter axioms: $\mathbb{N}\in p$, $\varnothing \notin p$, closure under finite intersections, and upward closure under inclusion. In addition, for every $A\subseteq \mathbb{N}$, exactly one of $A$ and $A^c$ belongs to $p$. Equivalently, an ultrafilter is a maximal proper filter. The principal ultrafilter at $n$ consists of all subsets containing $n$; an ultrafilter not of this form is a nonprincipal ultrafilter.

To prove existence, start with the cofinite filter and order the proper filters containing it by inclusion. The union of a chain is still a proper filter: finitely many of its members lie in one filter of the chain, and no constituent contains the empty set. Thus Zorn lemma supplies a maximal such filter $p$. If $A\notin p$, adjoining $A$ cannot generate a proper filter; otherwise maximality fails. Consequently some $B\in p$ has $B\cap A=\varnothing$, so $A^c\in p$ by upward closure. This proves the ultrafilter alternative. No finite $A$ can belong to $p$, because $A^c$ is cofinite and already belongs to $p$. In particular $p$ contains no singleton and is a nonprincipal ultrafilter. The same argument, starting from any proper filter, proves the ultrafilter lemma used below.

Define $\beta \mathbb{N}$ to be the set of all ultrafilters on $\mathbb{N}$, with basic open setsThey form a topological basis because $\hat{\mathbb{N}}=\beta \mathbb{N}$ and $\hat{A}\cap \hat{B}=\widehat{A\cap B}$. Moreover $(\hat{A}{)}^c=\widehat{A^c}$, so they are clopen sets. This is the compact Hausdorff topology on ultrafilters. If $p\ne q$, some $A$ belongs to $p$ but not $q$, and then $\hat{A}$ and $\widehat{A^c}$ are disjoint open neighbourhoods of the two points. Thus $\beta \mathbb{N}$ is Hausdorff.

For compactness, take an open cover and refine it by basic open sets $\widehat{A_{\lambda }}$. If no finite subfamily covers, then for every finite collection of indices the intersection $\bigcap A_{\lambda }^c$ is nonempty. Indeed, if that intersection were empty, the corresponding $A_{\lambda }$ would cover $\mathbb{N}$, and every ultrafilter would contain at least one of them by the finite ultrafilter alternative. The complements therefore have the finite intersection property and generate a proper filter. Extend it to an ultrafilter $q$ by the proved ultrafilter lemma. Then $A_{\lambda }^c\in q$ for every $\lambda$, so $q$ belongs to none of the covering $\widehat{A_{\lambda }}$, a contradiction. A finite basic subcover lies inside a finite subcover of the original cover. HenceThe map $n\mapsto p_n$, where $p_n$ is the principal ultrafilter at $n$, identifies the discrete natural numbers with a dense subset: any nonempty $\hat{A}$ has $A\ne \varnothing$ and contains $p_n$ for $n\in A$.

Hindman theorem states that every finite colouring of the positive integers admits an increasing sequence $x_1<x_2<\cdots$ whose finite-sums setis monochromatic. We now give the Idempotent-ultrafilter proof of Hindman's theorem. For $A\subseteq \mathbb{N}$, write $A-x=\{y\in \mathbb{N}:x+y\in A\}$. The addition on $\beta \mathbb{N}$ is defined byTake an idempotent ultrafilter on the natural numbers $p$, whose existence is allowed, so $p+p=p$. It is a nonprincipal ultrafilter: addition of principal points is $p_m+p_n=p_{m+n}$, whereas no positive integer satisfies $2m=m$.

Exactly one colour class $A$ belongs to $p$. DefineBy idempotence, $A^{\ast }\in p$. The idempotent-ultrafilter star-set lemma needed for the recursion is that $A^{\ast }-x\in p$ whenever $x\in A^{\ast }$. To prove it, put $D=A-x\in p$. Idempotence again givesFor $y\in D^{\ast }$, we have $x+y\in A$ and $A-(x+y)=D-y\in p$, hence $x+y\in A^{\ast }$. Thus $D^{\ast }\subseteq A^{\ast }-x$, proving the lemma by upward closure.

Choose $x_1\in A^{\ast }$. Suppose $F_n=FS(x_1,\dots ,x_n)\subseteq A^{\ast }$ has been constructed. Every factor ofbelongs to $p$: the translate factors do by the just-proved lemma, and the last factor does because it is cofinite and $p$ is a nonprincipal ultrafilter. The finite intersection is therefore nonempty. Choose $x_{n+1}$ in it. Then $x_{n+1}$ and every $s+x_{n+1}$ with $s\in F_n$ lie in $A^{\ast }$, so $F_{n+1}\subseteq A^{\ast }$. This constructs a strictly increasing sequence, indeed $x_{n+1}>{\sum }_{i\le n}{x}_i$, and proves Hindman theorem.

Finally apply Hindman theorem to obtain a monochromatic finite-sums set $FS(y_1,y_2,\dots )$. We construct a divisibility chain inside a finite-sums set using disjoint successive blocks of indices. Start with $x_1=y_1$. If $x_i=m$, take $2m$ unused terms after all indices used so far, and split them into two groups of $m$ consecutive terms. In each group its $m+1$ partial sums, including $0$, contain two in the same congruence class modulo $m$ by the pigeonhole principle. Their difference is a nonempty consecutive sum divisible by $m$, and positivity makes it at least $m$. Let $x_{i+1}$ be the sum of these two selected sums. Then $m\mid x_{i+1}$ and $x_{i+1}\ge 2m>m$.

The index set defining $x_{i+1}$ lies strictly after all previous index sets. Discard the other terms in these two groups before continuing. Because the chosen index sets are disjoint, every finite sum of distinct $x_i$ is a finite sum of distinct $y_j$, retaining the same colour. Therefore

Write $[M{]}^{\omega }$ for the set of all infinite subsets of $M$. A family $Y\subseteq [\mathbb{N}{]}^{\omega }$ is a Ramsey family in the homogeneous-cone sense if there is an infinite $M$ such that either $[M{]}^{\omega }\subseteq Y$ or $[M{]}^{\omega }\cap Y=\varnothing$. Thus membership in $Y$ is constant on an infinite homogeneous cone. We will prove the stronger version for open families: such a cone exists inside every prescribed infinite ground set, as in the definition of a Ramsey set of infinite subsets.

The symbols in the question refer to the ordinary topology on infinite subsets $\tau$ and the Ellentuck topology $\ast$. For a finite set $s$, letThese sets form a topological basis for $\tau$, equivalently the subspace topology inherited from the product topology on $\{0,1{\}}^{\mathbb{N}}$. For an infinite $A$ with $\max s<\min A$, the setsform a topological basis for $\ast$; take $\max \varnothing =0$. In particular $[s]=[s,\{n:n>\max s\}]$, so $\ast$ is finer than $\tau$.

For a non-Ramsey example use the finite-symmetric-difference parity colouring. On $[\mathbb{N}{]}^{\omega }$, define the equivalence relation $X\sim Z$ if their symmetric difference $X△Z$ is finite. By the axiom of choice, select a representative $R$ in every equivalence class. Give $X$ the colourwhere $R_X$ is its class representative. Deleting one point stays in the same class and toggles the parity. Thus for every infinite $M$, the sets $M$ and $M\setminus \{\min M\}$ are both in $[M{]}^{\omega }$ but have opposite colours. Either colour class, regarded as a family $Y$, is therefore not Ramsey.

Now let $U$ be $\tau$-open. We prove that for every infinite $A_0$ there is an infinite $C\subseteq A_0$ with $[C{]}^{\omega }\subseteq U$ or $[C{]}^{\omega }\cap U=\varnothing$. The proof uses acceptance and rejection of finite stems, which we define explicitly. For a finite stem $s$ and an infinite tail $A$ above $\max s$, say that $A$ accepts $s$ if $[s,A]\subseteq U$, and rejects $s$ if no infinite subset of $A$ accepts $s$. Both properties persist on taking infinite subsets. Every tail has an infinite subset that decides $s$: take an accepting subset if one exists, and otherwise it already rejects $s$.

First thin $A_0$ to decide the empty stem. Then construct $b_1<b_2<\cdots$ and nested infinite tails. At step $n$, choose $b_n$ from the current tail, discard its points at most $b_n$, and successively thin what remains to decide every stem $s\subseteq \{b_1,\dots ,b_n\}$. There are only finitely many such stems, so an infinite tail remains. Let $B=\{b_1,b_2,\dots \}$ and write $B/s=\{b\in B:b>\max s\}$. For every finite $s\subseteq B$, the tail $B/s$ decides $s$, since it lies in the tail obtained at the stage when the largest point of $s$ was selected. The empty stem is also decided. This is deciding all finite stems by fusion.

If $B$ accepts the empty stem, then $[B{]}^{\omega }\subseteq U$, as required. Otherwise $B$ rejects it. We need the finitely many accepting extensions of a rejected stem observation. Suppose a tail $B/s$ rejects $s$. Only finitely many $a\in B/s$ can have $B/a$ accepting $s\cup \{a\}$. Indeed, if infinitely many such $a$ formed a set $D$, every member of $[s,D]$ would have some first new point $a$ and all later points in $B/a$, hence would lie in $U$. This would make $D$ an accepting subset of $B/s$, contradicting rejection.

Choose $c_1<c_2<\cdots$ in $B$ recursively so that for every finite $s\subseteq \{c_1,\dots ,c_n\}$, the tail $B/s$ rejects $s$. The empty stem satisfies this initially. At the next step, each of the finitely many previous stems has only finitely many accepting one-point extensions by the observation. Choose $c_{n+1}$ larger than all previous points and outside all those finite exceptional sets. The first fusion ensured that the tail for every new stem decides it; since it does not accept it, it rejects it. This maintains the recursion.

Put $C=\{c_1,c_2,\dots \}$. If some $X\in [C{]}^{\omega }$ belonged to $U$, ordinary openness would give a finite initial segment $s$ of $X$ with $[s]\subseteq U$. In particular $[s,C/s]\subseteq U$. But $C/s$ is an infinite subset of $B/s$, which rejects $s$, a contradiction. Hence $[C{]}^{\omega }\cap U=\varnothing$. We have proved

Take the cone on an infinite coinfinite ground setIt is $\ast$-open because $E=[\varnothing ,2\mathbb{N}]$ is a basic open set of the Ellentuck topology. It is not $\tau$-open: if $X\in E$, every ordinary basic neighbourhood $[s]$ of $X$ contains an infinite extension of $s$ having an odd point larger than $\max s$. That extension is outside $E$. Therefore no point of $E$ has an ordinary open neighbourhood contained in $E$.

The same cone on an infinite coinfinite ground set works:It is $\tau$-closed: a set outside $E$ has an odd point, and the ordinary neighbourhood given by its initial segment through that point remains outside $E$. Its $\tau$-interior is empty, since every ordinary basic open set admits an extension having an odd point. Hence its ordinary closure equals itself and has empty interior, proving that it is a $\tau$-nowhere dense set.

In the Ellentuck topology, however, $E$ is itself a nonempty open set. Its $\ast$-closure therefore has nonempty $\ast$-interior, so $E$ is not $\ast$-nowhere dense.

LetThis is the dense countable family of cofinite infinite subsets. Every ordinary basic open set $[s]$ contains the cofinite set $s\cup \{n:n>\max s\}$. Thus $D$ is $\tau$-dense: its ordinary closure is the whole space, so it is not $\tau$-nowhere dense.

It is $\ast$-closed. Indeed, for an infinite noncofinite $X$, the Ellentuck topology neighbourhood $[\varnothing ,X]$ contains only noncofinite sets, because every subset of $X$ misses the infinite complement of $X$. This neighbourhood is disjoint from $D$.

Finally every nonempty basic $\ast$-open set $[s,A]$ contains a smaller basic $\ast$-open set disjoint from $D$: enumerate $A$ and let $B$ consist of every second point. Then $A\setminus B$ is infinite, and $[s,B]\subseteq [s,A]$ contains no cofinite set. In particular $D$ has empty $\ast$-interior. As it is already $\ast$-closed, its $\ast$-closure has empty $\ast$-interior, proving that it is $\ast$-nowhere dense.