go-v.orgdoi

Nonrepetitive Sequences on Arithmetic Progressions

Jarosław Grytczuk, Jakub Kozik, Marcin Witkowski · The Electronic Journal of Combinatorics · 2011

  • DOI 10.37236/696
  • Publisher Electronic Journal of Combinatorics
  • Type article
  • Issued 2011

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2011

Abstract

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.

Open the resolved locator · 10.37236/696

Metadata licence: OpenAlex metadata (CC0)