Nonrepetitive sequences on arithmetic progressions

MaRDI QIDQ648401zbMATHFDO

Authors Jarosław Grytczuk, Jakub Kozik, Marcin Witkowski

Publication date 22 November 2011

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1102.5438

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Combinatorics on words (68R15) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Arithmetic progressions (11B25)

Abstract: A sequence $S=s_1{s}_2\mathrm{..}{.}_n$ is emph{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 $kgeqslant1$ and every $cgeqslant1$ there exist arbitrarily long sequences over at most $(1+frac1c)k+18k^{c/c+1}$ symbols whose subsequences indexed by arithmetic progressions with common differences from the set $1,2,\mathrm{...},k$ are nonrepetitive. This improves a previous bound obtained in cite{Grytczuk Rainbow}. Our approach is based on a technique introduced recently in cite{GrytczukKozikMicek}, which was originally inspired by a constructive proof of the Lov'{a}sz Local Lemma due to Moser and Tardos cite{MoserTardos}. We also discuss some related problems that can be successfully attacked by this method.

Recommendations

• New approach to nonrepetitive sequences
• On non-repetitive sequences of arithmetic progressions: the cases \(k\in\{4,5,6,7,8\}\)
• Thue-like sequences and rainbow arithmetic progressions
• Nonrepetitive colorings of graphs
• Thue type problems for graphs, points, and numbers

Cited in

(13)

• Fractional meanings of nonrepetitiveness
• On a generalization of Thue sequences
• Generating square-free words efficiently
• Avoiding Multiple Repetitions in Euclidean Spaces
• The reverse mathematics of non-decreasing subsequences
• scientific article; zbMATH DE number 3904598 (Why is no real title available?)
• On avoding \(r\)-repetitions in \(\mathbb R^2\)
• On non-repetitive sequences of arithmetic progressions: the cases \(k\in\{4,5,6,7,8\}\)
• Thue-like sequences and rainbow arithmetic progressions
• Highly nonrepetitive sequences: winning strategies from the local Lemma
• scientific article; zbMATH DE number 5528974 (Why is no real title available?)
• New approach to nonrepetitive sequences
• Nonrepetitive and pattern-free colorings of the plane

This page was built for publication: Nonrepetitive sequences on arithmetic progressions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q648401)