An Erdős--Szekeres type result for words with repeats
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918524295839744 |
|---|---|
| author | Celano, Kyle Ollson, Abigail Velankar, Niraj Yan, Jun |
| author_facet | Celano, Kyle Ollson, Abigail Velankar, Niraj Yan, Jun |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_23573 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An Erdős--Szekeres type result for words with repeats Celano, Kyle Ollson, Abigail Velankar, Niraj Yan, Jun Combinatorics 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. |
| title | An Erdős--Szekeres type result for words with repeats |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2510.23573 |