Nonrepetitive colorings of Rd

EUROCOMB’23

Kathleen Barsse Daniel Gonçalves Matthieu Rosenfeld

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-016

PDF
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 $\mathbb{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 \cite{NonrepetitivePlanOG} that there exists a coloring of the plane that avoids 2-repetitions using 18 colors, and conversely, it was proved in \cite{GrytczuckEtAlMain} 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 $\mathbb{R}^d$ using $k$ colors. We prove that the plane, $\mathbb{R}^2$, admits a 2- and a 3-coloring avoiding 33- and 18-repetitions, respectively.

Pages:
114–119
References

P. Brass, W. Moser, and J. Pach. Research Problems in Discrete Geometry. Springer, New York, 2005.

A. de Grey. The chromatic number of the plane is at least 5. Geombinatorics, 28:18-31, 2018.

M. Dębski, J. Grytczuk, B. Nayar, U. Pastwa, J. Sokół, M. Tuczyński, P. Wenus, and K. Węsek. Avoiding multiple repetitions in euclidean spaces. SIAM Journal on Discrete Mathematics, 34(1):40-52, 2020.
https://doi.org/10.1137/18M1180347

M. Dębski, U. Pastwa, and K. Węsek. Grasshopper avoidance of patterns. Electron. J. Combin., 23:1-16, 2016.
https://doi.org/10.37236/6210

J. Grytczuk, K. Kosiński, and M. Zmarz. Nonrepetitive colorings of line arrangements. European Journal of Combinatorics, 51:275-279, 2016.
https://doi.org/10.1016/j.ejc.2015.05.013

M. Rosenfeld. Another approach to non-repetitive colorings of graphs of bounded degree. Electronic Journal of Combinatorics, 27(3), 2020.
https://doi.org/10.37236/9667

A. Soifer. The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators. Springer, New York, 2008.
https://doi.org/10.1007/978-0-387-74642-5

I. M. Wanless and D. R. Wood. A general framework for hypergraph coloring. SIAM Journal on Discrete Mathematics, 36(3):1663-1677, 2022.
https://doi.org/10.1137/21M1421015

P. Wenus and K. Węsek. Nonrepetitive and pattern-free colorings of the plane. European Journal of Combinatorics, 54:21-34, 2016.
https://doi.org/10.1016/j.ejc.2015.12.002

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Kathleen Barsse, Daniel Gonçalves, Matthieu Rosenfeld

PDF