EUVIMEDEUVIMED entdecken
Crossref

An Erdős--Szekeres type result for words with repeats

Kyle Celano, Abigail Ollson, Niraj Velankar, Jun Yan

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →