Cubic patterns with permutations

摘要

We consider a generalisation of the classical problem of pattern avoidance in infinite words with functional dependencies between pattern variables. More precisely, we consider patterns involving permutations. The foremost remarkable fact regarding this new setting is that the notion of avoidability index (the smallest alphabet size for which a pattern is avoidable) is meaningless, since a pattern with permutations that is avoidable in one alphabet can be unavoidable in a larger alphabet. We characterise the (un-)avoidability of all patterns of the form πi(x)πj(x)πk(x), called cubic patterns with permutations here, for all alphabet sizes in both the morphic and antimorphic case.