3 Euclidean Ramsey

Launched in 1970 by Erdős, Graham, Montgomery, Rothchild, Spencer and Straus.

Here we want actual copies of some objects.

Colourings of n.

Let us 2-colour 2. Then have 2 points of distance 1 of same colour (consider equilateral triangle of side length 1).

If we 3-colour 3, we can also get 2 points of distance 1, by considering a regular tetrahedron of side length 1.

In general, if we k-colour k, then by looking at the unit regular simplex (k+1), then any 2 have distance 1 between them, so we get 2 points having the same colour and being unit distance apart.

Definition (Isometric copy). We say X is an isometric copy of X if there exists ϕ:XX bijection such that d(x,y)=d(ϕ(x),ϕ(y)).

Definition. We say that a set X (finite) is Ramsey (Euclidean Ramsey) if for all k there exists a finite set Sn (n could be very big) such that whenever S is k-coloured, there exists a monochromatic copy of X.

Example.

  • (1) {0,1} is Ramsey: for k-colours, take a k-dimensional unit simplex.
  • (2) Unit equilateral triangle is Ramsey: for k-colours, can take 2k-dimensional unit simplex.
  • (3) Similarly have that any {0,a} is Ramsey.
  • (4) Similarly any regular simplex is Ramsey.

Remark.

  • (1) If X is infinite, then can build a 2-colouring of n with no monochromatic X (exercise).
  • (2) We took for k-colours S to be in k. Can we do better? For {0,1}, can we do it in ? Colour xxmod2. Need 2 dimensions or higher.

    What about {0,1}? Can we do it in 2? Yes we can:

    PIC

    This shows χ(2)4 (max χ(G) where G is a graph on 2 iwth xy if and only if d(x,y)=1).

    Up until 1990, 4χ(2)7 (by using hexagonal colouring idea).

    De Grey – 2018: showed χ(2)5 using a graph on 1500 vertices. Uses nice ideas and computer assistance.

    In general, 1.1nχ(n)3n. Lower bound is hard – by Frankl-Wilson. Upper bound is by a type of hexagonal colouring, by Posy.

Proposition 3.1. X is Euclidean Ramsey if and only if for all k, there exists n such that whenever n is k-coloured, there exists a monochromatic copy of X.

Proof.

  • If X is Euclidean Ramsey then take S finite in n (for k-colours).
  • We know that for all k-colourings of n, there exists a monochromatic copy of X (by compactness). Suppose not. Therefore, for any set S finite in n, there exists a bad colouring (i.e. not a copy of X monochromatic). Space of all k-colourings is [k]n, which is compact by Tychonoff. Let
    CX={colourings that do not make X monochromatic}.

    This is a closed set. Let {CX}X a copy of X. It has the finite intersection property, because any finite S has a bad k-colouring. Hence the intersection of all CX is non-empty. Hence there exists a colouring of m with no monochromatic X, contradiction.

How can we generate Ramsey sets?

Lemma 3.2. Assuming that:

Then X×Yn+m is also Ramsey.

Remark.

  • {0,a} is Ramsey, and so is {0,b}. So a×b rectangles are Ramsey. In particular, any right angled triangle is Ramsey.

    By considering {0,a}×{0,b}×{0,c}, we can acute angled triangles:

    PIC

Proof. Let k be a colouring of S×T, where S is k-Ramsey for X and T is k|S|-Ramsey for T.

We k|S|-colour T as follows:

c(t)=(c(s1,t),c(s2,t),,c(s|S|,t)).

By choice of T, there exists a monochromatic Y (copy of Y) with respect to c, i.e. c(s,y)=c(s,y) for all y,yY and any sS.

Now k-colour S via c(s)=c(s,y) for some yY (which is well-defined by the above). By the choice of X, there exists monochromatic X with respect to c, and hence X×Y is monochromatic with respect to c.

Homework: Convince yourself that this is a very standard product argument.

Remark.

  • (1) In general to prove sets are Ramsey we will first embed them into other sets (with ‘cool’ symmetry groups) and show that those sets are Ramsey.
  • (2) Spoiler:
    • Obtuse triangles are Ramsey (twisted prism).

    • Any regular n-gon is Ramsey.

    • 3D Platonic solids.

Next time: non-Ramsey. (think about {0,1,2}?)

Proposition 3.3. X={0,1,2} is not Ramsey.

Proof. Recall in n we have

x+y22+xy22=2(x22+y22).

Every copy of {0,1,2} is {xy,x,x+y} with y2=1 (in any n). We have

x+y22+xy22=2x22+2.

If we can find a colouring of 0 such that there does not exist a monochromatic solution to a+b=2c+2. Then use c(x)ϕ(x22).

We 4-colour 0 by ϕ(x)=x(mod4).

Suppose a,b,c all have colour n{0,1,2,3}. Then a+b=c+2 implies

a+b2c=M4+{a}+{b}2{c}=2

where M4 is a multiple of 4. This is impossible as 2<{a}+{b}2{c}<2.

Remark.

  • (1) For all n, there is a 4-colouring of n that stops every copy of X={0,1,2} from being monochromatic.
  • (2) Very important in a+b=2c+2, we got this 2 to not be 0.
  • (3) It will turn out that the property that made {0,1,2} not Ramsey is “it does not lie on a sphere”.

Definition (Spherical). A set Xn is called spherical if it lies on the surfcace of a sphere.

For example, a triangle, a rectangle, any simplex (non-degenerate).

Definition (Simplex). Let x1,,xd be some points. They form a simplex if x1xd,x2xd,,xd1xd are linearly independent. In other words, they do not lie in a (d2)-dimensional affine space.

Aim: If X is Ramsey, then X is spherical.

To do so, we will use a “generalised parallelogram law”.

Lemma 3.4. x1,,xd in n are not spherical if and only if there exists ci, not all 0, such that:

  • (1) ici=0
  • (2) icixi=0
  • (3) icixi220

In the previous proof, we took (1,1,2) and 2 being the value in (3).

Proof.

  • x1,,xd are not spherical. The first two conditions say that x1,,xd is not a simplex: so there exists c1,,cd1 (not all 0) such that ici(xixd)=0 or i=1N1cixi+(c1c2cd1)xd=0.

    First we note that (1)–(3) are invariant under translation by vn:

    • ici(xi+v)=0 since ici=0

    • icixi+v22=icixi22+2ci(xi,v)+civ22=icixi22+2(icixi,v)+v22ici=icixi22

    Let us look at a minimal subset of x1,,xd that is not spherical. If we can show this for without loss of generality x1,,xk (kd) then take ci=0 for all i[k+1,d]. Let {x2,,xk}. This is spherical by minimality. Suppose the sphere radius is r, and centred at y.

    By the above, translate the set such that {x2,,xk} is centred at 0. Since {x1,,xk} are not spherical, it is not a simplex. Hence there exists ci such that ici(xixk)=0. Then

    c1x1+c2x2++ck1xk1+(c1c2ck1)xk=0.

    Without loss of generality ci0. This is fine because the same ci’s work after translations ((1)–(3) is totally invariant under translations). Then

    i=1kcixi22=c1x122+r2(i=2kci)0

    as xir.

  • Suppose there exists ci as in the statement, and assume (x1,,xd) are spherical, centred at r, radius r.

    Translate the set so that they are centred at the origin (this preserves all conditions and does not vhange the value of Icixi20).

    Let xi2=r2. Then

    icixi2=r2ici=0

    so (x1,,xd) are not spherical.

Corollary 3.5 (Generalised parallelogram law). Let X={x1,,xn} be non-spherical. Then there exists c1,,cn not all 0 with ci=0 and there exists b0 such that icixi2=b.

Very important: This is tru for every copy X of X (with the same ci and b!).

Choosing the ci as in Lemma 3.4. If ϕ(X) is a copy of X

PIC

then as we have seen we can translate and the ci and b are unaffected, and ϕ(0)=0.

After that apply A that corresponds to rotation / reflection, and Ax2=x2, so (3) holds.

Theorem 3.6. Assuming that:

Then X is spherical.

Proof. Suppose X is not spherical. Then there exists ci (not all 0) such that ixi2=b and ici=0.

Also true for any copy of X.

Going to split [0,1) into [0,δ),[δ,2δ), for small δ. Then colour depending on where cix2 lies.

Let’s prove that there is a colouring of such that i=1nciyi=b does not have a monochromatic solution. Let i=1n1ci(yiyn)=b. By rescaling, we may assume b=12. Now we split [0,1) into intervals [0,δ),[δ,2δ), where δ is very small. Let

c(y)=(interval where {c1y} is,interval where {c2y} is,).

A (1δ)n1-colouring.

Assume y1,,yn1 monochromatic under c and such that ci(yiyn)=12.

Hence the sum is within (n1)δ of an integer, so not 12, if δ small enough.

We have showed Ramsey implies spherical.

What about spherical implies Ramsey?

Still an open question (1975).

What is known:

Aim: To show tht X={1,2,,m}= a regular m-gon is Ramsey.

PIC

Roughly speaking:

Definition (A-invariant). For a finite AX, we say that a colouring of Xn is A-invariant if it is invariant under chaning the coordinates within A. i.e. for x=(x1,,xn), x=(x1,,xn) if i either xi=xi or xi,xiA implies c(x)=c(x).

Proposition 3.7 (Our product argument). Assuming that:

  • Xd

  • AX

  • k, a finite Se such that whenever S is k-coloured, there exists a copy of X that is constant on A

Then for all n,k, there exists S finite such that whenever S is k-coloured there exists a copy of Xn that is A-invariant.

“boosting from A-constant to A-invariant.”

Proof. (Yawn, product argument…)

We will by induction on n (and all k at once).

n=1 is just the assumption.

Suppose true for n1. Fix k. Let S be a finite set such that whenever S is k|X| coloured, there exists an A-invariant copy of Xn1.

PIC

T a finite set such that whenever T is k|S|-coloured, there exists a copy of X with A monochromatic.

Claim: S×T works for Xn.

By definition of T, if we look at c(s,t)=(c(s1,t),c(s2,t),,c(s|S|,t)), a k|S|-colouring. Thus there exists a copy of X with A monochromatic.

This induces a colouring of S as follows: c(s)=(c(s,a),c(s,x1),,c(s,x|X||A|)) for some aA (note c(s,a) is well-defined). This is a k|X||A|+1-colouring.

Therefore by the choice of n, there exists a copy of Xn1 that is A-invariant.

Then we are done as this copy of X in T is A-invariant.

Next time:

Theorem 3.8 (Kriz Theorem). Every regular m-gon is Ramsey.

Note. We will show that we can find (1,2,,m),(2,3,,m,1),(3,4,,m,1,2),,(m,1,2,,m1) monochromatic, which is a copy of X, but scaled by m (which is fine as m is constant).

Proof. X={1,2,,m}, where the numbers are the names of points.

PIC

We find a copy of mX of the form

(1,2,,m),(2,3,,m,1),(3,4,,m,1,2),(m,1,2,,m1).

We will show by induction on r and all k at once that we can find a copy of X with {1,2,,r} monochromatic.

r=1 is trivial as it is just a point.

r=2 is 2 points at a specified distance (which we showed is Ramsey).

Assume true for r and all k. By Our product argument, there exists S and N such that we have a XN (copy) on which the colouring is {1,2,,r}-invariant on XN (for any N). We will choose N to be as big as we want.

The clever bit:

PIC

We will colour (m1) sets in [N] say a1<a2<<am1 as follows.

PIC

c({a1,,am+1})=(c(w1),c(w2),,c(wr)) is a kr colouring of [N](m1).

As N can be taken as big as needed, by Ramsey there exists a m-monochromatic set. By relabeling, we may assume that this set is {1,2,,m} coordinates.

PIC

Now we look at the following:

PIC

with this we note that the colour of yi is the same as the colour of xi+1.

Now look at: (1,2,,m), 2,3,,m,1), …, (r+1,,r,r1). monochromatic copy of {1,2,,r+1}. They all have the same colour (ignoring this).

Remark. Same proof works for any cyclic set: i.e. a set {x1,,xn} such that the map xixi+1 (modulo n) is a symmetry of the set.

Or equivalently, there exists a cyclic transitive symmetry group on X.

Example. Given by rotation 120 and reflection. Generates order 6.

PIC

This is Ramsey.

The following discussion is non-examinable (until told otherwise).

A soluble group is “built” up from cyclic groups.

Theorem (Kriz). If X hs a soluble, transitive symmetry group, then X is Ramsey.

Rival conjecture to the spherical conjecture (2010, Leader, Russell, Walters):

X is Ramsey if and only if X is subtransitive (subtransitive means that it can be embedded in a transitive set, i.e. it can be embedded in a set that has a transitive isometry group).

Why are they rival?

spherical does not imply sub-transitive.

sub-transitive does imply spherical: let X be sub-transitive. Embed into Y transitive. There exists a unique minimal sphere containing Y, which is preserved by the isometry group.

For spherical doesn’t imply sub-transitive: the kite.

PIC

This is not sub-transitive.

What happens if the kite is Ramsey? It would disprove the 2010 conjecture. If not Ramsey, it would disprove the original conjecture.

It is believed that the transitive conjecture is true.

It could also be the case that neither is true :?.

End of non-examinable discussion.