Nonrepetitive sequences on arithmetic progressions

Details Nonrepetitive sequences on arithmetic progressions Nonrepetitive sequences on arithmetic progressions

2011-02-26

arxiv.org/abs/1102.5438v2

Mathematics

Combinatorics

Scientific paper

A sequence $S=s_{1}s_{2}..._{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 $k\geqslant 1$ and every $c\geqslant 1$ there exist arbitrarily long sequences over at most $(1+\frac{1}{c})k+18k^{c/c+1}$ symbols whose subsequences indexed by arithmetic progressions with common differences from the set $\{1,2,...,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.

Affiliated with

Also associated with

No associations

Rating

Nonrepetitive sequences on arithmetic progressions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Nonrepetitive sequences on arithmetic progressions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nonrepetitive sequences on arithmetic progressions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-303283