An Erdős--Szekeres type result for words with repeats
Discrete Mathematics & Theoretical Computer Science · 20.05.2026 · vol. 28:1, Permutation... (Special issues)
DOI: 10.46298/dmtcs.16801 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Mathematics & Theoretical Computer Science, online erschienen am 20.05.2026. Verfasst von Kyle Celano und 3 weiteren Autor:innen.
Abstract (Originalsprache)
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
Zitieren
APA
Celano, K., Ollson, A., Velankar, N., & Yan, J. (2026). An Erdős--Szekeres type result for words with repeats. Discrete Mathematics & Theoretical Computer Science, vol. 28:1, Permutation...(Special issues). https://doi.org/10.46298/dmtcs.16801
Vancouver
Celano K, Ollson A, Velankar N, Yan J. An Erdős--Szekeres type result for words with repeats. Discrete Mathematics & Theoretical Computer Science. 2026;vol. 28:1, Permutation...(Special issues). doi:10.46298/dmtcs.16801
BibTeX
@article{Celano2026,
author = {Celano, Kyle and Ollson, Abigail and Velankar, Niraj and Yan, Jun},
title = {An Erdős--Szekeres type result for words with repeats},
journal = {Discrete Mathematics & Theoretical Computer Science},
year = {2026},
volume = {vol. 28:1, Permutation...},
number = {Special issues},
doi = {10.46298/dmtcs.16801}
}
EUVIMED