Circular words are cyclically ordered finite sequences of letters. We give a computer-free proof of the following result by Currie: square-free circular words over the ternary alphabet exist for all lengths $l$ except for 5, 7, 9, 10, 14, and 17. Our proof reveals an interesting connection between ternary square-free circular words and closed walks in the $K_{3{,}3}$ graph. In addition, our proof implies an exponential lower bound on the number of such circular words of length $l$ and allows one to list all lengths $l$ for which such a circular word is unique up to isomorphism.
展开▼
机译:圆形词是字母的循环有序有限序列。我们提供了Currie的以下结果的免费计算机证明:除5、7、9、10、14和17外,所有长度$ l $上都存在三进制字母上的无正方形圆形单词。我们的证明揭示了一个有趣的现象$ K_ {3 {,} 3} $图中的三元无平方圆形词与封闭步道之间的连接。另外,我们的证明暗含了这样的长度为$ l $的循环词的数量的指数下界,并允许列出所有长度为$ l $的此类循环词,直到同构为止。
展开▼