\documentclass[12pt]{article}
\usepackage{amsmath,mathrsfs,bbm}
\usepackage{amssymb}
\textwidth=4.825in
\overfullrule=0pt
\thispagestyle{empty}
\begin{document}
\noindent
%
%
{\bf Jaros\l aw Grytczuk, Jakub Kozik and Marcin Witkowski}
%
%
\medskip
\noindent
%
%
{\bf Nonrepetitive Sequences on Arithmetic Progressions}
%
%
\vskip 5mm
\noindent
%
%
%
%
A sequence $S=s_{1}s_{2}\ldots s_{n}$ is said to be \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$, 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\'{a}sz Local Lemma due to Moser and Tardos. We also discuss some related problems that can be attacked by this method.
\end{document}