Past exam of the mathematics course of the University of Cambridge / 2018 / iii / Paper 130 (Ramsey Theory)

Hales–Jewett and the arithmetic-progression consequence. For a finite alphabet $[m]$ and a positive integer $r$, the Hales-Jewett theorem gives an integer $N$ such that every $r$-color finite coloring of $[m{]}^N$ contains a monochromatic combinatorial line. A combinatorial line has a nonempty active coordinate set: all those coordinates receive the same freely varying letter, and the remaining coordinates are fixed.

We first prove the alphabet insensitivity lemma. Fix two letters $a,b\in [m]$, with $m\ge 2$, and a desired dimension $d$. There is a combinatorial subspace of dimension $d$ on which changing $a$ to $b$ in any variable coordinate, with all other variable coordinates arbitrary, preserves the color.

For the construction, divide the coordinates into $d$ consecutive blocks. Choose their lengths from left to right byProcess the blocks from right to left. When processing block $i$, the later blocks already form a $(d-i)$-dimensional combinatorial subspace. Color each word in block $i$ by the vector of its original colors for every prefix word of length $P_i$ and every assignment to those later variables. There are $m^{P_i+d-i}$ contexts, and at most $r^{m^{P_i+d-i}}=L_i$ such color vectors.

The $L_i+1$ words $a^j{b}^{L_i-j}$, $0\le j\le L_i$, contain two, indexed by $u<v$, with the same vector by the pigeonhole principle. Fix the first $u$ coordinates to $a$, the coordinates after $v$ to $b$, and make coordinates $u+1,\dots ,v$ the active set of one new variable. Its values $a,b$ now have identical colors for every prefix and later-variable context. The active set is nonempty. Insensitivity already obtained in later blocks survives, because it held for every unrestricted earlier prefix. After all $d$ blocks have been processed, changing $a,b$ in any of the $d$ variables preserves the color. This proves the lemma.

Now induct on $m$. For $m=1$, a one-coordinate combinatorial line is automatically monochromatic. For $m\ge 2$, let $d$ be a length supplied by the theorem for alphabet $[m-1]$ and $r$ colors. Apply the alphabet insensitivity lemma for the letters $m-1,m$ to obtain a $d$-dimensional combinatorial subspace. Restrict its variables to $[m-1]$. Induction gives a monochromatic combinatorial line in those variables. Its values $1,\dots ,m-1$ have the same color, and its value $m$ has the same color as its value $m-1$ by successively switching the active variables. Lifting this line to the original coordinates proves

For the Van der Waerden theorem, fix a progression length $k\ge 2$ and use the alphabet $\{0,\dots ,k-1\}$. Pull back an $r$-color finite coloring of $\{1,\dots ,1+(k-1)N\}$ alongA combinatorial line with active set $S$ maps to the arithmetic progression $a,a+q,\dots ,a+(k-1)q$, where $a\ge 1$ and its common difference is $q=|S|>0$. The Hales-Jewett theorem makes this progression monochromatic. Length one is trivial, so every finite coloring of the positive integers contains monochromatic arithmetic progressions of every finite length.

The active-coordinate obstruction. Color a word red when its first coordinate is $1$, and blue otherwise. Any combinatorial line whose active coordinate set contains $1$ has a red word at variable value $1$ and a blue word at variable value $2$, since $m>1$. ThusHere adequacy is the adequate family of active coordinate sets property; an active coordinate set is always nonempty.

Let $\mathcal{F}$ be an intersecting family. For a word $w\in [m{]}^n$, put $S(w)=\{i:w_i=1\}$. Give $w$ the red color if $S(w)$ contains some member of $\mathcal{F}$, and the blue color otherwise.

Consider any combinatorial line with active set $A\in \mathcal{F}$. At variable value $1$, $A\subseteq S(w)$, so that word is red. At variable value $2$, $S(w)\cap A=\varnothing$. No member of $\mathcal{F}$ can be contained in this $S(w)$, because every member meets $A$. Thus that word is blue. No such line is monochromatic, provingIf $\mathcal{F}$ is empty there is no permitted active set at all, so it is also not an adequate family of active coordinate sets.

Let $N$ be a word length supplied by the Hales-Jewett theorem for alphabet $[m]$ and two colors. For $n\ge 2N$, embed $[m{]}^N$ into $[m{]}^n$ by the coordinate duplication for combinatorial lines mapPull back any two-color finite coloring to this word space. The Hales-Jewett theorem gives a monochromatic combinatorial line with nonempty active set $S$. Its image is a combinatorial line whose active set isand hence has size $2|S|$, a positive even integer. ThereforeThe empty set's presence in the family causes no difficulty: the line just constructed has at least two active coordinates.

Rado's criterion. Let $A$ be a matrix over the rational numbers, with columns $a_1,\dots ,a_q$. A partition regular matrix is one for which every finite coloring of the positive integers gives a monochromatic positive vector $x\in {\mathbb{N}}^q$ with $Ax=0$; repeated coordinates are allowed. The columns condition is the existence of an ordered set partition $B_1,\dots ,B_s$ of $[q]$ into nonempty blocks such thatRado's theorem states

Necessity. Clear denominators so the columns are integer vectors. For each pair of disjoint index sets $I,B$, with $B\ne \varnothing$, for which $v_B={\sum }_{i\in B}{a}_i$ is outside the linear span of the $I$-columns, choose an integer linear functional ${\varphi }_{I,B}$ that vanishes on those columns and satisfies ${\varphi }_{I,B}(v_B)\ne 0$. Such a functional exists by extending a basis of the span to one also containing $v_B$, defining a functional on that basis, and clearing its rational denominators.

There are only finitely many such pairs. Choose a prime number $p$ dividing none of these nonzero integer evaluations. If there are no such pairs, any prime will do. Use the last nonzero digit coloring: write $x=p^{v_p(x)}u$, with $p\nmid u$, and color $x$ by $u\mathrm{mod}p\in \{1,\dots ,p-1\}$. Since $A$ is a partition regular matrix, this coloring supplies a monochromatic positive solution, so all its unit parts have a common nonzero residue $d$.

Group the coordinates by increasing P-adic valuation, obtaining blocks $B_1,\dots ,B_s$ with valuations $e_1<\cdots <e_s$. Suppose for some $j$ the sum $v_{B_j}$ lay outside the linear span of the earlier columns, with earlier index set $I$. Apply ${\varphi }_{I,B_j}$ to $Ax=0$. Earlier terms vanish exactly. Divide the remaining integer equation by $p^{e_j}$ and reduce modulo $p$. Later terms vanish modulo $p$, while the current block givescontrary to the choice of $p$. Thus every block sum lies in the earlier linear span, and for the first block this means it is zero. This proves the columns condition by the finite separating-functional proof of the columns condition.

Sufficiency. Suppose the columns condition holds. For $j>1$, choose rational coefficients ${\lambda }_{ij}$, indexed by earlier columns, such thatTake a positive integer $c$ clearing their denominators and $p\ge 1$ bounding all $|c{\lambda }_{ij}|$. We use the allowed monochromatic m-p-c set theorem with $s$ levels. Its M-p-c set is the full setwhere the generators make every displayed expression positive. Positivity is part of this convention, rather than a rule that discards nonpositive expressions. For $i\in B_h$, setAll these numbers lie in the monochromatic set $D$. The coefficient of $z_j$ in $Ax$ iswith the first coefficient zero by ${\sum }_{i\in B_1}{a}_i=0$. Hence $Ax=0$. This Rado solution inside an m-p-c set proves sufficiency.

The equality-or-inequality dichotomy. If every finite coloring gives a monochromatic solution with $x_1=x_2$, the first alternative holds. Otherwise fix a finite coloring $\chi$ admitting no such solution. Given any other finite coloring $\psi$, use the refinement of a finite coloring $n\mapsto (\chi (n),\psi (n))$. Since $A$ is a partition regular matrix, it supplies a solution monochromatic for both colorings. Its first two coordinates cannot be equal, by the defining property of $\chi$, so it is the required unequal solution for $\psi$. Thus one of the two universal alternatives always holds. This is the partition regularity dichotomy under an extra constraint; the alternatives are not asserted to be mutually exclusive.

Both restrictions can fail. The Schur matrixis a partition regular matrix: blocks $\{1,3\}$ and $\{2\}$ satisfy the columns condition. Color $n$ by $v_2(n)\mathrm{mod}2$, using the 2-adic valuation. An equal-coordinate solution would have $x_3=2x_1$, and $v_2(2x_1)=v_2(x_1)+1$, so its coordinates cannot be monochromatic. This exhibits failure of the equality restriction.

Conversely, $A=(1-1)$ satisfies the columns condition in one block. Every solution has $x_1=x_2$, so even the constant one-color finite coloring admits no unequal-coordinate solution. Consequently

The ultrafilter space. An ultrafilter $U$ on $\mathbb{N}$ is a proper filter on a set: it is upward closed, closed under finite intersections, excludes $\varnothing$, and contains exactly one of $A,A^c$ for each $A\subseteq \mathbb{N}$. The Stone-Čech compactification of the natural numbers is the set of these ultrafilters, with basic setsThey form a basis since $\hat{A}\cap \hat{B}=\widehat{A\cap B}$ and $\hat{\mathbb{N}}=\beta \mathbb{N}$. Moreover $(\hat{A}{)}^c=\widehat{A^c}$, so each is a clopen set. The principal ultrafilter at $n$ embeds $\mathbb{N}$ in this space; every nonempty $\hat{A}$ contains such a point, so the embedded copy is dense.

Distinct ultrafilters $U,V$ have some $A\in U$ with $A\notin V$. Then $A^c\in V$, and $\hat{A},\widehat{A^c}$ are disjoint open sets separating them. Thus the space is Hausdorff.

For compactness, any open set cover can be refined to a cover by basic sets. If $\{\widehat{A_i}\}$ has no finite subcover, the sets $A_i^c$ have the finite intersection property: otherwise finitely many $A_i$ cover $\mathbb{N}$, and their basic sets cover every ultrafilter. Extend the proper filter on a set generated by these complements to an ultrafilter $U$. This extension follows from Zorn lemma: unions of chains of proper filters remain proper, and a maximal proper filter decides every $A$ versus $A^c$. Indeed, if adding $A$ made the filter improper, some existing filter member would be disjoint from $A$, forcing $A^c$ into the filter. This $U$ contains every $A_i^c$ and misses every $\widehat{A_i}$, a contradiction. HenceThis proves the compact Hausdorff topology on ultrafilters directly.

An idempotent. The addition on the Stone-Čech compactification of the natural numbers can be defined byAssociativity is supplied. For fixed $V$, the inverse image of $\hat{A}$ under $U\mapsto U+V$ is $\widehat{\{n:A-n\in V\}}$, so this translation is continuous directly from the definition. This makes a left-topological semigroup in the convention used here.

We prove the Ellis–Numakura lemma in this case. Among nonempty compact subsemigroups choose one, $K$, minimal by inclusion. It exists by Zorn lemma: a descending chain has nonempty intersection by compactness, and that intersection is again a compact subsemigroup. For $a\in K$, the set $K+a$ is a nonempty compact subsemigroup contained in $K$. Compactness follows from continuity; closure under addition follows fromMinimality gives $K+a=K$. Hence there is $b\in K$ with $b+a=a$. The setis nonempty, compact, and a subsemigroup: if $x,y\in L$, then $(x+y)+a=x+(y+a)=x+a=a$. Thus minimality gives $L=K$, and in particular $a+a=a$. ThereforeThis is an idempotent ultrafilter on the natural numbers.

Isolating the sequence terms. Now use the hypothetical convergent sequence of distinct ultrafilters. For each $n$, choose $C_n\in U_n$ with $C_n^c\in U$, possible since $U_n\ne U$. Convergence implies $C_n^c\in U_m$ for all sufficiently large $m$. Thus only finitely many indices $m\ne n$ have $C_n\in U_m$. Call this finite set $E_n$.

For each $m\in E_n$, choose $D_{n,m}\in U_n$ with $D_{n,m}\notin U_m$, using distinctness. SetFinite-intersection closure puts $A_n$ in $U_n$. For $m\ne n$, either $C_n\notin U_m$ or one of the chosen $D_{n,m}$ is absent from $U_m$; upward closure then prevents $A_n$ from belonging to $U_m$. Hence

Use the isolating sets from the preceding part and make the finite disjointificationFor $j<n$, $A_j\notin U_n$, so $A_j^c\in U_n$. Thereforeby finite-intersection closure of the ultrafilter. If $m\ne n$, $B_n\subseteq A_n$ and $A_n\notin U_m$ imply $B_n\notin U_m$. Also $B_n$ avoids every earlier $A_j$, hence every earlier $B_j$. ThusOnly finite intersections were used; no countable-intersection closure of an ultrafilter is being assumed.

Let $E={\bigcup }_{j\ge 1}{B}_{2j}$. For every even index $2j$, $B_{2j}\subseteq E$ and $B_{2j}\in U_{2j}$ imply $E\in U_{2j}$. For every odd index $2j-1$, disjointness gives $B_{2j-1}\subseteq E^c$, so $E^c\in U_{2j-1}$ and $E\notin U_{2j-1}$. ConsequentlyThe limit ultrafilter $U$ contains either $E$ or $E^c$. Whichever it contains, the corresponding basic clopen set $\hat{E}$ or $\widehat{E^c}$ is a neighbourhood of $U$, but infinitely many sequence terms lie outside it. This contradicts convergence. Therefore pairwise distinct ultrafilters cannot form a convergent sequence in $\beta \mathbb{N}$, the key step in no nontrivial convergent sequences in the Stone-Čech compactification.

Let $(V_n)$ be a convergent sequence in the Stone-Čech compactification of the natural numbers, with limit $V$. Each fixed $W\ne V$ occurs only finitely often: the Hausdorff property gives a neighbourhood of $V$ excluding $W$, and eventually the sequence is in that neighbourhood.

If $(V_n)$ were not eventually equal to $V$, infinitely many terms would differ from $V$. They could not take only finitely many distinct values, because each such value occurs only finitely often. Recursively select a subsequence of pairwise distinct terms, all different from $V$. It still converges to $V$, contradicting the preceding parts. HenceThis establishes no nontrivial convergent sequences in the Stone-Čech compactification for arbitrary sequences, including ones with repetitions.

The two Ramsey properties and the topologies. Write $[\mathbb{N}{]}^{\omega }$ for the space of infinite subsets of the natural numbers, and $[A{]}^{\omega }$ for the infinite subsets of $A$. The positive integers are used throughout. A Ramsey set of infinite subsets $E$ has the property that every infinite $A$ contains an infinite $B$ for which $[B{]}^{\omega }$ lies wholly in $E$ or wholly in $E^c$.

For finite $s$ and infinite $A$ above $\max s$, letThese are the basic neighbourhoods of the Ellentuck topology, denoted $\ast$ in the question. They form a basis: if $X$ belongs to two such sets, their stems are comparable initial segments of $X$; take the longer stem and the intersection of the two tails beyond that stem. This intersection contains the infinite remaining tail of $X$ and yields a basic set contained in both.

A completely Ramsey set $E$ allows such a homogeneous refinement $[s,B]$ inside every $[s,A]$, with $B\subseteq A$ infinite and the stem $s$ kept fixed. Taking $s=\varnothing$ shows that complete Ramseyness implies Ramseyness. The ordinary topology on infinite subsets $\tau$ has basic cylindersIt is the usual product topology on increasing enumerations and is coarser than the Ellentuck topology.

Examples distinguishing the properties. A non-Ramsey example uses the axiom of choice. Let $\kappa =2^{{\aleph }_0}$ and enumerate all infinite sets as $(A_{\alpha }{)}_{\alpha <\kappa }$. Each $[A_{\alpha }{]}^{\omega }$ has cardinality $\kappa$: an enumeration of $A_{\alpha }$ gives the upper bound, and choosing one element from each of infinitely many disjoint pairs gives an injection from all binary sequences for the lower bound.

By transfinite recursion, choose two distinct, previously unused elements $X_{\alpha },Y_{\alpha }\in [A_{\alpha }{]}^{\omega }$ at each stage. Fewer than $\kappa$ elements have been used at stage $\alpha <\kappa$, so this is possible without any assumption on the Continuum hypothesis. Put $R=\{X_{\alpha }:\alpha <\kappa \}$. All the $Y_{\alpha }$ remain outside $R$, since subsequent choices also avoid previously chosen elements. Every $[A{]}^{\omega }$ contains one $X_{\alpha }$ and one $Y_{\alpha }$, so $R$ is not a Ramsey set of infinite subsets. This is the non-Ramsey set from transfinite selection construction.

Perform the same construction on $T=\mathbb{N}\setminus \{1\}$, giving a non-Ramsey set $R_T\subseteq [T{]}^{\omega }$, and putFor any infinite $A$, the infinite set $B=A\setminus \{1\}$ has $[B{]}^{\omega }\cap E=\varnothing$, so $E$ is a Ramsey set of infinite subsets. But no $[\{1\},B]$ with infinite $B\subseteq T$ is homogeneous, because $[B{]}^{\omega }$ meets both $R_T$ and its complement. Therefore $E$ is not a completely Ramsey set.

Every star-open set is completely Ramsey. We give the full fusion proof for open Ellentuck sets, without quoting an infinite Ramsey theorem. Fix a star-open set $O$ and a basic set $[s,A]$. For finite $a\subseteq A$ and an infinite tail $D\subseteq A$ above $\max a$, say $D$ accepts $a$ if $[s\cup a,D]\subseteq O$; it rejects $a$ if no infinite subset of $D$ accepts $a$. Both properties persist under passing to infinite subsets. Every infinite tail can be thinned to decide $a$: take an accepting subset if one exists, and otherwise the original tail rejects it.

First thin $A$ to decide $a=\varnothing$. If it accepts, the required homogeneous neighborhood has already been found. Otherwise keep a rejecting tail. We now fuse to an infinite set $B$ deciding every finite $a\subseteq B$, where the decision for $a$ is made by $B/a=\{b\in B:b>\max a\}$.

To do this, choose $b_1<b_2<\cdots$ successively from an infinite current tail. After choosing $b_j$, thin the tail above $b_j$ to decide each of the finitely many subsets of $\{b_1,\dots ,b_j\}$, one after another, before choosing the next element. For any finite $a\subseteq B$, at the stage when its largest element is selected, the current tail decides $a$ and contains every later selected element. Heredity therefore gives a decision on $B/a$. For $a=\varnothing$, rejection persists from the initial tail.

If $B/a$ rejects $a$, only finitely many $n\in B/a$ can have $B/n$ accepting $a\cup \{n\}$. Otherwise let $D$ be the infinite set of those $n$. Every member of $[s\cup a,D]$ has a first new element $n$, and its remaining tail lies in $B/n$. It therefore belongs to $O$ by acceptance of $a\cup \{n\}$. This would make $D$ accept $a$, contradicting rejection.

Thin $B$ a second time to $C=\{c_1<c_2<\cdots \}$ so that every finite $a\subseteq C$ is rejected. Start with the rejected empty set. At a finite stage, all subsets of the selected elements are rejected. For each of these finitely many subsets, avoid its finitely many next elements that would give an accepted extension, and choose the next $c_j$ beyond all excluded elements. Since $B$ decides every finite extension, each new extension is rejected. Induction gives the asserted property of $C$.

We claim $[s,C]\cap O=\varnothing$. If $X\in [s,C]\cap O$, openness provides a basic set $[t,D]\subseteq O$ containing $X$. Extend $t$, if necessary, to an initial segment $u$ of $X$ containing $s$. Write $u=s\cup a$ with finite $a\subseteq C$. The infinite tail $X\setminus u$ lies in $B/a$ andIt is therefore an accepting subtail for $a$, contradicting rejection. We have found either an accepting neighborhood or a neighborhood disjoint from $O$. Thus

Basic neighborhoods are clopen. Consider $[s,A]$ and a point $X$ outside it. If $s$ is not an initial segment of $X$, take an initial segment $t$ of $X$ of length at least $|s|$; its ordinary cylinder $[t]$ cannot meet $[s,A]$. Otherwise some element of $X\setminus s$ is outside $A$; take $t$ through that element, and again $[t]$ is disjoint from $[s,A]$.

Thus the complement of $[s,A]$ is already open in the ordinary topology on infinite subsets, and hence in the finer Ellentuck topology. A basic neighbourhood is open by definition, so

The answer is no. Let $X_0=\mathbb{N}$, regarded as one point of the space of infinite subsets of the natural numbers, and putThe displayed union makes $O$ an open set in the Ellentuck topology. On the other hand, every basic neighbourhood $[s,A]$ of $X_0$ contains a different infinite set: keep $s$ and remove one element from its infinite remaining tail. This other point belongs to $O$. Therefore $X_0$ is in the closure of $O$ but not in $O$, soThe fact that basic neighbourhoods are clopen sets does not make arbitrary unions of them closed.

Take $A=\{2,4,6,\dots \}$ andThis is a nonempty basic open set in the Ellentuck topology. It is a closed set in the ordinary topology on infinite subsets: an infinite set outside $O$ contains an odd integer, and its finite initial segment through that integer gives an ordinary cylinder disjoint from $O$.

Its ordinary interior is empty. In any nonempty ordinary cylinder $[s]$, choose an odd integer $b>\max s$ and continue $s\cup \{b\}$ by any infinite increasing tail. The resulting point belongs to $[s]$ and lies outside $O$. Indeed the smaller cylinder $[s\cup \{b\}]$ is disjoint from $O$. Since $O$ is ordinary-closed with empty ordinary interior, it is a nowhere dense set for $\tau$. Hence