Avoiding large squares in partial words

Well-known results on the avoidance of large squares in (full) words include the following: (1) Fraenkel and Simpson showed that we can construct an infinite binary word containing at most three distinct squares; (2) Entringer, Jackson and Schatz showed that there exists an infinite binary word avoiding all squares of the form x x such that | x | ≥ 3, and that the bound 3 is optimal; (3) Dekking showed that there exists an infinite cube-free binary word that avoids all squares x x with | x | ≥ 4, and that the bound of 4 is best possible. In this paper, we investigate these avoidance results in the context of partial words, or sequences that may have some undefined symbols called holes. Here, a square has the form u v with u and v compatible, and consequently, such a square is compatible with a number of full words that are squares over the given alphabet. We show that (1) holds for partial words with at most two holes. We prove that (2) extends to partial words having infinitely many holes. Regarding (3), we show that there exist binary partial words with infinitely many holes that avoid cubes and have only eleven full word squares compatible with factors of it. Moreover, this number is optimal, and all such squares x x satisfy | x | ≤ 4.

Authors

• F. Blanchet-Sadri
• Ilkyoo Choi
• Robert Mercaş

Keywords

• Combinatorics on words
• Partial words
• Squares
• Cubes