Euclidean Ramsey Theory 2 – Ramsey DocCourse Prague 2016 – Mike Pawliuk

The following notes are from the Ramsey DocCourse in Prague 2016. The notes are taken by me and I have edited them. In the process I may have introduced some errors; email me or comment below and I will happily fix them.

Title: Euclidean Ramsey Theory 2 (of 3).

Lecturer: David Conlon.

Date: November 25, 2016.

Main Topics: Ramsey implies spherical, an algebraic condition for spherical, partition regular equations, an analogous result for edge Ramsey.

Definitions: Spherical, partition regular.

Lecture 1 – Lecture 2 – Lecture 3

Ramsey DocCourse Prague 2016 Index of lectures.

Introduction

In the first lecture we defined the relevant terms and then established that all (non-degenerate) triangles are Ramsey. In this lecture we will compare the property of being spherical with being Ramsey. In this lecture we will show that Ramsey implies spherical (or more precisely, that non spherical sets cannot be Ramsey).

Definition. A set $X$ is spherical if there is an $n$ such that $X \subseteq S^n$ .

Typically $S$ will be finite, but this is not formally required.

The proofs are those of Erdos et Al, and go by establishing a tight algebraic condition for a set being spherical.

Show that three points in a line are not Ramsey.
Define a partition regular equation.
Prove two colouring lemmas about partition regular equations.
Relate spherical sets to a tight algebraic condition.
Put everything together to prove that Ramsey implies spherical.

(Evenly spaced) lines aren’t Ramsey

Let $L = \{x,y,z\}$ where $d(x,y) = d(y,z) = 1$ and $d(x,z) = 2$ ; it is a line segment with three points equally spaced.

Theorem. The line segment $L$ is not Ramsey.

“The reason is you can take a `spherical shell’ colouring.” These shell colourings are very important.

This doesn’t work for `cube colourings’ (i.e. using a different norm) since by Dvoretsky’s Theorem, hyperplane slices of cubes basically look spherical.

Proof. Fix $n$ . Define the colouring $\chi : \mathbb{R}^n \rightarrow \{0,1,2,3\}$ by $\chi(x) = \lfloor x \cdot x \rfloor$ . (You’re taking spherical shells of radii $\sqrt{n}$ .)

[Picture]

By the Cosine rule we get $a^2 = b^2 + 1 - 2b\cos(\theta)$ and $c^2 = b^2 + 1 + 2b\cos(\theta)$ . So we get $a^2 + c^2 = 2b^2 +2$ .

Suppose that $x,y,z$ have the same colour. This means that there is an $i \in \{0,1,2,3\}$ such that $a^2 = 4k_1 + i + \epsilon_1$ and $b^2 = 4k_2 + i + \epsilon_2$ and $c^2 = 4k_3 + i + \epsilon_3$ , where each $0 \leq \epsilon_j < 1$ .

Putting this into our cosine law info gives
$\displaystyle 4(k_1 + k_3 - 2k_2) -2 = 2\epsilon_2 - \epsilon_1 - \epsilon_3,$
which is a contradiction since the left is $2 \mod 4$ but the right is strictly between $-2$ and $2$ .

Partition regular equations

Eventually we will relate the condition of a set being spherical with a tight algebraic condition. With this in mind, we examine when algebraic conditions can yield Ramsey witnesses. We start with a general discussion of partition regular equations.

Definition. An equation is partition regular if every finite colouring of $\mathbb{R}^n$ contains a monochromatic solution to the equation.

For example,

Schur. $x + y = z$ .
Van der Waerden. $x + y = 2z$ .
Rado. A simple equation $\sum_{i=1}^k c_i x_i = 0$ is partition regular if and only if there is a non empty $I$ such that $\sum_{i \in I} c_i = 0$ .

Exercise. If the equation is translation invariant then you get a corresponding density result.

Use this to show that you always get a non-trivial solution.

Are there inhomogeneous equations that are partition regular? Two lemmas.

First an example.

Example. $x + y = z + 1$ .

We can homogenize this equation by replacing the variables. Use $x = x^\prime+1, y = y^\prime +1$ and $z = z^\prime+1$ . This gives the equation $x^\prime + y^\prime = z^\prime$ .

Basically, these are the only types of partition regular equations.

Lemma 1. There is a $2n$ colouring $\chi$ of $\mathbb{R}$ with no solution of
$\displaystyle \sum_{i=1}^n (x_i - x^\prime_i) = 1$
with $\chi(x_i) = \chi(x^\prime_i)$ for all $i$ .

The number of colours is equal to the number of variables.

This is a strong result of the equation not being partition regular. You can’t have a monochromatic solution, you can’t even have all the paired variables agree!

The idea is to colour whether you are in a certain interval.

Proof. Fix $n$ . Colour $x \in \mathbb{R}$ with $j$ if $x \in [2m + \frac{j}{n}, 2m + \frac{j+1}{n}]$ for some integer $m$ .

If $\chi(x_i) = \chi(x^\prime_i)$ , then $x_i - x^\prime_i = 2m_i + \epsilon_i$ where $\vert \epsilon_i \vert < \frac{1}{n}$ .

So
$\displaystyle 1 = \sum_{i=1}^n (x_i - x^\prime_i) = \sum_{i=1}^n 2m_i + \sum_{i=1}^n \epsilon_i.$

Here the first sum is an even number, and the second is $< 1$ , a contradiction.

Now we increase the number of colours to deal with a more general equation.

Lemma 2. There is a $(2n)^n$ colouring $\chi$ of $\mathbb{R}$ with no solution of
$\displaystyle \sum_{i=1}^n c_i (x_i - x^\prime_i) = b \neq 0$
with $\chi(x_i) = \chi(x^\prime_i)$ for all $i$ .

Proof. Fix $n$ . By dividing by $b$ it suffices to consider $b = 1$ .

Let $\chi$ be the ( $2n$ ) colouring from Lemma 1.

Define $\chi^\prime(x) = (\chi(c_1 x), \chi(c_2 x), \ldots, \chi(c_n x))$ .

Now if $\chi^\prime(x_i) = \chi^\prime(x^\prime_i)$ , then $\chi(c_i x_i) = \chi(c_i x^\prime_i)$ .

So $c_i(x_i - x_i^\prime) = 2m_i + \epsilon_i$ where $\vert \epsilon_i \vert < \frac{1}{n}$ .

If this happens for all $i$ , then we have a contradiction identical to the one in Lemma 1.

In the original paper there was a similar lemma but it had a worse bound on the number of colours. This improvement was observed by Strauss a little later.

Note that these equations are not susceptible to the “translation trick” since $(y_i + 1) - (y_i^\prime + 1) = y_i - y_i^\prime$ .

Characterizing spherical in terms of an algebraic condition

The following is the main technical lemma. The proof is purely algebraic.

Theorem. A set $X = \{\vec{x}_0, \ldots, \vec{x}_t\} \subset \mathbb{R}^n$ is not spherical if and only if there are constants $c_i$ , not all $0$ , such that
$\displaystyle \sum_{i=1}^t c_i (\vec{x}_i - \vec{x}_0) = 0$
and
$\displaystyle \sum_{i=1}^t c_i (\vec{x}_i^2 - \vec{x}_0^2) = \vec{b}.$

For readability, we will write $x$ instead of $\vec{x}$ . We will make use of the following useful fact:

Useful identity.
$\displaystyle a^2 - b^2 = (a - c)^2 - (b - c)^2 + 2a \cdot c - 2 b \cdot c.$
Using $c=b$ yields
$\displaystyle a^2 - b^2 = (a - b)^2 + 2b(a - b).$

Proof of $\Leftarrow$ . Assume that $X$ is spherical and satisfies the first equation. We will show the second equality fails.

Say $X$ has centre $w (\in \mathbb{R}^n)$ and radius $r$ .

For each $i$ we have:

$r^2$

$= (x_i - w) \cdot (x_i - w)$
$= ((x_i -x_0) + (x_0 - w)) \cdot ((x_i -x_0) + (x_0 - w))$
$= (x_i -x_0)^2 + (x_0 - w)^2 + 2(x_i - x_0)(x_0-w)$ . Here the second term is $r^2$ .

So we must have $(x_i -x_0)^2 = -2(x_i - x_0)(x_0-w)$ for each $i$ . So by multiplying by $c_i$ and adding up we get
$\displaystyle \sum_{i=1}^t c_i (x_i - x_0)^2 = -2(x_0-w)\sum_{i=1}^t c_i (x_i-x_0) = 0.$

By using the special case of the useful identity, we get:
$\displaystyle \sum_{i=1}^t c_i (x_i^2 - x_0^2) = \sum_{i=1}^t(x_i-x_0)^2 - 2x_0 \sum_{i=1}^t c_i (x_0 - x_i).$

We know the first sum is $0$ by our above calculations, and by assumption we know
$\displaystyle 2x_0 \cdot \sum_{i=1}^t c_i (x_i - x_0) = 0,$
a contradiction.

Proof of $\Rightarrow$ . Assume $X$ is not spherical, and moreover that it is minimal (in the sense that removing any one point makes it spherical). In particular, $X$ is not a non-degenerate simplex. So there is a linear relation
$\displaystyle \sum_{i=1}^t c_i (x_i - x_0).$

Assume that $c_t \neq 0$ . By minimality, $\{x_0, \ldots, x_{t-1}\}$ is spherical, and is on a sphere with centre $w$ and radius $r$ .

Thus
$\displaystyle x_i^2 - x_0^2 = (x_i - w)^2 - (x_0 - w)^2 + 2x_i \cdot w - 2 x_0 \cdot w.$

So
$\displaystyle \sum c_i (x_i^2 - x_0^2) = \sum c_i ((x_i - w)^2 - (x_0 - w)^2) + 2w \cdot \sum c_i (x_i - x_0),$

here the second sum is $0$ , and the first, by minimality, is
$\displaystyle c_t ((x_t - w)^2 - (x_0 - w)^2) \neq 0,$
which isn’t $0$ since the distances of $x_t$ and $x_0$ to $w$ are different.

Ramsey implies spherical

We are now in a position to put everything together.

Theorem. All Ramsey sets are spherical.

Proof. Assume $X$ is not spherical. So there are constants $c_1, \ldots, c_t$ and a vector $\vec{b} \neq \vec{0}$ such that
$\displaystyle \sum c_i (\vec{x}_i - \vec{x}_0) = 0$
and
$\displaystyle \sum c_i (\vec{x}_i^2 - \vec{x}_0^2) = \vec{b}.$

Technical exercise. Any congruent copy of $X$ satisfies the same equations.

(Use the fact that congruence is formed by rotations and translations. The translations will spit out terms like $\star$ .)

In every non-zero coordinate of $\vec{b}$ use the colouring $\chi$ from Lemma 2, and set $\chi^\prime(x) = \chi(x^2)$ . This will give no monochromatic solution to
$\displaystyle \sum c_i (\vec{x}_i^2 - \vec{x}_0^2) = \vec{b}.$

This is the end of this lecture’s material on point-Ramsey. We shift gears a little now.

Edge Ramsey

Instead of colouring points, we can colour pairs of points. This leads to the notion of edge Ramsey. We mention two results in this area.

Theorem. If the edge set $X$ is not vertex spherical and not bipartite, it is not edge Ramsey.

Proof. Suppose the vertex set is not spherical. Colour the points, using $\chi$ , so that no copy of $X$ has a monochromatic vertex set.

Now colour the edge $(x,y)$ with $\chi^\prime (x,y) = (\chi(x), \chi(y))$ .

Each edge has the same colour and must contain two distinct vertex colours. So the edge set is bi-partite.

This gives us an analogous theorem to the theorem that Ramsey implies spherical.

Theorem. If $X$ is edge Ramsey then the points lie on two concentric spheres.

The proof is a variation on what we’ve seen.

References

See lecture 1 for references.

Introduction

(Evenly spaced) lines aren’t Ramsey

Partition regular equations

Are there inhomogeneous equations that are partition regular? Two lemmas.

Characterizing spherical in terms of an algebraic condition

Ramsey implies spherical

Edge Ramsey

References

Share this:

Like this:

Related

Leave a Reply Cancel reply