Avoiding letter patterns in ternary square-free words (Q2635082): Difference between revisions

The usual pattern-avoidance results in combinatorics on words consider patterns where each variable can be replaced by a word. Thus a word avoiding the pattern \(xx\) is a square-free word. The present paper considers letter patterns, where each variable represents a single letter from a fixed alphabet, while different variables represent different letters. For example, the pattern \(xyxz\) represents the set of words \(\left\{ abac,acab,babc,bcba,cacb,cbca\right\} \) on the alphabet \(\left\{ a,b,c\right\} \). The author investigates avoidability of such patterns in square-free words on a 3-letter alphabet. She constructs the required square-free words based on an encoding of Fibonacci words. She shows that the following ternary square-free letter patterns are avoidable by ternary square-free words: (a) \(xyxzx,xyzxy\); (b) \(xyxzyz\) and all patterns of length \(6\) containing a pattern from (a). All other such patterns of length \(\leq6\) are unavoidable by ternary square-free words.