In a new paper, Square-free strings over alphabet lists, my PhD student Neerja Mhaskar and I, solve an open problem that was posed in A new approach to non repetitive sequences, by Jaroslaw Grytczuk, Jakub Kozik, and Pitor Micek, in arXiv:1103.3809, December 2010.
The problem can be stated as follows: Given an alphabet list $L=L_1,\ldots,L_n$, where $|L_i|=3$ and $0 \leq i \leq n$, can we always find a square-free string, $W=W_1W_2 \ldots W_n$, where $W_i\in L_i$? We show that this is indeed the case. We do so using an “offending suffix” characterization of forced repetitions, and a counting, non-constructive, technique. We discuss future directions related to finding a constructive solution, namely a polytime algorithm for generating square-free words over such lists.
Our paper will be presented and published in the 26th International Workshop on Combinatorial Algorithms (IWOCA), Verona, Italy, October 2015.