New approach to nonrepetitive sequences. Issue 2 (29th February 2012)

• Record Type: Journal Article
• Authors: Grytczuk, Jarosław; Kozik, Jakub; Micek, Piotr
• Is Part Of: Random structures & algorithms. Volume 42:Issue 2(2013)
• Page Start: 214
• Page End: 225
• Publication Date: 2012-02-29
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20411
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>A sequence is <italic>nonrepetitive</italic> if it does not contain two adjacent identical blocks. The remarkable construction of Thue asserts that three symbols are enough to build an arbitrarily long nonrepetitive sequence. It is still not settled whether the following extension holds: for every sequence of three‐element sets <italic>L</italic><sub>1</sub>, …, <italic>L</italic><sub><italic>n</italic></sub> there exists a nonrepetitive sequence <italic>s</italic><sub>1</sub>, …, <italic>s</italic><sub><italic>n</italic></sub> with <italic>s</italic><sub><italic>i</italic></sub>∈<italic>L</italic><sub><italic>i</italic></sub>. We propose a new non‐constructive way to build long nonrepetitive sequences and provide an elementary proof that sets of size 4 suffice confirming the best known bound. The simple double counting in the heart of the argument is inspired by the recent algorithmic proof of the Lovász local lemma due to Moser and Tardos. Furthermore we apply this approach and present game‐theoretic type results on nonrepetitive sequences. <italic>Nonrepetitive game</italic> is played by two players who pick, one by one, consecutive terms of a sequence over a given set of symbols. The first player tries to avoid repetitions, while the second player, in contrast, wants to create them. Of course, by simple imitation, the second player can force lots of repetitions of size 1. However, as proved by Pegden, there is a strategy for the first player to build an arbitrarily long sequence over 37 symbols with no repetitions of size greater than 1. Our techniques allow to reduce 37–6. Another game we consider is the <italic>erase‐repetition game</italic>. Here, whenever a repetition occurs, the repeated block is immediately erased and the next player to move continues the play. We prove that there is a strategy for the first player to build an arbitrarily long nonrepetitive sequence over 8 symbols. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012</p> </abstract>