Nonrepetitive games

Details Nonrepetitive games Nonrepetitive games

2011-03-19

arxiv.org/abs/1103.3810v2

Mathematics

Combinatorics

8 pages, no figures

Scientific paper

(Note. The results of this manuscript has been merged and published with another paper of the same authors: A new approach to nonrepetitve sequences.) A repetition of size $h$ ($h\geqslant1$) in a given sequence is a subsequence of consecutive terms of the form: $xx=x_1... x_hx_1... x_h$. A sequence is nonrepetitive if it does not contain a repetition of any size. The remarkable construction of Thue asserts that 3 different symbols are enough to build an arbitrarily long nonrepetitive sequence. We consider game-theoretic versions of results on nonrepetitive sequences. A nonrepetitive game 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 $>1$. Our techniques allow to reduce 37 to 6. Another game we consider is an erase-repetition game. 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. Our approach is inspired by a new algorithmic proof of the Lov\'asz Local Lemma due to Moser and Tardos and previous work of Moser (his so called entropy compression argument).

Affiliated with

Also associated with

No associations

Rating

Nonrepetitive games 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 games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nonrepetitive games will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-695111