2011/02/26 by Grytczuk, Jarosław, Kozik, Jakub, Witkowski, Marcin
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT)
paper · doi:10.48550/arxiv.1102.5438
A sequence S=s1s2...n is 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+(1)/(c))k+18kc/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 \citeGrytczuk Rainbow. Our approach is based on a technique introduced recently in \citeGrytczukKozikMicek, which was originally inspired by a constructive proof of the Lovász Local Lemma due to Moser and Tardos \citeMoserTardos. We also discuss some related problems that can be successfully attacked by this method.