Avoidability of Palindrome Patterns

Abstract

We characterize the formulas that are avoided by every $\alpha$-free word for some $\alpha>1$. We show that the avoidable formulas whose fragments are of the form $XY$ or $XYX$ are $4$-avoidable. The largest avoidability index of an avoidable palindrome pattern is known to be at least $4$ and at most $16$. We make progress toward the conjecture that every avoidable palindrome pattern is $4$-avoidable.