Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-09T19:50:53.033Z Has data issue: false hasContentIssue false

Abelian pattern avoidance in partial words∗

Published online by Cambridge University Press:  10 June 2014

F. Blanchet-Sadri
Affiliation:
Department of Computer Science, University of North Carolina, P.O. Box 26170, Greensboro, NC 27402–6170, USA.. blanchet@uncg.edu
Benjamin De Winkle
Affiliation:
Department of Mathematics, Pomona College, 610 North College Avenue, Claremont, CA 91711–4411, USA.
Sean Simmons
Affiliation:
Department of Mathematics, Massachusetts Institute of Technology, Building 2, Room 236, 77 Massachusetts Avenue, Cambridge, MA 02139–4307, USA.

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Pattern avoidance is an important topic in combinatorics on words which dates back to thebeginning of the twentieth century when Thue constructed an infinite word over a ternaryalphabet that avoids squares, i.e., a word with no two adjacent identicalfactors. This result finds applications in various algebraic contexts where more generalpatterns than squares are considered. On the other hand, Erdős raised the question as towhether there exists an infinite word that avoids abelian squares, i.e.,a word with no two adjacent factors being permutations of one another. Although thisquestion was answered affirmately years later, knowledge of abelian pattern avoidance israther limited. Recently, (abelian) pattern avoidance was initiated in the more generalframework of partial words, which allow for undefined positions called holes. In thispaper, we show that any pattern p with n> 3 distinct variables oflength at least 2n is abelian avoidable by a partial wordwith infinitely many holes, the bound on the length of p being tight. We completethe classification of all the binary and ternary patterns with respect to non-trivialabelian avoidability, in which no variable can be substituted by only one hole. We alsoinvestigate the abelian avoidability indices of the binary and ternary patterns.