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

Fix a number $k$ of colors. For a two-point set whose points are distance $d$ apart, take the vertices of a regular simplex with $k+1$ vertices and side length $d$. The pigeonhole principle gives two vertices of one color, and they form the required congruent copy. Thus every two-point set, equivalently every line segment, is a Euclidean Ramsey set.

For an equilateral triangle of side length $d$, take a regular simplex with $2k+1$ vertices and side length $d$. The pigeonhole principle gives three vertices of one color, and every three vertices of a regular simplex form an equilateral triangle. Hence every equilateral triangle is Euclidean Ramsey.

To prove the product theorem for Euclidean Ramsey sets, let $S_X$ be a finite Ramsey witness for $X$ under $k$ colors. There are at most $k^{|S_X|}$ possible color patterns on $S_X$. Choose a finite Ramsey witness $S_Y$ for $Y$ under that many colors. Given a $k$-coloring of $S_X\times S_Y$, color each $y\in S_Y$ by the complete patternThere is a copy $Y^{\prime }\cong Y$ on which this pattern is constant. The common pattern on $S_X$ contains a monochromatic copy $X^{\prime }\cong X$. Every point of $X^{\prime }\times Y^{\prime }$ then has the same original color, and the orthogonal product is congruent to $X\times Y$.

A rectangle is the Cartesian product of two line segments, so it is Euclidean Ramsey. Three suitable vertices of a rectangle form a right triangle; any subset of a monochromatic set is monochromatic. Thus every right triangle is Euclidean Ramsey.

It remains to show that the collinear set $\{0,1,2\}$ behaves differently. In every ${\mathbb{R}}^m$, use the finite coloringA congruent copy has the form $a-v,a,a+v$ with $\Vert v\Vert =1$ for the Euclidean norm. The parallelogram law givesPut $n_{+}=\lfloor 2\Vert a+v{\Vert }^2\rfloor$, $n_{-}=\lfloor 2\Vert a-v{\Vert }^2\rfloor$, and $n_0=\lfloor 2\Vert a{\Vert }^2\rfloor$. The errors introduced by the three floor functions show thatIf all three points had one color, the integer in the middle would be divisible by ten, which is impossible. This proves the three-term unit arithmetic progression is not Euclidean Ramsey assertion.

The Hales-Jewett theorem says that, for every finite alphabet $A$ and number of colors $r$, there is $N$ such that every $r$-coloring of $A^N$ contains a monochromatic combinatorial line.

We use the standard insensitivity lemma. Assuming the Hales-Jewett theorem for alphabets of size $m-1$, fix two letters $a,b$ in an $m$-letter alphabet. For every $r$ and $d$, there is $N$ such that each $r$-coloring of $A^N$ has a $d$-dimensional combinatorial subspace on which changing any selection of variable coordinates from $a$ to $b$, or from $b$ to $a$, leaves the color unchanged.

Here is the finite fusion proof of the lemma. Choose the sizes of $d$ successive coordinate blocks backwards. On the last block, omit $b$ and color a word over $A\setminus \{b\}$ by the vector of all colors obtained after filling the previously chosen blocks in every possible way and then replacing any chosen occurrences of $a$ by $b$. This is a finite derived coloring. The induction hypothesis supplies a combinatorial line on which that entire vector is constant. Treat its active coordinates as one new variable block and repeat. After $d$ repetitions, each replacement of $a$ by $b$ can be pushed into the last block where it was created, and equality of the derived color vectors shows that it does not alter the original color. This proves the insensitivity lemma.

Now induct on $m=|A|$. The case $m=1$ is immediate. For $m>1$, choose the target dimensions backwards and apply the insensitivity lemma successively to the pairsAt every step pass to the resulting nested combinatorial subspace, so the insensitivities already obtained are retained. On the final positive-dimensional subspace, replacing $a_m$ by any other letter does not change the color. Any two words can be connected by such replacements, so the whole subspace is monochromatic. It contains a combinatorial line, completing the induction and the proof.

The Gallai theorem for an integer lattice says that, for every finite $S\subseteq {\mathbb{N}}^d$ and every finite coloring of ${\mathbb{N}}^d$, there are $u\in {\mathbb{N}}^d$ and $q\ge 1$ such that the homothetic copyis monochromatic.

Write $S=\{s_1,\dots ,s_m\}$ and apply the Hales-Jewett theorem to the alphabet $[m]$. Color a word $w\in [m{]}^N$ by the color ofwhere a fixed positive vector $t$ keeps the image in ${\mathbb{N}}^d$ under either convention for the natural numbers. On a monochromatic combinatorial line, let $I$ be the active coordinate set. The fixed coordinates contribute a vector $u-t$, while the word whose active letter is $i$ maps toThese points form a monochromatic copy $u+|I|S$, proving Gallai's theorem.

This is always true. Pull the given coloring of ${\mathbb{N}}^2$ back along the dilationApply the Gallai theorem for an integer lattice to the four vertices of the unit square. The image of the resulting homothetic square has side length $2q$, which is even, and all four vertices have one color.

This can fail. Color $(x,y)$ by the parity of $x$. If a square has odd side length $q$, then the two endpoints of each horizontal side have first coordinates of opposite parity, so the square cannot be monochromatic.

This can also fail. Color $(x,y)$ by $x(\mathrm{mod}3)$. No power of two is divisible by three, so the endpoints of a horizontal side whose length is a power of two receive different colors.

A rational matrix is a partition regular matrix when every finite coloring of the positive integers admits a monochromatic positive vector in its kernel. Its columns have the columns property if their indices can be partitioned into ordered nonempty blocks $B_1,\dots ,B_s$ such that the columns in $B_1$ sum to zero and, for $j>1$, the sum over $B_j$ lies in the rational linear span of the columns in the earlier blocks. Rado's theorem states that a rational matrix is partition regular if and only if its columns have this property.

For one equation, clear denominators and writeThe one-row columns property is equivalent to the existence of a nonempty $I\subseteq [n]$ with

First suppose such an $I$ exists. Choose $i_0\in I$, put $c=|c_{i_0}|$, $C={\sum }_{j\notin I}{c}_j$, and choose $p\ge |C|$. The monochromatic m-p-c set theorem, whose finite induction proof uses the Van der Waerden theorem, gives positive $z_1,z_2$ for which all numbersare positive and have one color. SetThe middle coefficient is the integer $-C\mathrm{sgn}(c_{i_0})$, of absolute value at most $p$, so all the $x_i$ belong to the monochromatic set. Their $z_1$ contribution vanishes because the coefficients over $I$ sum to zero, and their $z_2$ contribution isThus the equation is partition regular.

Conversely, suppose no nonempty subset of the coefficients sums to zero. Choose a prime number $p$ that divides none of the finitely many nonzero subset sums. Color each positive integer by its last nonzero digit coloring in base $p$. If a monochromatic solution existed, let $v$ be the smallest P-adic valuation among its coordinates and let $I$ index the coordinates of valuation $v$. After division by $p^v$ and reduction modulo $p$, all $x_i$ with $i\in I$ have the same nonzero last digit $r$, while the other terms vanish. The equation would givecontrary to the choice of $p$. This proves the Rado theorem for one equation.

No. TakeThe full set of coefficients sums to zero, so the equation is partition regular by the Rado theorem for one equation. Every solution satisfieswhich can never be positive.

No. ConsiderEvery finite coloring of the positive integers has an infinite color class. Choose $x<y$ in that class with $y/x$ as large as needed. Assigning $y$ to the three positive-coefficient variables and $x$ to the negative-coefficient variable makes the linear formpositive. Reversing the assignments makes it $3x-4y<0$. Thus both strict-sign hypotheses hold in every finite coloring.

The nonempty subset sums of $1,1,1,-4$ are among $1,2,3,-1,-2,-3,-4$, so none is zero. The Rado theorem for one equation therefore says that this coefficient vector is not partition regular.

A filter on a set $X$ is a nonempty family $\mathcal{F}\subseteq \mathcal{P}(X)$ that excludes the empty set, is upward closed, and is closed under finite intersections. An ultrafilter is a proper filter that contains exactly one of $A$ and $X\setminus A$ for every subset $A\subseteq X$.

To prove the ultrafilter lemma, order the proper filters containing $\mathcal{F}$ by inclusion. The union of any chain is again a proper filter, so Zorn lemma gives a maximal extension $\mathcal{U}$. If neither $A$ nor $X\setminus A$ belonged to $\mathcal{U}$, adjoining either one would generate an improper filter. There would then be $U,V\in \mathcal{U}$ with $U\cap A=\varnothing$ and $V\cap (X\setminus A)=\varnothing$. But $U\cap V=\varnothing$, contradicting propriety. Hence $\mathcal{U}$ is an ultrafilter.

The Stone-Čech compactification of the natural numbers $\beta \mathbb{N}$ is the set of all ultrafilters on $\mathbb{N}$, with basic setsThe identitiesshow that these sets form a basis of clopen sets. Distinct ultrafilters disagree on some $A$; one lies in $\overline{A}$ and the other in the disjoint set $\overline{\mathbb{N}\setminus A}$. Thus $\beta \mathbb{N}$ is a Hausdorff space.

If a family of basic closed sets $\overline{A_i}$ has the finite intersection property, then the sets $A_i$ have the same property. They generate a proper filter, which extends to an ultrafilter lying in every $\overline{A_i}$. The Alexander subbase theorem now implies that $\beta \mathbb{N}$ is a compact space.

Assume condition ii. In a finite coloringan ultrafilter contains exactly one color class: at least one must belong to it because their union is $\mathbb{N}$, and two disjoint classes cannot both belong to a proper filter. The chosen $C_i$ contains a member of $\mathcal{S}$, which is therefore monochromatic. This proves condition i.

Assume condition i and call a set $B\subseteq \mathbb{N}$ bad when it contains no member of $\mathcal{S}$. No finite collection of bad sets covers $\mathbb{N}$: if it did, assigning each integer to the first bad set containing it would give a finite coloring whose color classes are bad, contrary to condition i. Consequentlyhas the finite-intersection property. It generates a proper filter on a set, which the ultrafilter lemma extends to an ultrafilter $\mathcal{U}$. If some $A\in \mathcal{U}$ were bad, then $\mathbb{N}\setminus A$ would also belong to $\mathcal{U}$ by construction, contradicting propriety. Hence every $A\in \mathcal{U}$ contains a member of $\mathcal{S}$, proving condition ii.

For the final question, let $\mathcal{S}$ consist of the pairs $\{x,2x\}$ and $\{x,3x\}$. Color $n$ byMultiplication by either two or three reverses this parity, so this two-coloring has no monochromatic member of $\mathcal{S}$. Condition i fails, and the equivalence just proved shows that no ultrafilter with the stated property exists.