CLR cover

Problem 93: Unavoidable Patterns

Patterns of the problem are defined with a specific alphabet of variables in addition to the finite alphabet $\Al=\{\sa{a},\sa{b},\dots\}$. Variables are from the infinite alphabet $\mathtt{V}=\{\alpha_1,\alpha_2,\dots\}$. A pattern is a word whose letters are variables. A typical pattern is $\alpha_1\alpha_1$: it appears in a word that contains a square. The aim of the problem is to produce unavoidable patterns.

A word $w\in \Al^+$ is said to contain a pattern $P\in\mathtt{V}^*$ if $\psi(P)$ is a factor $w$ for some morphism $\psi : \alph(P)^+\rightarrow \Al^+$. If not, $w$ is said to avoid $P$. A pattern is avoidable if there are infinitely many words of $\Al^+$ avoiding it, which is equivalent (because $\Al$ is finite) to the existence of an infinite word in $\Al^\infty$ whose finite factors avoid it. For example, $\alpha_1\alpha_1$ is avoidable if the alphabet has at least three letters, but is unavoidable on a binary alphabet (see Problem 79).

Zimin patterns $Z_n$ are standard examples of unavoidable patterns. They are defined, for $n\gt 0$, by $$Z_0=\mv \mbox{ and } Z_n = Z_{n-1}\cdot \alpha_n\cdot Z_{n-1}.$$ In particular, a word contains the Zimin pattern $Z_n$ if it contains a factor whose Zimin type is at least $n$ (see Problem 43).

Show that Zimin patterns $Z_n$, $n\gt 0$, are unavoidable.

References

  • A. Carayol and S. Göller. On long words avoiding Zimin patterns. In H. Vollmer and B. Vallée, editors, 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany, volume 66 of LIPIcs, pages 19:1-19:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017.
  • M. Lothaire. Algebraic Combinatorics on Words. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2002.