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.
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 is spherical if there is an such that .
Typically 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 where and ; it is a line segment with three points equally spaced.
“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 . Define the colouring by . (You’re taking spherical shells of radii .)
By the Cosine rule we get and . So we get .
Suppose that have the same colour. This means that there is an such that and and , where each .
Putting this into our cosine law info gives
which is a contradiction since the left is but the right is strictly between and .
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.
- Schur. .
- Van der Waerden. .
- Rado. A simple equation is partition regular if and only if there is a non empty such that .
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.
We can homogenize this equation by replacing the variables. Use and . This gives the equation .
Basically, these are the only types of partition regular equations.
with for all .
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 . Colour with if for some integer .
If , then where .
Here the first sum is an even number, and the second is , a contradiction.
Now we increase the number of colours to deal with a more general equation.
with for all .
Proof. Fix . By dividing by it suffices to consider .
Let be the () colouring from Lemma 1.
Now if , then .
So where .
If this happens for all , 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 .
Characterizing spherical in terms of an algebraic condition
The following is the main technical lemma. The proof is purely algebraic.
For readability, we will write instead of . We will make use of the following useful fact:
Proof of . Assume that is spherical and satisfies the first equation. We will show the second equality fails.
Say has centre and radius .
For each we have:
- . Here the second term is .
So we must have for each . So by multiplying by and adding up we get
By using the special case of the useful identity, we get:
We know the first sum is by our above calculations, and by assumption we know
Proof of . Assume is not spherical, and moreover that it is minimal (in the sense that removing any one point makes it spherical). In particular, is not a non-degenerate simplex. So there is a linear relation
Assume that . By minimality, is spherical, and is on a sphere with centre and radius .
here the second sum is , and the first, by minimality, is
which isn’t since the distances of and to are different.
Ramsey implies spherical
We are now in a position to put everything together.
Proof. Assume is not spherical. So there are constants and a vector such that
Technical exercise. Any congruent copy of satisfies the same equations.
(Use the fact that congruence is formed by rotations and translations. The translations will spit out terms like .)
In every non-zero coordinate of use the colouring from Lemma 2, and set . This will give no monochromatic solution to
This is the end of this lecture’s material on point-Ramsey. We shift gears a little now.
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.
Proof. Suppose the vertex set is not spherical. Colour the points, using , so that no copy of has a monochromatic vertex set.
Now colour the edge with .
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.
The proof is a variation on what we’ve seen.
See lecture 1 for references.