Shuffle Squares and Nest-Free Graphs
摘要
A shuffle square is a word consisting of two shuffled copies of the same word. For instance, the French word is a shuffle square, as it can be split into two copies of the word \(\texttt{tuer}\) . An ordered graph is a graph with a fixed linear order of vertices. We propose a representation of shuffle squares in terms of special nest-free ordered graphs and demonstrate the usefulness of this approach by applying it to several problems. Among others, we prove that binary words of the type \((\texttt{1001})^n\) , n odd, are not shuffle squares and, moreover, they are the only such words among all binary words whose every \(\texttt{1}\) -run has length one or two, while every \(\texttt{0}\) -run has length two. We also provide a counterexample to a believable stipulation that binary words of the form \(\mathtt 1^{n}\mathtt 0^{n-2}\mathtt 1^{n-4}\cdots \) , n odd, are far from being shuffle squares (the distance measured by the minimum number of letters one has to delete in order to turn a word into a shuffle square).