Ann wins the nonrepetitive game over four letters and the erase-repetition game over six letters

DOI10.1016/J.EJC.2024.103924arXiv2107.14022OpenAlexW3187028950WikidataQ129667523 ScholiaQ129667523MaRDI QIDQ6201902FDOQ6201902

Authors: Matthieu Rosenfeld 

Publication date: 26 March 2024

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: We consider two games between two players Ann and Ben who build a word together by adding alternatively a letter at the end of the shared word. In the nonrepetitive game, Ben wins the game if he can create a square of length at least $4$, and Ann wins if she can build an arbitrarily long word before that. In the erase-repetition game, whenever a square occurs the second part of the square is erased and the goal of Ann is still to build an arbitrarily large word (Ben simply wants to limit the size of the word in this game). Grytczuk, Kozik, and Micek showed that Ann has a winning strategy for the nonrepetitive game if the alphabet is of size at least $6$ and for the erase-repetition game is the alphabet is of size at least $8$. In this article, we lower these bounds to respectively $4$ and $6$. The bound obtain by Grytczuk et al. relied on the so-called entropy compression and the previous bound by Pegden relied on some particular version of the Lov'asz Local Lemma. We recently introduced a counting argument that can be applied to the same set of problems as entropy compression or the Lov'asz Local Lemma and we use our method here. For these two games, we know that Ben has a winning strategy when the alphabet is of size at most 3, so our result for the nonrepetitive game is optimal, but we are not able to close the gap for the erase-repetition game.

Full work available at URL: https://arxiv.org/abs/2107.14022

Recommendations

• A note on Thue games
• New approach to nonrepetitive sequences
• How to play Thue games
• Highly nonrepetitive sequences: winning strategies from the local Lemma
• Online version of the theorem of Thue

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx) Game theory (91Axx) Graph theory (05Cxx)

Cites Work

• New approach to nonrepetitive sequences
• Two-Sided Bounds for the Growth Rates of Power-Free Languages
• A constructive proof of the general Lovász local lemma
• Highly nonrepetitive sequences: winning strategies from the local Lemma
• Another approach to non-repetitive colorings of graphs of bounded degree
• Avoiding squares over words with lists of size three amongst four symbols

This page was built for publication: Ann wins the nonrepetitive game over four letters and the erase-repetition game over six letters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6201902)