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

Ramsey's theorem for $r$-sets says that every finite coloring of $[\mathbb{N}{]}^{(r)}$ has an infinite monochromatic set. We prove it by mathematical induction on $r$. The case $r=1$ is the infinite pigeonhole principle. Suppose the result holds for $r-1$, and let $c:[\mathbb{N}{]}^{(r)}\to [k]$. Choose $a_1$, then use the induction hypothesis on the coloring $F\mapsto c(F\cup \{a_1\})$ to obtain an infinite set $M_1$ on which this color is constant, say $d_1$. Inductively chooseso that $c(F\cup \{a_j\})=d_j$ for every $F\in [M_j{]}^{(r-1)}$. Some color $d$ occurs for infinitely many $d_j$. If $j_1<j_2<\cdots$ are the corresponding indices, every $r$-set from $\{a_{j_1},a_{j_2},\dots \}$ has color $d$: take its least-indexed element $a_{j_s}$, after which its other $r-1$ elements lie in $M_{j_s}$. This proves the theorem.

Solved by gpt-5.6-sol high.

Suppose the Finite Ramsey theorem failed for fixed positive integers $r,k,m$. For every $n$ choose a $k$-coloring $c_n:[n{]}^{(r)}\to [k]$ with no monochromatic $m$-set. There are only finitely many colorings of $[r{]}^{(r)}$, so an infinite subsequence of the $c_n$ agrees there. Pass to a further infinite subsequence agreeing on $[r+1{]}^{(r)}$, and continue. The diagonal argument produces compatible colorings $d_N:[N{]}^{(r)}\to [k]$ such that $d_{N+1}{|}_{[N{]}^{(r)}}=d_N$ and no $d_N$ has a monochromatic $m$-set.

Define $d(F)=d_N(F)$ whenever $N\ge \max F$. Compatibility makes this a well-defined finite coloring of $[\mathbb{N}{]}^{(r)}$. By Ramsey's theorem it has an infinite monochromatic set, whose first $m$ elements contradict the defining property of a sufficiently large $d_N$. This compactness argument proves the finite statement.

Solved by gpt-5.6-sol high.

Let $c:\mathbb{N}\to [k]$ be the given finite coloring. Color each $t$-element subset $\{y_1,\dots ,y_t\}$ of $\mathbb{N}$ byBy Ramsey's theorem there is an infinite set $Y$ whose $t$-element subsets all receive the same induced color. Enumerate it increasingly as $x_1<x_2<\cdots$. Then every sum $x_{i_1}^2+\cdots +x_{i_t}^2$ with $i_1<\cdots <i_t$ has that color. The argument works for every positive integer $t$; primality is not needed for this part.

Solved by gpt-5.6-sol high.

No. It is enough to take the prime number $t=2$. By the monochromatic sums-and-products obstruction, there is a finite coloring $\chi$ of $\mathbb{N}$ for which no infinite set has all its pairwise sums and pairwise products in one color. Refine $\chi$ by also recording the parity of the 2-adic valuation.

If a sequence $(x_i)$ made both requested families monochromatic, put $y_i=x_i^2$. If the set of distinct $y_i$ were infinite, an injective subsequence would make all pairwise sums $y_i+y_j$ and products $y_i{y}_j$ monochromatic under $\chi$, a contradiction. Otherwise some $y=x_i^2$ occurs infinitely often. Two occurrences give the sum $2y$ and the product $y^2$, butbecause $v_2(y)$ is even. The refining colors differ, another contradiction.

Solved by gpt-5.6-sol high.

The Hales-Jewett theorem states that for positive integers $m,k$ there is $N$ such that every $k$-coloring of the words $[m{]}^N$ contains a monochromatic combinatorial line.

Here is the standard focused-line proof. Induct on the alphabet size $m$, the case $m=1$ being immediate. Assume the result for $m-1$ and every number of colors. For $1\le s\le k$, prove inductively that some dimension has the following alternative: either there is a monochromatic combinatorial line, or there are $s$ color-focused lines, meaning that the lines without their common focus are monochromatic in $s$ distinct colors. For $s=1$, restrict to words on $[m-1]$ and use the induction hypothesis on $m$.

For the step from $s-1$ to $s$, let $n$ work for $s-1$ and view a longer word as $(a,b)\in [m{]}^n\times [m{]}^M$. Color each $b\in [m-1{]}^M$ by the complete patternwhich uses at most $k^{m^n}$ colors. Taking $M=HJ(m-1,k^{m^n})$ gives a line on which this entire pattern is constant. Append its missing $m$-letter endpoint. Applying the $s-1$ alternative to the induced coloring of the first block and joining the active coordinate sets produces either a monochromatic line or $s$ lines with one common focus and distinct colors. At $s=k$, the focus has one of the $k$ colors, so it completes the line carrying that color. This proves the theorem.

To deduce the Van der Waerden theorem, let $N=HJ(m,k)$ and color a word $(x_1,\dots ,x_N)\in [m{]}^N$ by the color of $x_1+\cdots +x_N$. On a combinatorial line with active set $I$, these sums area monochromatic arithmetic progression of length $m$.

Solved by gpt-5.6-sol high.

The Strengthened Van der Waerden theorem says that every finite coloring contains, for each prescribed $m$, a monochromatic setWe prove the finite form by induction on the number $k$ of colors. The case $k=1$ is immediate. Let $n$ work for $m$ and $k-1$ colors, and apply the ordinary Van der Waerden theorem to obtain a monochromatic progressionIf one of $d,2d,\dots ,nd$ has the progression's color, say $rd$, thenworks. Otherwise $d,2d,\dots ,nd$ use at most $k-1$ colors. By the induction hypothesis their indices contain $b,b+r,\dots ,b+(m-1)r$ together with $r$ in one color. Multiplying by $d$ yieldswhich is the required progression together with its common difference.

Solved by gpt-5.6-sol high.

Restrict the coloring to the diagonal by setting $d(n)=c(n,n)$. We give the direct focusing proof of a monochromatic three-term arithmetic progression. For each $1\le s\le k$, induction constructs a finite interval in which either there is a monochromatic three-term progression or there are $s$ color-focused two-term progressions. The case $s=1$ is the pigeonhole principle. For the induction step, take sufficiently many equal blocks that two have identical color patterns. Translate the $s-1$ focused pairs in the first block to the second and join corresponding points. These give $s-1$ focused pairs at a translated focus; the pair formed by the old and translated focuses supplies the last one. If its color repeated one of the previous colors, the associated pair and the focus would already form a monochromatic three-term progression. Thus the alternative holds.

At $s=k$, the common focus has one of the $k$ colors and completes the pair of that color, so there are $a,r>0$ with $d(a)=d(a+r)=d(a+2r)$. Thereforeis the required monochromatic two-dimensional progression. This proves the result without invoking the Van der Waerden theorem as a black box.

Solved by gpt-5.6-sol high.

The finite-witness version of part c can be iterated by the standard product argument: color one finite witness by the entire color pattern it induces on a second witness, find a diagonal triple with one pattern, and then find a diagonal triple inside that common pattern. This is the special four-point case of the Gallai theorem for an integer lattice. Apply that theorem toA monochromatic homothetic copy $(a,b)+rS$ is exactlyas required.

Solved by gpt-5.6-sol high.

Let $c_1,\dots ,c_n$ be the columns of the rational partition regular matrix $A$, and clear denominators so that they are integer vectors. We use the P-adic columns lemma. For a large prime number $p$, color each positive integer by a sufficiently long initial block of the unit part of its P-adic valuation, together with its valuation modulo the block length. Partition regularity supplies a monochromatic $x=(x_1,\dots ,x_n)$ withGroup the indices according to the successive $p$-adic orders of the $x_i$. At the lowest order, division by the common power of $p$ and reduction modulo the chosen large power showsComparing the next nonzero blocks of base-$p$ digits shows successively thatFor completeness, these congruences may be made exact by taking the digit block longer than every determinant and coordinate formed from the fixed columns: a nonzero such integer cannot be divisible by the resulting power of $p$. There are only finitely many ordered partitions of $[n]$, so passing through arbitrarily long blocks leaves one partition satisfying all the displayed identities. This is precisely the columns property.

Solved by gpt-5.6-sol high.

Rado's theorem states that a rational matrix is partition regular if and only if it has the columns property. By hypothesis each $A_i$ is partition regular, so choose a columns partition for each one. Form the block-diagonal matrixTaking at stage $j$ the union of the $j$th blocks from the individual partitions, with empty blocks added after a partition ends, gives the columns property for $B$: each row block sees exactly the corresponding dependence for its $A_i$. Hence $B$ is partition regular by Rado's theorem. A monochromatic vectorin the kernel of $B$ satisfies $A_i{x}_i=0$ for every $i$, and all entries of all the $x_i$ have the same color.

Solved by gpt-5.6-sol high.

Given a finite coloring $c:\mathbb{N}\to [k]$, color each three-element subset $\{a<b<d\}$ by the color ofRamsey's theorem gives an infinite set $M$ on whose triples this induced coloring is constant. Enumerating $M$ increasingly as $x_1<x_2<\cdots$ gives a strictly increasing sequence for which every $x_i+2x_j+3x_k$, $i<j<k$, has the same color.

Solved by gpt-5.6-sol high.

No. The incompatibility part of the Milliken–Taylor theorem provides a finite coloring of $\mathbb{N}$ for which the systems associated with the nonproportional compressed coefficient vectors $(1)$ and $(1,2,3)$ cannot be monochromatic in the same color. The first system is the finite-sums setwhile singleton separated blocks in the second include every $x_i+2x_j+3x_k$ with $i<j<k$. Thus a sequence satisfying the proposed union would contradict that finite coloring.

Solved by gpt-5.6-sol high.

Write $X=\{x_1,\dots ,x_s\}$. Since $X$ is not a spherical point set, there are real coefficients ${\lambda }_i$, not all zero, such thatIndeed, take a minimal nonspherical subset; its points are affinely dependent, and centering the proper spherical subset shows that the corresponding quadratic sum is nonzero. The three relations are invariant under isometries, and rescaling the ${\lambda }_i$ lets us assume $b=1/2$.

Choose $\delta <1/(2s)$ and color every $y$ by the $s$ intervals of length $\delta$ containing the fractional parts of ${\lambda }_i\Vert y{\Vert }^2$. This uses finitely many colors. If $y_1,\dots ,y_s$ were a monochromatic isometric copy of $X$, then eachwould lie within $\delta$ of an integer. Their sum is within $s\delta <1/2$ of an integer, but because ${\sum }_i{\lambda }_i=0$ it equalsa contradiction. Hence $X$ is not a Euclidean Ramsey set.

Solved by gpt-5.6-sol high.

Let $S$ be a finite Ramsey witness for $X$ under $k$ colors. Choose a finite witness $T$ for $Y$ under $k^{|S|}$ colors. Given a coloring of $S\times T$, color each $t\in T$ by the complete vectorThere is a copy $Y^{\prime }\subseteq T$ on which this vector is constant. Thus, for each $s$, the color $c(s,t)$ is independent of $t\in Y^{\prime }$. These values define a $k$-coloring of $S$, which has a monochromatic copy $X^{\prime }$. Then $X^{\prime }\times Y^{\prime }$ is a monochromatic isometric copy of $X\times Y$. This proves the product theorem for Euclidean Ramsey sets.

Every nondegenerate triangle and every line segment is a Euclidean Ramsey set. If $T$ is the given acute triangle and $I$ is a segment of length $t$ in a new orthogonal coordinate, then $T\times I$ is exactly the vertex set of the triangular prism with base $T$ and height $t$. The product theorem therefore makes it Euclidean Ramsey.

Solved by gpt-5.6-sol high.

Put ${\rho }^2=28-28\sqrt{5}/5$ and, for $j\in \mathbb{Z}/30\mathbb{Z}$, defineThe shift $v_j\mapsto v_{j+1}$ is an isometry acting transitively on the finite set $V=\{v_j\}$, so $V$ is a cyclic transitive point set and hence a Euclidean Ramsey set by the Kriz theorem for cyclic transitive point sets.

For every $j,k$,For $k=1,5,11,15,4,14$, these squared distances are respectivelyConsequently $v_0,v_1,v_{26},v_{15}$, in that order, have consecutive side lengths $9,5,9,10$ and equal diagonals $\sqrt{131}$. This is an isometric copy of the required isosceles trapezium. Since every monochromatic copy of $V$ contains this four-point subset, the trapezium is Euclidean Ramsey.

Solved by gpt-5.6-sol high.

Define a six-coloring of ${\mathbb{R}}^n$ byLet $p,q,r$ be the vertices of a unit equilateral triangle and let $o$ be its center. Its circumradius is $1/\sqrt{3}$, and the translation-invariant quadratic identity isSuppose all four points had one color $s$. WriteMultiplying the quadratic identity by $3$ givesThe final expression lies strictly between $-3$ and $3$, whereas $3$ is at distance exactly $3$ from the nearest multiple of $6$. This is impossible. The coloring therefore contains no monochromatic copy of the four-point configuration in any dimension $n\ge 2$.

Solved by gpt-5.6-sol high.