Example

$ \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} \def\alph{\mathit{alph}} \def\mv{\varepsilon} \def\Al{A} $

For example, the word $\sa{aaaaabaabbaaaabaabb}$ contains $Z_3$, since its factor $\sa{aaabaabbaaaabaa}$ is the image of $Z_3=\alpha_1\alpha_2\alpha_1\alpha_3\alpha_1\alpha_2\alpha_1$ by the morphism $\psi$ defined by \[\cases{ \psi(\alpha_1) = \sa{aa} &\cr \psi(\alpha_2) = \sa{ab} &\cr \psi(\alpha_3) = \sa{bba} }\]

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.

125 Problems in Text Algorithms

Example

Problem 93: Unavoidable Patterns

References