Computing Depths of Patterns

¹ Department of Computer Science, University of North Carolina, P.O. Box 26170, Greensboro, NC 27402–6170, USA.
blanchet@uncg.edu
² Department of Mathematics, Rutgers University, 110 Frelinghuysen Rd., Piscataway, NJ 08854–8019, USA.
ajl213@scarletmail.rutgers.edu

Received: 22 January 2016
Accepted: 13 June 2016

Abstract

Pattern avoidance is an important research topic in combinatorics on words which dates back to Thue’s construction of an infinite word over three letters that avoids squares, i.e., a sequence with no two adjacent identical factors. This result finds applications in various algebraic contexts where more general patterns than squares are considered. A more general form of pattern avoidance has recently emerged to allow for undefined positions in sequences. New concepts on patterns such as depth have been introduced and a number of questions have been raised, some of them we answer. In the process, we prove a strict bound on the number of square occurrences in an unavoidable pattern, and consequently, any pattern with more square occurrences than distinct variables is avoidable over three letters. We also provide an algorithm that determines whether a given pattern is of bounded depth, and if so, computes its depth.