On ternary square-free circular words
classification
💻 cs.FL
cs.DMmath.CO
keywords
circularwordsproofsquare-freeternarylengthsadditionallows
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.