Nonrepetitive colorings of $R^d$ - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2023

Nonrepetitive colorings of $R^d$

Abstract

The results of Thue state that there exists an infinite sequence over 3 symbols without 2 identical adjacent blocks, which we call a 2-nonrepetitive sequence, and also that there exists an infinite sequence over 2 symbols without 3 identical adjacent blocks, which is a 3-nonrepetitive sequence. An $r$-repetition is defined as a sequence of symbols consisting of $r$ identical adjacent blocks, and a sequence is said to be $r$-nonrepetitive if none of its subsequences are r-repetitions. Here, we study colorings of Euclidean spaces related to the work of Thue. A coloring of $R^d$ is said to be $r$- nonrepetitive of no sequence of colors derived from a set of collinear points at distance 1 is an $r$-repetition. In this case, the coloring is said to avoid r-repetitions. It was proved in [9] that there exists a coloring of the plane that avoids 2-repetitions using 18 colors, and conversely, it was proved in [3] that there exists a coloring of the plane that avoids 43-repetitions using only 2 colors. We specifically study $r$-nonrepetitive colorings for fixed number of colors : for a fixed number of colors k and dimension d, the aim is to determine the minimum multiplicity of repetition $r$ such that there exists an r-nonrepetitive coloring of $R^d$ using $k$ colors. We prove that the plane, $R^2$, admits a 2- and a 3-coloring avoiding 33- and 18- repetitions, respectively.
Fichier principal
Vignette du fichier
35550-Article Text-58940-1-10-20230714.pdf (360.34 Ko) Télécharger le fichier

Dates and versions

lirmm-04308803 , version 1 (27-11-2023)

Licence

Identifiers

Cite

Kathleen Barsse, Daniel Gonçalves, Matthieu Rosenfeld. Nonrepetitive colorings of $R^d$. Eurocom 2023 - 12th European Conference on Combinatorics, Graph Theory and Applications, Aug 2023, Prague, Czech Republic. pp.114-119, ⟨10.5817/CZ.MUNI.EUROCOMB23-016⟩. ⟨lirmm-04308803⟩
30 View
30 Download

Altmetric

Share

More