洗牌平方与无巢图

Shuffle squares and nest-free graphs

摘要 Abstract

洗牌平方是指由两个相同单词洗牌组合而成的单词。例如,法语单词$\mathtt{\color{red}{tu}\color{blue}{t}\color{red}{e}\color{blue}{u}\color{red}{r}\color{blue}{er}}$是一个洗牌平方,因为它可以被分割为两个相同的单词$\mathtt{tuer}$。有序图是一种顶点具有固定线性顺序的图。我们通过特殊的无巢有序图来表示洗牌平方,并通过此方法解决了一些问题。其中,我们证明了形如$(\mathtt{1001})^n$($n$为奇数)的二进制词不是洗牌平方,并且它们是所有二进制词中唯一满足每个$\mathtt{1}$-段长度为一或二,而每个$\mathtt{0}$-段长度为二的非洗牌平方词。此外,我们还提供了一个反例,反驳了一种可信的假设:形如$\mathtt1^{n}\mathtt0^{n-2}\mathtt1^{n-4}\cdots$($n$为奇数)的二进制词远不是洗牌平方(距离通过删除最少数量的字母使单词成为洗牌平方来衡量)。

A shuffle square is a word consisting of two shuffled copies of the same word. For instance, the French word $\mathtt{\color{red}{tu}\color{blue}{t}\color{red}{e}\color{blue}{u}\color{red}{r}\color{blue}{er}}$ is a shuffle square, as it can be split into two copies of the word $\mathtt{tuer}$. An ordered graph is a graph with a fixed linear order of vertices. %In particular, the same abstract graph may give rise to many different ordered graphs identified by an order-prserving isomorphism. 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 $(\mathtt{1001})^n$, $n$ odd, are not shuffle squares and, moreover, they are the only such words among all binary words whose every $\mathtt{1}$-run has length one or two, while every $\mathtt{0}$-run has length two. We also provide a counterexample to a believable stipulation that binary words of the form $\mathtt1^{n}\mathtt0^{n-2}\mathtt1^{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).

洗牌平方与无巢图 - arXiv