An Assortment of Euclidean Coloring Problems

An Assortment of Euclidean Coloring Problems ) Introduction Euclidean Coloring problems (also known as Euclidean Ramsey theory) concerns colorings of Euclidean space such that certain geometric conditions are met. Perhaps the most famous of such problems is the Hadwiger-Nelson problem, which asks for the smallest integer 𝑘 such that there exists a 𝑘-coloring of ℝ! (and in general ℝ" ) forbidding monochromatic unit distances (this number we denote as χ ℝ" ) [1]. At the discovery of the problem in 1950 a lower bound of 4 and an upper bound of 7 were established. Little progress was made until 2018 when Aubrey de Grey published a computer-generated graph of 1581 vertices with chromatic number 5, where all the edges were unit distances, thus pushing the lower bound up to 5 [2]. Most of our research revolved around this problem or problems of this type. For = 3, < 3: 𝒏 𝒌 For 𝒏 = 4, 𝒌 < 2: Consider the following coloring, where Consider the following coloring, circles are colored alternatingly in the 3 where circles that are packed different colors and packed so that hexagonally are colored alternatingly circles of the same color are unit distance in the 4 different colors. The coloring apart. The coloring forbids the 3-point forbids the 2-point set as shown set as shown below. below. In 1999 Arthur Szlam proved the following [3]: Lemma (Szlam’s lemma) Given a coloring of ℝ# with red and blue such that blue forbids unit distance, and an integer 𝑘 < χ ℝ# , the coloring does not forbid any 𝑘point set. In particular for ℝ! , this leads to a lower bound that for 𝑛 = 1, 𝑘 ≥ 5. We present the following generalization of the above lemma: Theorem Given a coloring of ℝ# with red and 𝑛 colors such that the 𝑛 colors each forbid unit distance, and an integer 𝑘 such that 𝑛𝑘 < χ ℝ# , the coloring does not forbid any 𝑘-point set. In ℝ! , this gives us the lower bound that for 𝑛 = 2, 𝑘 ≥ 3. On a side note, the converse of this theorem gives us a novel way to approach the chromatic number of ℝ# : if we can find a coloring of ℝ# with 𝑛 colors such that a 𝑘-point set is forbidden, then we know that the chromatic number of χ ℝ# ≤ 𝑛𝑘. Some of the upper bounds for ℝ! are as follows: This is proven by showing that there must exist an -ball containing 4 ! different colors, and then taking the unit sphere around this ball, which itself must be colored by 6 different colors. Given that the current known bounds are 6 ≤ χ ℝ- ≤ 15, we know that any coloring using 6, 7, 8, or 9 colors cannot forbid an interval of distances. Conjecture χ( ℝ " ≥ "&% " ! . In addition, χ)*+, ℝ " ≥ "&% " ! . While we have an intuitive idea of how we might prove this conjecture, there are some difficulties with working with higher dimensions that we have not been able to figure out. We consider the following problem: Given a coloring of 𝐽-dimensional Euclidean space ℝ , we say the coloring forbids unit distance for color 𝑐$ if for any two points 𝑣% , 𝑣! ∈ ℝ# with color 𝑐$ , 𝑣% and 𝑣! are not a unit distance apart. Given a coloring of ℝ# , we say the coloring forbids a 𝑘-point set if there does not exist a translate of the 𝑘-point set in ℝ# such that all the points are red. For each 𝑛 ∈ ℤ& , 𝐽 ≥ 2, what is the largest 𝑘 ∈ ℤ& such that for any coloring of ℝ# with 𝑛 colors and the color red, and for any 𝑘-point set {𝑣% , 𝑣! , … , 𝑣' } ∈ ℝ# the coloring does not forbid the 𝑘-point set? ( Generalizing the above two theorems we have the following conjecture: A Generalization of Szlam’s Lemma # Theorem χ( ℝ- ≥ 10. In addition, χ)*+, ℝ- ≥ 10. Further research in this area can include tighten our current bounds, and considering colorings that forbid congruent copies of 𝑘-point sets, instead of translates. Epsilon Colorings We next considered the following problem: What happens to the Hadwiger-Nelson problem if instead of forbidding unit distance, we forbid an interval of distances 1 − 𝜖, 1 + 𝜖 , for some 𝜖 > 0? We define this type of coloring as 𝜖 -colorings, and we denote the associated chromatic number to be χ( ℝ# . In ℝ! , the upper bound of 7 still holds, as the 7-coloring that forbids unit distance also forbids an interval of distances. We proved the following theorem: Theorem χ( ℝ! ≥6. In particular, this means that for any 5 coloring of the plane, it cannot forbid any interval of distances. We define an open-set coloring to be a coloring of ℝ# such that each color set is open, and we denote the associated chromatic number to be χ)*+, ℝ# . This notion has been explored in papers such as [4]. It turns out that 𝜖-colorings have a close relation to open-set colorings: Theorem χ( ℝ# ≥ χ)*+, ℝ# . Moreover: χ)*+, ℝ# ≥ χ( (𝐾), where 𝐾 ⊂ ℝ# is any compact subset. Finally, we looked at what happens in higher-dimensional Euclidean space. Further Research A new research problem under consideration is as follows: Given a 𝑘-point set {𝑣% , 𝑣! , … , 𝑣' } ∈ ℝ" , a subset 𝐴 of ℝ" is colored red such that the coloring forbids the 𝑘-point set. Defining a notion of the size of a subset relative to ℝ" known as upper density, what is the maximum upper density of 𝐴? What about colorings that forbid congruent copies of 𝑘-point sets? References [1]: Soifer A. (2016) The Hadwiger–Nelson Problem. In: Nash, Jr. J., Rassias M. (eds) Open Problems in Mathematics. Springer, Cham. [2]: de Grey, Aubrey D.N.J. (2018), "The Chromatic Number of the Plane Is at least 5", Geombinatorics, 28: 5–18 [3]: PD Johnson Jr and AD Szlam (2001), “A new connection between two kinds of Euclidean coloring problems”, Geombinatorics, 10: 172–178. [4]: N. Brown, N. Dunfield and G. Perry (1993), “Colorings of the plane I”, Geombinatorics, 3: 24–31.