Growth problems for avoidable words (Q908709): Difference between revisions

A word w is said to avoid a word u if no subword of w is the homomorphic image of u. The word u is said to be avoidable on n letters if there are arbitrarily long words on an alphabet with n letters avoiding u. If u is avoidable on n letters for some n, let \(\mu\) (U) denote the minimum possible such n. It is proved that \(\mu\) (U) has a linear bound in terms the alphabet size of u and that there are 4-avoidable words which are not 3-avoidable. Such a word is \[ a b w b c x c a y b a z a c. \] The general case, of \((n+1)\)-avoidable words which are not n-avoidable, for \(n\geq 4\), remains open. Moreover, it is proved that if u is 4-avoidable and not 3-avoidable, then the number of words of length p on an \(\mu\) (U)-letter alphabet tha avoid u has a polynomial bound in terms of p. (In contrast, for xx this bound is known to be exponential.) Combinatorial, graph theory and topological instruments are involved in proofs; a list of open problems and a large bibliography end this beautiful paper.