A note on diameter-Ramsey sets
Jan Corsten Nóra Frankl

[
    Pavel Exner
    December 30, 2023
=====================


A finite set A ⊂ℝ^d is called diameter-Ramsey if for every r ∈, there exists some n ∈ and a finite set B ⊂ℝ^n with A=B such that whenever B is coloured with r colours, there is a monochromatic set A' ⊂ B which is congruent to A.
We prove that sets of diameter 1 with circumradius larger than 1/√(2) are not diameter-Ramsey. In particular, we obtain that triangles with an angle larger than 135^∘ are not diameter-Ramsey, improving a result of Frankl, Pach, Reiher and Rödl. Furthermore, we deduce that there are simplices which are almost regular but not diameter-Ramsey.




§ INTRODUCTION

In this note, we discuss questions related to Euclidean Ramsey theory, a field introduced in <cit.> by Erdős, Graham, Montgomery, Rothschild, Spencer and Straus. A finite set A ⊂ℝ^d is called Ramsey if for every r ∈, there exists some n ∈ such that in every colouring of ℝ^n with r colours, there is a monochromatic set A' ⊂^n which is congruent to A. The problem of classifying which sets are Ramsey has been widely studied and is still open (see <cit.> for more details). 

The diameter of a set P ⊂^d is defined by P := sup{x-y : x,y ∈ P }, where · denotes the Euclidean norm. Recently,  Frankl, Pach, Reiher and Rödl <cit.> introduced the following stronger property. 

 A finite set A ⊂ℝ^d is called diameter-Ramsey if for every r ∈, there exists some n ∈ and a finite set B ⊂ℝ^n with A=B such that whenever B is coloured with r colours, there is a monochromatic set A' ⊂ B which is congruent to A.


It follows from the definition that every diameter-Ramsey set is Ramsey. A set A ⊂^d is called spherical, if it lies on some d-dimensional sphere and the circumradius of A, denoted by A, is the radius of the smallest sphere containing A.
(Note that if A is spherical and is not contained in a proper subspace of ℝ^d, then there is a unique sphere that contains it.)
In <cit.> it was proved that every Ramsey set must be spherical. Our main result states that every diameter-Ramsey set must also have a small circumradius.


If A ⊂ℝ^d is a finite, spherical set with circumradius strictly larger than A/√(2), then A is not diameter-Ramsey.


 Frankl, Pach, Reiher and Rödl <cit.> proved that acute and right-angled triangles are diameter-Ramsey, while triangles having an angle larger than 150^∘ are not. <ref> implies the following improvement.


Triangles with an angle larger than 135^∘ are not diameter-Ramsey.



Let us call a d-simplex A = {p_1, …, p_d+1} -almost regular if 
    1/d+12∑_1 ≤ i < j ≤ d+1 A^2 - p_i -p_j^2 ≤· A^2.
 In <cit.> it was further proved that -almost regular simplices are diameter-Ramsey for every ≤ 1/d+12. This is a rather small class of simplices since 1/d+12 tends to zero, but another corollary of <ref> shows that one cannot hope for much more. 



For every d ∈ and every > √(d)/d+12, there is an -almost regular d-simplex which is not diameter-Ramsey.   


For d ∈ and r ≥ 0, we denote the closed d-dimensional ball of radius r centred at the origin by B_d(r).
We will deduce <ref> from the following result.


For every finite, spherical set A ⊂^d and every positive number r <  A, there is some k = k(A,r) ∈ such that the following holds. For every D ∈, there is a colouring of B_D(r) with k colours and with no monochromatic, congruent copy of A.


A result of Matoušek and Rödl <cit.> shows that the conclusion of <ref> does not hold whenever r >  A. We do not know what happens when r =  A.


After completing this work, we have learnt that Theorem <ref> has independently been proved by  Frankl, Pach, Reiher and Rödl, with a similar proof (János Pach, private communication).






§ PROOFS



 §.§ Proof of the main theorem

Fix some finite, spherical A ⊂^d and some positive number r <  A. The following claim is the key step of the proof.


There exists a constant c = c(A,r) > 0 such that for every D ∈ and for every congruent copy A' of A in B_D(r) we have max_x,y ∈ A'(  x -  y ) ≥ c. 


 First observe that it is sufficient to prove the claim for D = d+1. For D < d+1, this follows immediately from B_D(r) ⊂ B_d+1(r), and for D>d+1 we can consider the at most (d+1)-dimensional subspace spanned by the vertices of A' and the origin.

Let E={e:A→ B_D(r)}⊂ B_D(r)^|A| be the set of all embeddings of A to B_D. It is easy to see that, if e_1, e_2, …∈ E and the pointwise limit e := lim_n e_n exists, then e ∈ E. Therefore, E is a closed subset of a compact metric space and hence E is compact as well. Define f:E→ℝ by 
    f(e) := max_x,y ∈ e(A)( x -  y ).


Clearly, f(e)≥ 0 for every e ∈ E, and f(e) = 0, if and only if e(A) lies on a sphere around the origin. But since e(A) > r for every embedding e ∈ E, this is not the case, and hence f(e)>0 for all e ∈ E. Finally, since f is continuous, there is a constant c >0 such that f(e) ≥ c for all e ∈ E.




  Let k = ⌊ r/c ⌋ + 1 now, and fix some D ∈. We will colour points in B_D(r) by their distance to the origin: Define χ : B_D(r) →{0, …, k-1 } by χ(x) = ⌊ 1/c ·x⌋, and let A' ⊂ B_D(r) be a congruent copy of A. It follows immediately from <ref> that there are x,y ∈ A' with x-y≥ c, and hence χ (x) ≠χ (y). This finishes the proof of the main theorem.




 §.§ Implications of the main theorem

In this section we will deduce <ref> and then <ref>. In order to do so we will use the following classical result.


Every bounded set A ⊂^d can be covered by a closed ball of radius √(d/(2d+2))· A.


In particular, every finite set B ⊂^n can be covered by a ball of radius B /√(2), and hence <ref> follows immediately from <ref>.

Furthermore, if T is a triangle with an angle α>135^∘ and diameter a, it is folklore that the circumradius of T is a/(2sinα)>a/√(2). Thus, we obtain <ref> as a corollary of <ref>.

To prove <ref>, we show that we can move one vertex of the regular d-simplex by just a little bit to obtain a simplex of circumradius strictly larger than 1/√(2). We will use the elementary geometric fact that the circumradius of a d-dimensional unit simplex is √(d/(2d+2)).


Let δ >0, r^2 = 1/2 + δ, a^2 = 1/(2d) +δ, and define H_a := { x ∈^d : x_d = a }. Then B:=B_d(r) ∩ H_a is a (d-1)-dimensional ball of radius √(r^2 - a^2) = √((d-1)/(2d)), and hence there is a (d-1)-dimensional unit simplex A'={p_1, …, p_d} contained in the boundary of B. Finally, let A = A' ∪{p_d+1}, where p_d+1 = (0, …, 0, r).

By construction, we have A > 1/√(2), p_i-p_j^2 = 1 for all 1 ≤ i < j ≤ d, and p_i - p_d+1^2 = 1 - 1/√(d) + O(δ) for all 1 ≤ i ≤ d. Hence the theorem follows from <ref> after choosing δ > 0 small enough.




§ REMARKS


In <cit.> it was asked whether there exists an obtuse triangle which is diameter-Ramsey. Although we could not answer this question, we think the answer is no. More generally, we think the following statement is true.


A simplex is diameter-Ramsey if and only if its circumcentre is contained in its convex hull.


Furthermore, it would be interesting to close the gap between <ref> and the related result from <cit.>.


For every d ∈, determine the largest = (d) >0, such that every -almost-regular simplex is diameter-Ramsey.


Note that, provided <ref> is true, a similar construction as in the proof of <ref> shows that the result in <cit.> is best possible, i.e. (d) = 1/d2.



§ ACKNOWLEDGEMENT

The authors would like to thank their supervisors Peter Allen, Julia Böttcher, Jozef Skokan and Konrad Swanepoel for their helpful comments on this note.

amsplain

