Kyle Celano ; Abigail Ollson ; Niraj Velankar ; Jun Yan - An Erdős--Szekeres type result for words with repeats

dmtcs:16801 - Discrete Mathematics & Theoretical Computer Science, May 20, 2026, vol. 28:1, Permutation Patterns 2025 - https://doi.org/10.46298/dmtcs.16801
An Erdős--Szekeres type result for words with repeatsArticle

Authors: Kyle Celano ; Abigail Ollson ; Niraj Velankar ; Jun Yan

We prove an Erdős--Szekeres type result for finite words over $\mathbb{N}$ with repeated values. Specifically, we define a \emph{repeat} in a word to be an occurrence of a value which is not its first occurrence. We define an occurrence of a \emph{pattern} $π$ in a word $w$ to be a (not necessarily consecutive) subword of $w$ that is order isomorphic to $π$. In this note, we show that every word with $kn^6+1$ repeats contains one of the following patterns: $0^{k+2}$, $0011\cdots nn$, $nn\cdots1100$, $012 \cdots n012 \cdots n$, $012 \cdots nn\cdots 210$, $n\cdots 210012\cdots n$, $n\cdots 210n\cdots 210$. Moreover, when $k=1$, we show that this is best possible by constructing a word with $n^6$ repeats that does not contain any of these patterns.

11 pages, 9 figures


Volume: vol. 28:1, Permutation Patterns 2025
Section: Special issues
Published on: May 20, 2026
Accepted on: May 14, 2026
Submitted on: October 28, 2025
Keywords: Combinatorics