Pattern avoidance in partial words over a ternary alphabet (Q2517160): Difference between revisions

A long-standing conjecture from [\textit{J. Cassaigne}, Motifs évitables et régularités dans les mots. Paris: Université Paris VI (PhD Thesis) (1994)] states that for a pattern \(p\) with exactly \(k\) distinct variables, (1) if \(p\) is of length at least \(2^k\), then its avoidability index is at most 3, while (2) if \(p\) is of length at least \(3 \cdot 2^{k-1}\), its avoidability index is 2. This conjecture was recently settled independently by \textit{F. Blanchet-Sadri} and \textit{B. Woodhouse} [Theor. Comput. Sci. 506, 17--28 (2013; Zbl 1301.68209)] and by \textit{P. Ochem} and \textit{A. Pinlou} [Electron. J. Comb. 21, No. 2, Research Paper P2.7, 12 p. (2014; Zbl 1299.68046)]. Furthermore, Blanchet-Sadri and Woodhouse conjectured that (1) is true for doubled patterns with \(k \geq 4\) distinct variables when partial word avoidability is concerned. In this paper, the authors answer affirmatively this conjecture on partial words via entropy compression and the probabilistic method.