Kalpana Kalpana (Editor)

Unavoidable pattern

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

In mathematics and theoretical computer science, an unavoidable pattern is a pattern of symbols that must occur in any sufficiently long string over an alphabet. An avoidable pattern is one for which there are infinitely many words no part of which match the pattern.

Contents

Zimin words are an example of unavoidable patterns. These are formed by inserting a new letter between two instances of the previous Zimin word, i.e., the first Zimin word A is used to create the second Zimin word ABA, which in turn creates ABACABA and then ABACABADABACABA and so on.

It is unavoidable that any string, containing two unique characters, that is five or more characters long will contain a pattern of the form ABA (the second Zimin word). Using three unique characters any string containing 29 or more characters will contain a pattern of the form ABACABA

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-avoidable if it is avoidable on an alphabet of size k.

There is a word W(k) over an alphabet of size 4k which avoids every avoidable pattern with less than 2k variables.

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; words avoiding this pattern are square-free.
  • The power patterns xn for n ≥ 3 are 2-avoidable: the Thue–Morse sequence is an example for n=3.
  • Sesquipowers are unavoidable.

    • Avoidability index

    The avoidability index of a pattern p is the smallest k such that p is k-avoidable, or ∞ if p is unavoidable. For binary patterns (two variables x and y) we have:

  • The Zimin words x, xyx, xyxzxyx, xyxzxyxwxyxzxyx, etc. are unavoidable, as well as any word that can be written as a subword of a Zimin word via a homomorphism. All other words are avoidable.
  • Many patterns have avoidability index 2.
  • xx,xxy,xyy,xxyx,xxyy,xyxx,xyxy,xyyx,xxyxx,xxyxy,xyxyy, as well as many doubled words, have avoidability index 3, though this list is not complete.
  • abwbaxbcyaczca has avoidability index 4, as well as other locked words. (Baker, McNulty, Taylor 1989)
  • abvbawbcxacycdazdcd has avoidability index 5. (Clark 2004)
  • no words with index greater than 5 have been found.

    • Square-free words

    A square-free word is one avoiding the pattern xx. An example is the word over the alphabet {0,±1} obtained by taking the first difference of the Thue–Morse sequence.

    References

    Unavoidable pattern Wikipedia
    (Text) CC BY-SA