Ramsey theory and Szemeredi's theorem

 In a previous post we discussed Szemeredi's theorem. This finds a lot of structure in what could a priori be extremely disordered sets, so it shouldn't be surprising that there are Ramsey-theoretic consequences. Recall that van der Waerden's theorem, one of the earliest theorems in Ramsey-theory, states that for any given positive integers $r$ and $k$, there is some number $N$ such that if the integers $\{1, 2, ..., N\}$ are colored, each with one of $r$ different colors, then there is a monochromatic AP of length $k$. We recall Szemeredi's theorem.

Definition: For $A \subseteq \mathbb{N}$, we let the density of $A$ as

\[\bar{d}(A) = \limsup_{(b - a) \to \infty} \frac{A \cap [a, b]}{|b - a|}.\]

Theorem Let $\delta > 0$ and $m \in \mathbb{N}$. Then there exists some $N = S(m, \delta) \in \mathbb{N}$ such that any subset $A \subseteq [N]$ with $|A| \geq \delta N$ contains an $m$-term arithmetic progression.

Clearly, in any finite $k$-colouring of $\mathbb{N}$, there exists a colour class with positive density. Thus, we want to know if merely a positive density implies the existence of progressions. Remarkably, the answer is yes!

In the case of graph colourings, usually what students are first exposed to is what happens when there are finitely many colours. Suppose we now have a colouring $c: \mathbb{N} \to \mathbb{N}$. Can we still find a monochromatic progression of length $m$? Of course not, because $c$ can be injective.

Theorem: For any $c: \mathbb{N} \to \mathbb{N}$, there exists a $m$-AP on which $c$ is either constant orinjective.

It is possible to prove this directly, but it is easy with Szemeredi.

Proof: We set

\[ \delta = \frac{1}{m^2(m + 1)^2}.\]

We let $N = S(m, \delta)$. We write

\[[N] = A_1 \cup A_2 \cup \cdots \cup A_k,\]

where the $A_i$'s are the colour-classes of $c|_{[N]}$. By choice of $N$, we are done if $|A_i| \geq \delta N$ for some $1 \leq i \leq k$. So suppose not.

Let's try to count the number of arithmetic progressions in $[N]$. There are more than $N^2/(m + 1)^2$ of these, as we can take any $a, d \in [N/m + 1]$. We want to show that there is an AP that hits each $A_i$ at most once.

So, fixing an $i$, how many AP's are there that hit $A_i$ at least twice? We need to pick two terms in $A_i$, and also decide which two terms in the progression they are in, e.g.\ they can be the first and second term, or the 5th and 17th term. So there are at most $m^2 |A_i|^2$ terms.

So the number of AP's on which $c$ is injective is greater than

\[\frac{N^2}{(m + 1)^2} - k |A_i|^2 m^2 \geq \frac{N^2}{(m + 1)^2} - \frac{1}{\delta} (\delta N)^2 m^2 = \frac{N^2}{(m + 1)^2} - \delta N^2 m^2 \geq 0.\]

So we are done. Here the first inequality follows from the fact that $\sum |A_i| = [N]$ and each $|A_i| < \delta N$. $\blacksquare$

Our next theorem will mix arithmetic and graph-theoretic properties. Consider a colouring $c: \mathbb{N}^{(2)} \to [2]$. As before, we say a set $X$ is monochromatic if $c|_{X^{(2)}}$ is constant. Now we want to try to find a monochromatic set with some arithmetic properties.

The first obvious question to ask is --- can we find a monochromatic 3-term arithmetic progression? The answer is no. For example, we can define $c(ij)$ to be the parity of largest power of $2$ dividing $j - i$, and then there is no monochromatic $3$-term arithmetic progression.

What if we ask for less? Can we find a blue 10-AP, or if not, find an infinite red set? The answer is again no. To construct a counterexample, we can make progressively larger red cliques, and take all other edges blue. If we double the size of the red cliques every time, it is not hard to check that there is no blue 4-AP, and no infinite red set.

What if we further relax our condition, and only require an arbitrarily large red set?

Theorem For any $c: \mathbb{N}^{(2)} \to \{\mathrm{red}, \mathrm{blue}\}$, either there exists a blue $m$-AP for each $m \in \mathbb{N}$; or there exists arbitrarily large red sets.

Proof: Suppose we can't find a blue $m$-AP for some fixed $m$. We induct on $r$, and try to find a red set of size $r$.

Say $A \subseteq \mathbb{N}$ is a progression of length $N$. Since $A$ has no blue $m$-term progression, so it must contain many red edges. Indeed, each $m$-AP in $A$ must contain a red edge. Also each edge specifies two points, and this can be extended to an $m$-term progression in at most $m^2$ ways. Since there are $N^2/(m + 1)^2$. So there are at least

\[\frac{N^2}{m^2(m + 1)^2}\]

red edges. With the benefit of hindsight, we set

\[\delta = \frac{1}{2m^2(m + 1)^2}.\]

The idea is that since we have lots of red edges, we can try to find a point with a lot of red edges connected to it, and we hope to find a progression in it.

We say $X, Y \subseteq \mathbb{N}$ form an $(r, k)$-structure if

• They are disjoint
• $X$ is red;
• $Y$ is an arithmetic progression;
• All $X- Y$ edges are red;
• $|X| = r$ and $|Y| = k$.

We show by induction that there is an $(r, k)$-structure for each $r$ and $k$.

A $(1, k)$ structure is just a vertex connected by red edges to a $k$-point structure. If we take $N = S(\delta, k)$, we know among the first $N$ natural numbers, there are at least $N^2/(m^2(m + 1)^2)$ red edges inside $[N]$. So in particular, some $v \in [N]$ has at least $\delta N$ red neighbours in $[N]$, and so we know $v$ is connected to some $k$-AP by red edges. That's the base case done.

Now suppose we can find an $(r - 1, k')$-structure for all $k' \in \mathbb{N}$. We set

\[k' = S\left(\frac{1}{2m^2(m + 1)^2}, k\right).\]

We let $(X, Y)$ be an $(r - 1, k')$-structure. As before, we can find $v \in Y$ such that $v$ has $\delta|Y|$ red neighbours in $Y$. Then we can find a progression $Y'$ of length $k$ in the red neighbourhood of $v$, and we are done, as $(X \cup \{v\}, Y')$ is an $(r, k)$-structure, and an ``arithmetic progression'' within an arithmetic progression is still an arithmetic progression. $\blacksquare$