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 ϕ:X→X′ 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 S⊆ℝn (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 x↦⌊x⌋mod2. 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 x∼y 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×Y⊂ℝn+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 Y.

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,y′∈Y and any s∈S.

Now k-colour S via c″(s)=c″(s,y) for some y∈Y′ (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+y∥22+∥x−y∥22=2(∥x∥22+∥y∥22).

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

∥x+y∥22+∥x−y∥22=2∥x∥22+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)→ϕ(∥x∥22).

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+b−2c=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 X⊆ℝn 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 x1−xd,x2−xd,…,xd−1−xd are linearly independent. In other words, they do not lie in a (d−2)-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) ∑⁡ici∥xi∥22≠0

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,…,cd−1 (not all 0) such that ∑⁡ici(xi−xd)=0 or ∑⁡i=1N−1cixi+(−c1−c2−⋯−cd−1)xd=0.

    First we note that (1)–(3) are invariant under translation by v∈ℝn:

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

    • ∑⁡ici∥xi+v∥22=∑ici∥xi∥22+2ci(xi,v)+ci∥v∥22=∑ici∥xi∥22+2(∑icixi,v)+∥v∥22∑ici=∑ici∥xi∥22

    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 (k≤d) then take ci=0 for all i∈[k+1,d].

    Since {x1,…,xk} are not spherical, it is not a simplex. Hence there exists ci such that ∑⁡ici(xi−xk)=0. Then

    c1x1+c2x2+⋯+ck−1xk−1+(−c1−c2−⋯−ck−1)xk=0.

    Without loss of generality c1≠0 (because the conditions are invariant under reordering the ci’s).

    Consider {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. This is fine because the same ci’s work after translations ((1)–(3) are totally invariant under translations). Then

    ∑i=1kci∥xi∥22=c1∥x1∥22+r2(∑i=2kci)≠0

    as ∥x1∥≠r.

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

    Translate the set so that they are centred at the origin (this preserves all conditions and does not vhange the value of ∑⁡Ici∥xi∥2≠0).

    Let ∥xi∥2=r2. Then

    ∑ici∥xi∥2=r2∑ici=0

    so (x1,…,xd) are not spherical. □

Corollary 3.5 (Generalised parallelogram law). Assuming that:

  • X={x1,…,xn} non-spherical

Then there exists c1,…,cn not all 0 with ∑⁡ci=0 and there exists b≠0 such that ∑⁡ici∥xi∥2=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 ∥Ax∥2=∥x∥2, 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 ∑⁡i∥xi∥2=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 ci∥x∥2 lies.

Let’s prove that there is a colouring of ℝ such that ∑⁡i=1nciyi=b does not have a monochromatic solution. Let ∑⁡i=1n−1ci(yi−yn)=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δ⌋)n−1-colouring.

Assume y1,…,yn−1 monochromatic under c and such that ∑⁡ci(yi−yn)=12.

Hence the sum is within (n−1)δ 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 A⊆X, 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,xi′∈A implies c(x′)=c(x).

Proposition 3.7 (Our product argument). Assuming that:

  • X⊆ℝd

  • A⊆X

  • ∀⁡k,∃⁡ a finite S⊆ℝe 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 n−1. Fix k. Let S be a finite set such that whenever S is k|X| coloured, there exists an A-invariant copy of Xn−1.

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 a∈A (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 Xn−1 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,…,m−1) 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,…,m−1).

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 (m−1) sets in [N] say a1<a2<⋯<am−1 as follows.

PIC

c′({a1,…,am−1})=(c(w1),c(w2),…,c(wr)) is a kr colouring of [N](m−1).

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,r−1). 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 xi↦xi+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.