Abelian Pattern Avoidance in Partial Words

10/16/2012 - 12:15pm
10/16/2012 - 1:10pm
Ben De Winkle (Pomona College)

In 1961, Erdös asked whether there exists an infinite word (read “string of letters”) such that no two adjacent blocks within this word are permutations of each other. We call such adjacent blocks an abelian square. This launched study into abelian instances of higher powers and more general patterns in words. For example, “hand-to-hand” is an instance of the pattern “ABA” because the block “hand” is repeated with a different block in between the two occurrences, and “level” is an abelian instance of “ABA” because “le” and “el” are permutations of each other and occur with a different block between them. Motivated by DNA sequencing, Berstel and Boasson began studying partial words by inserting “do not know” symbols, also known as “holes” into words. In this talk, I will survey results concerning power and pattern avoidance in words and partial words, with special focus on avoiding abelian instances of patterns in infinite partial words with infinitely many holes.

ML 208 (Pomona College)