Some Variations on a Theme of Irina Mel'nichuk Concerning the Avoidability of Patterns in Strings of Symbols

Abstract

The set of all doubled patterns on $n$ or fewer letters can be avoided on an alphabet with $k$ letters, where $k$ is the least even integer strictly greater than $n+1$, with the exception of $n=4$. The set of all doubled patterns on $4$ or fewer letters can be avoided on the $8$-letter alphabet. The set of all avoidable patterns on $n$ or fewer letters can be avoided on an alphabet with $2(n+2)$ letters.