An Erdős–Szekeres type result for words with repeats
Kyle Celano, Abigail Ollson, Niraj Velankar, Jun Yan · 2025
Read An Erdős–Szekeres type result for words with repeats by Kyle Celano, Abigail Ollson, Niraj Velankar, Jun Yan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-23573.txt.
Introduction
Kyle Celano and three co-authors prove a pattern result for words, meaning finite strings of natural numbers where values may repeat. A repeat is any occurrence of a value after its first appearance. They ask how many repeats a word can carry before one of several fixed patterns must show up inside it. A pattern shows up when some scattered subword matches the pattern's ordering of values.
They show that any word past a certain count of repeats must contain one of seven listed patterns. Those patterns range from long flat runs to rising and falling staircase shapes, and the count depends on the pattern size. For the smallest case of their parameter, the bound is exactly right. They prove that by building a word that reaches the lower count of repeats while dodging every one of the patterns.
Catalog record
| CREATOR | Kyle Celano, Abigail Ollson, Niraj Velankar, Jun Yan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 19 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-23573
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An Erdős–Szekeres type result for words with repeats Kyle Celano, Abigail Ollson, Niraj Velankar, Jun Yan Abstract . In this short note, we prove an Erdős–Szekeres type result for words with repeats. Specifically, we show that every word with k n 6 + 1 kn^{6}+1 repeats contains one of the following patterns: 0 k + 2 0^{k+2} , 0011 ⋯ n n 0011\cdots nn , n n ⋯ 1100 nn\cdots 1100 , 012 ⋯ n 012 ⋯ n 012\cdots n012\cdots n , 012 ⋯ n n ⋯ 210 012\cdots nn\cdots 210 , n ⋯ 210012 ⋯ n n\cdots 210012\cdots n , n ⋯ 210 n ⋯ 210 n\cdots 210n\cdots 210 . Moreover, when k = 1 k=1 , we show that this is best possible by constructing a word with n 6 n^{6} repeats that does not contain any of these patterns. 1. Introduction Let \mathbb{N}=\{0,1,2,\dots\} . A word of length n is an element w=w_{1}w_{2}\cdots w_{n}\in\mathbb{N}^{n} . For example, 376885 is a word of length 6. A word w\in\mathbb{N}^{n} can also be represented on a grid with points at (i,w_{i}) for every i\in[n] . For example, the word 13043134 is shown in Figure 1 . 0 1 2 3 4 1 2 3 4 5 6 7 8 Figure 1 . The word 13043134. We define a subword w^{\prime} of a word w to be a word obtained by taking a subsequence of letters in w which are not necessarily consecutive, for example 3313 is a subword of the word 13043134. The standardisation of a word w\in\mathbb{N}^{n} is defined to be the word obtained by replacing every occurrence of the smallest value in w by 0, the next smallest by 1 and so on. The standardisation of a word is called a pattern 1 1 1 These are also called Cayley permutations; see [ Mor and Fraenkel, 1984 ] . For example, the standardisation of the word 296893 is the pattern 042341. A word w contains a pattern \pi if there exists a subword of w which standardises to \pi , otherwise w avoids \pi . As the standardisation of 3313 is 1101, the word 13043134 contains the pattern 1101. A non-decreasing word is an increasing word in which repeated values are allowed, for example 00122, and a strictly increasing word is an increasing word in which repeated values are not allowed, for example 0123. Non-increasing and strictly decreasing words are defined similarly. The Erdős–Szekeres Theorem, stated below in Theorem 1.1 , is a landmark result in combinatorics with many variants and generalisations, and wide-ranging applications in areas like discrete geometry, graph theory, and computer science. Theorem 1.1 (Erdős–Szekeres Theorem [ Erdős and Szekeres, 1935 ] ) . Let r,s\in\mathbb{N} . Every word of length rs+1 contains a non-decreasing subword of length r+1 or a non-increasing subword of length s+1 (or both). For permutations, the Erdős–Szekeres Theorem implies that any permutation of size n^{2}+1 contains a strictly increasing or decreasing pattern of size n+1 , or equivalently either the pattern 01\cdots n or n\cdots 10 . For general words that can have repeated values, this is no longer true. In this short note, we prove a similar result, Theorem 1.2 , that identifies the unavoidable patterns in any word with a given number of repeated values. This will be used in an upcoming work for understanding and enumerating inversion sequences. We define the number of repeats in a word to be the total number of occurrences of values which are not the first occurrence of that value. Equivalently, for a word w=w_{1}\cdots w_{n} , the number of repeats is number of i\in[n] such that there exists j<i with w_{j}=w_{i} . For example, 0000 has 3 repeats, and 00110 has 3 repeats as 0 is repeated twice and 1 is repeated once. For a word w , let w^{id}=w , and let w^{rev} be the reverse of w , e.g. (2341)^{rev}=1432 . We show that the types of unavoidable patterns are the constant patterns, patterns of the form 001122\cdots nn and their reverses, and patterns of the form u^{e_{1}}u^{e_{2}} where u=01\cdots n and e_{i}\in\{id,rev\} . These three types are defined as types a) , b) and c) in Theorem 1.2 , respectively. Theorem 1.2 . Let k,n\in\mathbb{N} . Every word with kn^{6}+1 repeats contains one of the following patterns. a) 0^{k+2} . b) (0011\cdots nn)^{e} for e\in\{id,rev\} . c) (012\cdots n)^{e_{1}}(012\cdots n)^{e_{2}} for e_{1},e_{2}\in\{id,rev\} . When k=1 , Theorem 1.2 is best possible as shown by the following result. See Section 4 for a discussion when k>1 . Proposition 1.3 . There exists a word with n^{6} repeats that does not contain any of the following patterns. a) 0^{3} . b) (0011\cdots nn)^{e} for e\in\{id,rev\} . c) (012\cdots n)^{e_{1}}(012\cdots n)^{e_{2}} for e_{1},e_{2}\in\{id,rev\} . The asymmetric versions of both Theorem 1.2 and 1.3 , where the lengths of the patterns in b) and c) are allowed to differ like in Theorem 1.1 , can also be easily obtained by modifying our proof. We will prove Theorem 1.2 and 1.3 in Section 2 and Section 3 , respectively. In Section 4 , we will discuss some related problems and future research directions. 2. Unavoidable patterns In this section, we prove Theorem 1.2 , which says that any word with kn^{6}+1 repeats must contain one of the patterns in a) , b) and c) . Proof of Theorem 1.2 . Let w be a word with kn^{6}+1 repeats. If w contains a value that occurs k+2 times, then it contains the pattern 0^{k+2} , so a) holds. Assume now that every value appears at most k+1 times. Then, there are at least n^{6}+1 distinct values in w each with at least one repeat. Fix any n^{6}+1 distinct values in w with repeats, and let w^{\prime} be the subword of w consisting of the first two occurrences of each of these values in w . In particular, w^{\prime} has length 2n^{6}+2 . Let a_{0}a_{1}\cdots a_{n^{6}} be the subword of w^{\prime} consisting of the first occurrence of each of the n^{6}+1 distinct values in w^{\prime} . By Theorem 1.1 (Erdős–Szekeres), there is a subword a^{\prime}_{0}a^{\prime}_{1}\cdots a^{\prime}_{n^{3}} of a_{0}a_{1}\cdots a_{n^{6}} that is monotone. We first attempt to find a pattern in c) using Claim 2.1 below. Claim 2.1 . If there exists an index 0\leq j\leq n^{3}-n^{2} , such that the second occurrences in w^{\prime} of the values a^{\prime}_{j},a^{\prime}_{j+1},\ldots,a^{\prime}_{j+n^{2}} are all after the first occurrence of the value a^{\prime}_{j+n^{2}} , then w^{\prime} contains a pattern in c) . Proof of 2.1 . Suppose the repeats of a^{\prime}_{j},a^{\prime}_{j+1},\ldots,a^{\prime}_{j+n^{2}} form the subword b_{0}b_{1}\cdots b_{n^{2}} in w^{\prime} . By Theorem 1.1 (Erdős–Szekeres), b_{0}\cdots b_{n^{2}} contains a monotone subword b_{0}^{\prime}\cdots b_{n}^{\prime} . Let a_{0}^{\prime\prime}\cdots a_{n}^{\prime\prime} be the subword of a^{\prime}_{j}a^{\prime}_{j+1}\cdots a^{\prime}_{j+n^{2}} consisting of the values in b_{0}^{\prime}\cdots b_{n}^{\prime} , and note that it is also monotone. Therefore, a_{0}^{\prime\prime}\cdots a_{n}^{\prime\prime}b_{0}^{\prime}\cdots b_{n}^{\prime} is a subword of w^{\prime} forming a pattern in c) . ∎ If the hypothesis in Claim 2.1 holds for any j of the form j=(t-1)n^{2} with t\in[n] , then we are done, so assume otherwise. Hence, for each t\in[n] , there exists some (t-1)n^{2}\leq i_{t}\leq tn^{2}-1 , such that both occurrences of a^{\prime}_{i_{t}} appear before the first occurrence