Nonrepetitive and pattern-free colorings of the plane

Przemysław Wenus , Krzysztof Węsek

Abstract

A classic result of Thue states that using 3 symbols one can construct an infinite nonrepetitive sequence, that is, a sequence without two identical adjacent blocks. In this paper, we present Thue-type results concerning coloring of the Euclidean plane, related to the famous Hadwiger–Nelson problem. This old problem asks for the chromatic number of the unit distance graph of the plane, the infinite graph with the set of vertices of R2 and edges between points at distance 1. We solve a problem posed by Grytczuk (2008) by showing that any coloring of the unit distance graph of R2 in which the sequence of colors of every simple path is nonrepetitive needs more than countable number of colors. Grytczuk, Kosiński and Zmarz (2016) introduced a relaxation of this problem, by restricting the nonrepetitiveness condition to a certain class of paths. Let a path in the unit distance graph of R2 be called line path if it consists of collinear points. A coloring of R2 is line nonrepetitive if the sequence of colors on every line path is nonrepetitive. We present a line nonrepetitive 18-coloring of R2, which improves the result of Grytczuk, Kosiński and Zmarz with 36 colors. Furthermore, we construct a line nonrepetitive coloring, which additionally avoids palindromes and uses 32 colors. We also consider a natural generalization of this problem to other patterns. We say that a pattern q (finite sequence over a set of variables E) occurs in a sequence w (over an alphabet A) if there exists a substitution f from E to the set of nonempty sequences over A such that f(q) is a block in w. A sequence w avoids a pattern q if q does not occur in w. For a pattern q, a coloring of R2 is called line p-free if the sequence of colors on every line path avoids q. We present a 9-coloring of R2 which is line ααα-free and line αβαβ-free at once. Moreover, we give a non-constructive result for a class of patterns. Namely, let q be a pattern with no variable occurring exactly once or satisfying ℓ⩾2d, where ℓ is the length of q and d is the number of variables in q. Then there exists a line q-free coloring of R2 using a finite number of colors. In fact, this result holds even if (instead of taking into account only line paths) we consider all sequences of points in R2 with consecutive distances in some fixed interval [a,b] and without any pair of vertices at distance smaller than a fixed ε>0.
Author Przemysław Wenus WMiNI
Przemysław Wenus,,
- Faculty of Mathematics and Information Science
, Krzysztof Węsek WMiNI
Krzysztof Węsek,,
- Faculty of Mathematics and Information Science
Journal seriesEuropean Journal of Combinatorics, ISSN 0195-6698
Issue year2016
Vol54
Pages21-34
Publication size in sheets0.65
Keywords in Englishnonrepetitive sequence, avoidable pattern, palindrome, coloring of the plane
Abstract in PolishKlasyczny wynik A. Thuego mówi, że 3 symbole wystarczą by zbudować ciąg o dowolnej długości unikający repetycji, tj. dwóch identycznych bloków jakiejkolwiek długości obok siebie. Praca dotyczy połączenia problemów w duchu Thuego z problemami związanymi z klasycznym problemem Hadwigera-Nelsona. Problem ten pyta o liczbę chromatyczną nieskończonego grafu jednostkowego płaszczyzny, w którym wierzchołkami są wszystkie punkty płaszczyzny, a dwa punkty łączy krawędź, gdy są w odległości dokładnie 1. W niniejszej publikacji odpowiadamy na pytanie J. Grytczuka (2008) poprzez pokazanie, że każdego kolorowanie R^2, takie że ciąg kolorów na każdej ścieżce unika repetycji, wymaga więcej niż przeliczalnej liczby kolorów. Grytczuk, Kosiński i Zmarz (2016) wprowadzili uproszczenie tego problemu w postaci rozważania tylko ścieżek liniowych, tj, ciągów różnych punktów współliniowych o kolejnych odległościach 1. W sposób konstruktywny pokazujemy, że 18 kolorów wystarczy, by pokolorować R^2 w sposób unikający repetycji na ścieżkach liniowych - co poprawia wynik Grytczuka, Kosińskiego i Zmarza (36 kolorów). Dodatkowo, prezentujemy 32-kolorowanie unikające na ścieżkach liniowych jednocześnie repetycji i palindromów. W dalszej części pracy badamy również inne wzorce (czyli skończonych ciągów zmiennych). Mówimy, że wzorzec p występuje w ciągu a, gdy istnieje podstawienie f ze zbioru zmiennych wzorca p w zbiór niepustych ciągów nad alfabetem ciągu a, takie że f(p) jest blokiem w a. Dla wzorca p mówimy, że kolorowanie jest liniowo p-wolne, jeśli ciąg kolorów żadnej ścieżki liniowej nie zawiera p. Prezentujemy 9-kolorowanie płaszczyzny, które jest jednocześnie liniowo xx-wolne i liniowo xyxy-wolne. Co więcej, w niekonstruktywny sposób udowadniamy dla całej klasy wzorców, że dla każdego wzorca p z tej klasy istnieje kolorowanie liniowo p-wolne używające skończonej liczby kolorów. Ten wynik jest prawdziwy również w przypadku, gdy dopuścimy możliwość (ograniczonego) “skręcania” ścieżki i wykonywania kroków o długości z zadanego przedziału [a,b].
DOIDOI:10.1016/j.ejc.2015.12.002
URL http://www.sciencedirect.com/science/article/pii/S0195669815002668
Languageen angielski
Score (nominal)30
ScoreMinisterial score = 25.0, 28-11-2017, ArticleFromJournal
Ministerial score (2013-2016) = 30.0, 28-11-2017, ArticleFromJournal
Publication indicators WoS Impact Factor: 2016 = 0.786 (2) - 2016=0.828 (5)
Citation count*0 (2016-06-23)
Cite
Share Share



* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back