Natasha Ter-Saakov, Rutgers University

Abstract

Consider a word (a sequence of letters) on an alphabet of size k. This word contains a pattern if it contains (consecutive) subwords that realize the pattern and avoids it otherwise. An extremal pattern-avoiding word is one where inserting any letter anywhere realizes some fixed pattern. How long can such words be? How many are there? In this talk, we will give an overview of much that is known about extremal pattern-avoiding words. (Part of this talk will be based on joint work with Emily Zhang.)