Extremal Pattern-Avoiding Words

Abstract

Recently, Grytczuk, Kordulewski, and Niewiadomski defined an extremal word over an alphabet $\mathbb{A}$ to be a word with the property that inserting any letter from $\mathbb{A}$ at any position in the word yields a given pattern. In this paper, we determine the number of extremal $X{Y}_{1}X{Y}_{2}X\dots X{Y}_{t}X$-avoiding words on a $k$-letter alphabet. We also derive a lower bound on the shortest possible length of an extremal square-free word on a $k$-letter alphabet that grows exponentially in $k$.

10 pages

References in corpus (1)

• Lengths of extremal square-free ternary words