Unavoidable pattern

In mathematics, an unavoidable pattern refers to a pattern of symbols which must occur in any sufficiently long string over an alphabet. An avoidable pattern is one which for which there is an infinite word no part of which matches the pattern.

Let A be an alphabet of letters and E a disjoint alphabet of pattern symbols or "variables". Elements of E⁺ are patterns. For a pattern p, the pattern language is that subset of A^∗ containing all words h(p) where h is a non-erasing semigroup morphism from the free monoid E^∗ to A^∗. A word w in A^∗ matches or meets p if it contains some word in the pattern language as a factor, otherwise w avoids p.

A pattern p is avoidable on A if there are infinitely many words in A^∗ that avoid p; it is unavoidable on A if all sufficiently long words in A^∗ match p. We say that p is k-unavoidable if it is unavoidable on every alphabet of size k and correspondingly k-unavoidable if it is avoidable on an alphabet of size k.

Examples

• The Thue–Morse sequence avoids the patterns xxx and xyxyx.
• The patterns x and xyx are unavoidable on any alphabet.
• The power pattern xx is 3-avoidable.
• The power patterns xⁿ for n≥3 are 2-avoidable: the Thue–Morse sequence is an example.

References

• Lothaire, M. (2011). Algebraic combinatorics on words. Encyclopedia of Mathematics and Its Applications. Vol. 90. With preface by Jean Berstel and Dominique Perrin (Reprint of the 2002 hardback ed.). Cambridge University Press. ISBN 978-0-521-18071-9. Zbl 1221.68183.