What question did this study set out to answer?

To establish a result analogous to Erdős-Szekeres for finite words over integers with repeated values, focusing on the presence of specific patterns.

May 22, 2026Open Access

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

Key Points

To establish a result analogous to Erdős-Szekeres for finite words over integers with repeated values, focusing on the presence of specific patterns.
Defined repeats as non-first occurrences in a word.
Characterized patterns through order isomorphism and subwords.
Constructed a counterexample for k=1 with n^6 repeats without patterns.
Every word with kn^6+1 repeats contains specified patterns including 0^{k+2} and 0011\cdots nn.
Proved the result is best possible by constructing a word with n^6 repeats lacking any of the patterns.

Abstract

We prove an Erdős--Szekeres type result for finite words over N with repeated values. Specifically, we define a repeat in a word to be an occurrence of a value which is not its first occurrence. We define an occurrence of a 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⁶+1 repeats contains one of the following patterns: 0^k+2, 0011 nn, nn1100, 012 n012 n, 012 nn 210, n 210012 n, n 210n 210. Moreover, when k=1, we show that this is best possible by constructing a word with n⁶ repeats that does not contain any of these patterns. 11 pages, 9 figures

Ask AI

Helpful

Bookmark

View Full Paper