Application of entropy compression in pattern avoidance (Q405191): Difference between revisions

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\). We give a positive answer to Problem 3.3.2 in \textit{M. Lothaire}'s book [Algebraic combinatorics on words. Cambridge: Cambridge University Press (2002; Zbl 1001.68093)], that is, every pattern with \(k\) variables of length at least \(2^k\) (resp. \(3\times2^{k-1}\)) is 3-avoidable (resp. 2-avoidable). This conjecture was first stated by \textit{J. Cassaigne} [Motifs évitables et régularité dans les mots. Paris: Université Paris VI (PhD Thesis) (1994)]. This improves previous bounds due to \textit{J. P. Bell} and \textit{T. L. Goh} [Inf. Comput. 205, No. 9, 1295--1306 (2007; Zbl 1127.68073)] and \textit{N. Rampersad} [Electron. J. Comb. 18, No. 1, Research Paper P134, 8 p. (2011; Zbl 1219.68128)].