Nonrepetitive sequences on arithmetic progressions
The electronic journal of combinatorics, Tome 18 (2011) no. 1
A sequence $S=s_{1}s_{2}\ldots s_{n}$ is said to be nonrepetitive if no two adjacent blocks of $S$ are identical. In 1906 Thue proved that there exist arbitrarily long nonrepetitive sequences over $3$-element set of symbols. We study a generalization of nonrepetitive sequences involving arithmetic progressions. We prove that for every $k\geqslant 1$, there exist arbitrarily long sequences over at most $2k+10 \sqrt{k}$ symbols whose subsequences, indexed by arithmetic progressions with common differences from the set $\{1,2,\ldots ,k\}$, are nonrepetitive. This improves a previous bound of $e^{33}k$ obtained by Grytczuk. Our approach is based on a technique introduced recently by Grytczuk Kozik and Micek, which was originally inspired by a constructive proof of the Lovász Local Lemma due to Moser and Tardos. We also discuss some related problems that can be attacked by this method.
@article{10_37236_696,
author = {Jaros{\l}aw Grytczuk and Jakub Kozik and Marcin Witkowski},
title = {Nonrepetitive sequences on arithmetic progressions},
journal = {The electronic journal of combinatorics},
year = {2011},
volume = {18},
number = {1},
doi = {10.37236/696},
zbl = {1229.68063},
url = {http://geodesic.mathdoc.fr/articles/10.37236/696/}
}
Jarosław Grytczuk; Jakub Kozik; Marcin Witkowski. Nonrepetitive sequences on arithmetic progressions. The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/696
Cité par Sources :