| DĘBSKI, Michał Karol, Jarosław GRYTCZUK, Barbara NAYAR, Urszula PASTWA, Joanna SOKÓŁ, Michał TUCZYŃSKI, Przemysław WENUS a Krzysztof WEΙSEK. Avoiding Multiple Repetitions in Euclidean Spaces. SIAM Journal on Discrete Mathematics. Philadelphia: SIAM, 2020, roč. 34, č. 1, s. 40-52. ISSN 0895-4801. Dostupné z: https://dx.doi.org/10.1137/18M1180347. |
Další formáty:
BibTeX
LaTeX
RIS
@article{1645736,
author = {Dębski, Michał Karol and Grytczuk, Jarosław and Nayar, Barbara and Pastwa, Urszula and Sokół, Joanna and Tuczyński, Michał and Wenus, Przemysław and Weͅsek, Krzysztof},
article_location = {Philadelphia},
article_number = {1},
doi = {http://dx.doi.org/10.1137/18M1180347},
keywords = {nonrepetitive sequence; pattern avoidance; Euclidean Ramsey theory; Lovász Local Lemma},
language = {eng},
issn = {0895-4801},
journal = {SIAM Journal on Discrete Mathematics},
title = {Avoiding Multiple Repetitions in Euclidean Spaces},
url = {https://doi.org/10.1137/18M1180347},
volume = {34},
year = {2020}
}
TY - JOUR
ID - 1645736
AU - Dębski, Michał Karol - Grytczuk, Jarosław - Nayar, Barbara - Pastwa, Urszula - Sokół, Joanna - Tuczyński, Michał - Wenus, Przemysław - Weͅsek, Krzysztof
PY - 2020
TI - Avoiding Multiple Repetitions in Euclidean Spaces
JF - SIAM Journal on Discrete Mathematics
VL - 34
IS - 1
SP - 40-52
EP - 40-52
PB - SIAM
SN - 08954801
KW - nonrepetitive sequence
KW - pattern avoidance
KW - Euclidean Ramsey theory
KW - Lovász Local Lemma
UR - https://doi.org/10.1137/18M1180347
L2 - https://doi.org/10.1137/18M1180347
N2 - 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.
ER -
DĘBSKI, Michał Karol, Jarosław GRYTCZUK, Barbara NAYAR, Urszula PASTWA, Joanna SOKÓŁ, Michał TUCZY$\backslash$'NSKI, Przemysław WENUS a Krzysztof WEΙSEK. Avoiding Multiple Repetitions in Euclidean Spaces. \textit{SIAM Journal on Discrete Mathematics}. Philadelphia: SIAM, 2020, roč.~34, č.~1, s.~40-52. ISSN~0895-4801. Dostupné z: https://dx.doi.org/10.1137/18M1180347.
|
