Avoiding Multiple Repetitions in Euclidean Spaces

Logo poskytovatele

Varování

Publikace nespadá pod Pedagogickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

DĘBSKI Michał Karol GRYTCZUK Jarosław NAYAR Barbara PASTWA Urszula SOKÓŁ Joanna TUCZYŃSKI Michał WENUS Przemysław WE?SEK Krzysztof

Rok publikování 2020
Druh Článek v odborném periodiku
Časopis / Zdroj SIAM Journal on Discrete Mathematics
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www https://doi.org/10.1137/18M1180347
Doi http://dx.doi.org/10.1137/18M1180347
Klíčová slova nonrepetitive sequence; pattern avoidance; Euclidean Ramsey theory; Lovász Local Lemma
Popis We study colorings of Euclidean spaces avoiding specified patterns on straight lines. This extends the seminal work of Thue on avoidability properties of sequences to continuous, higher dimensional structures. We prove that every space R^d has a 2-coloring such that no sequence of colors derived from collinear points separated by unit distance consists of more than r(d) identical blocks. In case of the plane we show that r(2) <= 43. We also consider more general patterns and give a sufficient condition for a pattern to be avoided in the plane. This supports a general Pattern Avoidance Conjecture in Euclidean spaces. The proofs are based mainly on the probabilistic method, but additional tools are forced by the geometric nature of the problem. We also consider similar questions for general geometric graphs in the plane. In the conclusion of the paper, we pose several conjectures alluding to some famous open problems in Euclidean Ramsey Theory.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.