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

The Canonical Ramsey theorem says that for every map $c:[\mathbb{N}{]}^{(r)}\to C$, with no restriction on the colour set $C$, there are an infinite set $X=\{x_1<x_2<\cdots \}$ and $I\subseteq \{1,\dots ,r\}$ such that, for increasing tuples from $X$,

To prove it, define an equivalence relation on $[\mathbb{N}{]}^{(r)}$ by equality of colours. Two ordered pairs of $r$-sets have one of finitely many intersection-order types. Successively apply the infinite Ramsey theorem to obtain an infinite $X$ on which, for each type, equivalence has a constant truth value. Let $I$ consist of those coordinates whose replacement, with all other coordinates fixed and order preserved, changes the equivalence class. Homogeneity of the pair types shows first that this does not depend on the chosen tuple. Changing coordinates one at a time then shows that agreement on $I$ implies equivalence; reversing the same chain shows that disagreement at a coordinate in $I$ implies inequivalence. This gives the displayed canonical form.

For $r=2$, the four choices of $I$ give exactly the constant, minimum, maximum, and injective colourings. Suppose the asserted finite result failed for some $s$. For every $n$ choose an equivalence relation on $[n{]}^{(2)}$ having no canonical $s$-set. These finite bad relations form a finitely branching tree under restriction. König infinity lemma gives an infinite branch, hence a colouring-equivalence relation on $[\mathbb{N}{]}^{(2)}$ with no canonical $s$-set. The canonical theorem supplies an infinite canonical set, whose first $s$ vertices give a contradiction. Therefore a suitable finite $n$ exists.

Solved by gpt-5.6-sol high.

Restrict the given finite edge-colouring to the positive integers inside $\mathbb{Q}$. The infinite Ramsey theorem gives an infinite monochromatic subset; listing it in increasing order producesApply the same theorem separately to the negative integers. If the selected indices satisfy $n_1<n_2<\cdots$, thenforms a monochromatic set with $y_1>y_2>\cdots$. The two monochromatic colours need not agree.

Solved by gpt-5.6-sol high.

For a single homogeneous equationwith nonzero integer coefficients, Rado theorem says that it is a partition regular equation exactly whenfor some nonempty $I\subseteq \{1,\dots ,r\}$.

For necessity, suppose no nonempty coefficient sum vanishes. Choose a prime $p$ dividing none of the finitely many nonzero numbers ${\sum }_{i\in I}{c}_i$. Colour $x\in \mathbb{N}$ by the first nonzero base-$p$ digitIf $x_1,\dots ,x_r$ had one colour, divide the equation by the least power of $p$ occurring among them and reduce modulo $p$. The terms of minimum valuation givefor a nonzero $u$, contradicting the choice of $p$.

For sufficiency, reorder so that $c_1+\cdots +c_t=0$. The standard focusing lemma derived from the Van der Waerden theorem says the following: given a finite colouring, a finite monochromatic solution of the first $j$ blocks of the columns condition can be chosen together with a common difference $d$ so that every bounded translate of every chosen entry by a multiple of $d$ retains its colour. To prove the lemma, refine the colour of $a$ to the finite vector $(\chi (a),\chi (2a),\dots ,\chi (Ra))$, apply van der Waerden to a sufficiently long progression in this refined colouring, and take a common multiple of the finitely many resulting coefficients as $d$.

Start with the zero-sum block $\{1,ldots,t\}$, for which equal variables already solve its contribution. Add each remaining coefficient as a singleton block. In one dimension its block sum is a rational multiple of any fixed nonzero earlier coefficient, so the focusing lemma chooses a bounded translate that cancels this new contribution while preserving the common colour. Induction over the remaining indices gives a monochromatic solution of the full equation. This proves the single-equation form of Rado's theorem.

Now let $a_1,ldots,a_n,b$ be positive and put $A=a_1+\cdots +a_n$. If $b=At$, then $x_1=\cdots =x_n=t$ is a monochromatic solution in every colouring. Conversely, every solution has $x_i\le b/a_i$. Give each integer at most $b/{\min }_i{a}_i$ its own colour and colour all larger integers with one extra colour. A monochromatic solution must have all $x_i=t$, so $b=At$. Thus the inhomogeneous equation is partition regular exactly when $A$ divides $b$.

Solved by gpt-5.6-sol high.

The cofinite subsets of $\mathbb{N}$ form a proper filter. By Zorn lemma, it extends to an ultrafilter $\mathcal{U}$. Since $\mathcal{U}$ contains every cofinite set, it cannot contain a finite set, so it is nonprincipal.

Define the Stone-Čech compactification of the natural numbers $\beta \mathbb{N}$ to be the set of ultrafilters on $\mathbb{N}$, with basic setsSince $\beta \mathbb{N}\setminus \bar{A}=\overline{\mathbb{N}\setminus A}$, these sets are clopen. If $\mathcal{U}\ne \mathcal{V}$, choose $A\in \mathcal{U}\setminus \mathcal{V}$; then $\bar{A}$ and $\overline{\mathbb{N}\setminus A}$ are disjoint neighbourhoods, proving Hausdorffness. For compactness, a family of basic closed sets with the finite-intersection property corresponds to a family of subsets of $\mathbb{N}$ with the finite-intersection property. Extend that family to an ultrafilter; the resulting point belongs to every closed set. The Alexander subbase theorem now proves compactness.

The Hindman theorem states that every finite colouring of $\mathbb{N}$ admits an infinite sequence $x_1,x_2,\dots$ for which every nonempty finite sum of distinct terms has one colour. Let $\mathcal{U}\in \beta \mathbb{N}$ be an additive idempotent, and choose a colour class $A\in \mathcal{U}$. PutIdempotence gives $A^{\ast }\in \mathcal{U}$, and $A^{\ast }-x\in \mathcal{U}$ whenever $x\in A^{\ast }$. Having selected $x_1,ldots,x_n$ with all finite sums in $A^{\ast }$, chooseThis finite intersection belongs to $\mathcal{U}$ and is nonempty. Induction keeps every finite sum in $A^{\ast }\subseteq A$, proving Hindman's theorem.

Solved by gpt-5.6-sol high.

Write ${\forall }_{\mathcal{U}}x\phi (x)$ to mean $\{x:\phi (x)\}\in \mathcal{U}$. For each $x$, exactly one of the red-neighbour set $R_x$ and the blue-neighbour set $B_x$ belongs to $\mathcal{U}$. Applying the ultrafilter dichotomy once more toshows that exactly one ofholds. They cannot both hold because the two outer sets are complementary; the diagonal causes no problem because a nonprincipal ultrafilter contains no singleton.

Assume the red statement and put $X=\{x:R_x\in \mathcal{U}\}\in \mathcal{U}$. Choose $x_1\in X$. Recursively chooseoutside the finitely many previously chosen points. Every set in this finite intersection belongs to $\mathcal{U}$, so a choice is always possible. Then $M=\{x_1,x_2,\dots \}$ is infinite and all of its edges are red.

Solved by gpt-5.6-sol high.

Let $X$ be the vertex set of a regular polygon and let the cyclic rotation group $A$ act transitively on it. The finite invariant-colouring lemma says that for every number of colours there are positive weights $w_1,ldots,w_N$ with ${\sum }_i{w}_i^2=1$ such that every colouring of the weighted Cartesian powercontains a monochromatic setFor completeness, prove the lemma along a cyclic composition series for $A$. For a prime cyclic quotient, refine each colour to the finite vector of colours obtained by applying the quotient elements in every active coordinate. The Hales-Jewett theorem supplies a variable block on which this vector is constant. Assign that block squared weights summing to the squared weight of the coordinate it replaces. This makes the quotient orbit monochromatic without changing any orbit distance. Iterating through the cyclic factors proves the lemma for the finite cyclic group $A$.

Because rotations commute, for $a,b\in A$ each coordinate satisfiesfor a fixed vertex $v$. Hence the squared distance between the two corresponding product points isThe monochromatic orbit is therefore isometric to $X$. This proves that every regular polygon is a Euclidean Ramsey set.

Now consider the edge-colouring definition. If all pairwise distances in $X$ are equal, then $X$ is a regular simplex. Take a sufficiently large regular simplex $S$ of the same side length. The ordinary finite Ramsey theorem gives a monochromatic $|X|$-vertex complete subgraph, and every such vertex set is isometric to $X$. Thus $X$ is an edge Ramsey set.

Conversely, if $X$ has two distances, let $a$ and $b$ be its least and greatest distances. Colour every Euclidean edge by whether its length equals $a$. Every isometric copy of $X$ contains both an edge of length $a$ and one of length $b$, so no copy is monochromatic. Hence the edge Ramsey sets are exactly the equidistant finite sets.

Allowing similar copies does not change the answer. If $r=b/a>1$, colour an edge of length $d$ by the parity ofIn every similar copy, the images of a shortest and a longest edge have lengths $ta$ and $tb=rta$, whose displayed integers differ by one. They receive opposite colours. Thus no non-equidistant $X$ is edge Ramsey even up to similarity, while the regular-simplex argument already supplies an isometric copy.

Solved by gpt-5.6-sol high.