论文标题
极端模式的单词
Extremal Pattern-Avoiding Words
论文作者
论文摘要
最近，Grytczuk，Kordulewski和Niewiadomski在字母$ \ Mathbb {a} $上定义了一个极端单词，是一个单词，是一个属性，该属性从$ \ Mathbb {a} $中插入任何位置的任何字母都在任何位置都以给定的模式产生一个给定的模式。在本文中，我们确定了$ xy_1xy_2x \ dots xy_tx $ - 在$ k $ - 字母字母上避免单词的极端数量。我们还以$ k $ - 字母的极端无正方形单词的最短长度得出了一个下限，该字母在$ k $中呈指数增长。
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 $XY_1XY_2X\dots XY_tX$-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$.
