Nonrepetitive sequences on arithmetic progressions (Q648401): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 01:52, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Nonrepetitive sequences on arithmetic progressions |
scientific article |
Statements
Nonrepetitive sequences on arithmetic progressions (English)
0 references
22 November 2011
0 references
Summary: A sequence \(S=s_1s_2\dots s_n\) is said to be nonrepetitive if no two adjacent blocks of \(S\) are identical. In 1906, \textit{A. Thue} [Christiania Vidensk.-Selsk. Skr. 1906, Nr. 7, 22 S. (1906; JFM 39.0283.01)] proved that there exist arbitrarily long nonrepetitive sequences over a 3-element set of symbols. We study a generalization of nonrepetitive sequences involving arithmetic progressions. We prove that for every \(k\geq 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,\dots,k\}\), are nonrepetitive. This improves a previous bound of \(e^{33}k\) obtained by the first author. Our approach is based on a technique introduced recently by the first two authors and \textit{P. Micek} [``A new approach to nonrepetitive sequences'' (submitted), \url{arXiv:1103.3809}] which was originally inspired by a constructive proof of the Lovász local lemma due to \textit{R. A. Moser} and \textit{G. Tardos} [``A constructive proof of the general Lovász local lemma'', J. ACM 57, No. 2, Art. No. 11, 15 p. (2010), \url{arXiv:0903.0544}]. We also discuss some related problems that can be attacked by this method.
0 references