A new approach to nonrepetitive sequences

Jarosław Grytczuk, Jakub Kozik, Piotr Micek

Published 2011-03-19, updated 2011-11-22Version 2

A sequence is nonrepetitive if it does not contain two adjacent identical blocks. The remarkable construction of Thue asserts that 3 symbols are enough to build an arbitrarily long nonrepetitive sequence. It is still not settled whether the following extension holds: for every sequence of 3-element sets $L_1,..., L_n$ there exists a nonrepetitive sequence $s_1, ..., s_n$ with $s_i\in L_i$. Applying the probabilistic method one can prove that this is true for sufficiently large sets $L_i$. We present an elementary proof that sets of size 4 suffice (confirming the best known bound). The argument is a simple counting with Catalan numbers involved. Our approach is inspired by a new algorithmic proof of the Lov\'{a}sz Local Lemma due to Moser and Tardos and its interpretations by Fortnow and Tao. The presented method has further applications to nonrepetitive games and nonrepetitive colorings of graphs.