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.