Doubled patterns with reversal and square-free doubled patterns (Q2699639)

Summary: In combinatorics on words, a word \(w\) over an alphabet \(\Sigma\) is said to avoid a pattern \(p\) over an alphabet \(\Delta\) if there is no factor \(f\) of \(w\) such that \(f=h(p)\) where \(h:\Delta^*\to\Sigma^*\) is a non-erasing morphism. A pattern \(p\) is said to be \(k\)-avoidable if there exists an infinite word over a \(k\)-letter alphabet that avoids \(p\). A pattern is \textit{doubled} if every variable occurs at least twice. Doubled patterns are known to be \(3\)-avoidable. Currie, Mol, and Rampersad have considered a generalized notion which allows variable occurrences to be reversed. That is, \(h(V^R)\) is the mirror image of \(h(V)\) for every \(V\in\Delta \). We show that doubled patterns with reversal are \(3\)-avoidable. We also conjecture that (classical) doubled patterns that do not contain a square are \(2\)-avoidable. We confirm this conjecture for patterns with at most 4 variables. This implies that for every doubled pattern \(p\), the growth rate of ternary words avoiding \(p\) is at least the growth rate of ternary square-free words. A previous version of this paper containing only the first result has been presented at WORDS 2021.