TL;DR: This is an informal summary of our recent paper Extending the Continuum of Six-Colorings by Konrad Mundinger, Sebastian Pokutta, Christoph Spiegel, and Max Zimmer. We present two novel six-colorings of the Euclidean plane that avoid monochromatic pairs of points at unit distance in five colors and monochromatic pairs at another specified distance in the sixth color. Our results significantly expand the known range for these colorings, representing the first improvement in 30 years. The constructions were derived using a custom machine learning approach.

### Introduction

The Hadwiger-Nelson problem asks for the smallest number of colors needed to color the points of the Euclidean plane so that no two points at unit distance have the same color. This number is also known as the chromatic number of the plane, denoted by $\chi(E_2)$. The chromatic number of the plane has a lower bound of $5$, as established by de Grey in 2018 (see [DG] and also [EI, H]). The upper bound has remained at $7$ since the first seven-coloring was observed in 1950. Various six-colorings have been proposed, but the range of valid distances for the sixth color has been limited. The problem, which dates back to 1950 (see e.g., [dBE]), has remained one of the most famous open problems in combinatorial geometry and graph theory.

Recent advancements have been made by extending the range of distances that can be used in six-colorings of the plane, avoiding monochromatic pairs at both unit distance for the first five colors and another specified distance $$d$$ for the sixth color. Previous work established that such colorings existed for distances within a specific but relatively small range of $$0.414 \approx \sqrt{2} - 1 \leq d \leq 1/\sqrt{5} \approx 0.447$$ (see [HS1, HS2, S] and the references contained therein for a complete overview). Our results significantly broaden this range to $$0.354 \leq d \leq 0.657$$ via two novel six-colorings derived from a machine learning approach, which we coined deep annealing. Most notably, the obtained colorings are somewhat “unexpected” as they are rather irregular compared to previously found colorings. For more information also see my [slides].

### Our Contributions

We introduce two novel six-colorings that expand the known range of distances significantly:

1. A six-coloring valid for $$0.354 \leq d \leq 0.553$$.
2. A six-coloring valid for $$0.418 \leq d \leq 0.657$$.

These constructions were derived using a custom machine learning approach, where a neural network was trained to represent colorings of a specified type, allowing us to explore and formalize new colorings efficiently.

#### Coloring 1 for $$0.354 \leq d \leq 0.553$$

This construction involves four different polytopal shapes:

• Equidiagonal pentagons
• Equilateral triangles
• Octagons
• Hexagons

These shapes are colored in a specific pattern to avoid monochromatic pairs at both unit distance and the specified distance $$d$$. The exact parameters and shapes are described in detail in our paper [MPSZ].

Figure 1. Illustration of the first coloring with circles at unit distance (dotted) and distance (d) (dashed) highlighted at three critical points.

Figure 2. Building blocks of first coloring.

#### Coloring 2 for $$0.418 \leq d \leq 0.657$$

This construction also uses four polytopal shapes:

• Axisymmetric pentagons
• Squares
• Heptagons
• Hexagons

Similar to the first construction, these shapes are arranged and colored to avoid monochromatic pairs at the specified distances.

Figure 3. Illustration of the second coloring with circles at unit distance (dotted), and distance $$d_{\text{max}}$$ (dashed), and distance $$d_{\text{min}}$$ (dash-dotted) highlighted at six critical points.

Figure 4. Building blocks of second coloring.

#### Conflicts vs. distance

A natural question to ask is whether we left something on the table with our approach. Below is a plot where we measure the (minimum) fraction of conflicts vs. the distance in the sixth color obtained over a large number of deep annealing runs. As you can see we basically cover the full spectrum with exact constructions for which we found a coloring candidate with no conflicts.

Figure 5. Fraction of conflicts vs. distance in the sixth color over a large number of deep annealing runs. The dark blue regime is the interval known before our work.

### References

(for a more complete list, see our paper [MPSZ] and the references contained therein)

[MPSZ] Mundinger, K., Pokutta, S., Spiegel, C., Zimmer, M.: Extending the Continuum of Six-Colorings. Geombinatorics Quaterly (see also arXiv preprint arXiv:2404.05509) (2024)

[dBE] de Bruijn, N.G., Erdős, P.: A colour problem for infinite graphs and a problem in the theory of relations. Indigationes Mathematicae 13, 371–373 (1951)

[DG] De Grey, A.D.: The chromatic number of the plane is at least 5. Geombinatorics Quarterly XXVIII(1), 18–31 (2018)

[EI] Exoo, G., Ismailescu, D.: The chromatic number of the plane is at least 5: a new proof. Discrete & Computational Geometry 64(1), 216–226 (2020)

[H] Heule, M.J.: Computing small unit-distance graphs with chromatic number 5. Geombinatorics Quarterly XXVIII(1), 32–50 (2018)

[HS1] Hoffman, I., Soifer, A.: Almost chromatic number of the plane. Geombinatorics 3(2), 38–40 (1993)

[HS2] Hoffman, I., Soifer, A.: Another six-coloring of the plane. Discrete Mathematics 150(1-3), 427–429 (1996)

[S] Soifer, A.: The mathematical coloring book: Mathematics of coloring and the colorful life of its creators. Springer (2009)