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).

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Shuffle Squares and Nest-Free Graphs

  • Jarosław Grytczuk,
  • Bartłomiej Pawlik,
  • Andrzej Ruciński

摘要

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).