Three Generalizations of Erdős Szekeres: k k -Modal Subsequences
Charles Gong · 2025
Read Three Generalizations of Erdős Szekeres: k k -Modal Subsequences by Charles Gong (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-2508-20360.txt.
Introduction
Charles Gong published this mathematics paper in 2025. It revisits a classic result of Erdős and Szekeres about shuffled numbers. Any shuffling of n numbers hides a monotone run, steadily rising or falling, of length at least the square root of n. Later work allowed runs that change direction a few times, called modal subsequences.
Fan Chung had shown that one direction change guarantees a run near the square root of three n. She conjectured the pattern for k changes: a run of about the square root of (2k+1)n. Another researcher proved the conjecture in 2024 using partial orders. Gong gives a substantially different proof based on sophisticated labeling arguments. The paper also proves a related guarantee for runs that rise first, of length about the square root of 2kn. New proofs of known results matter in combinatorics because they often generalize where the first proof cannot.
Catalog record
| CREATOR | Charles Gong |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 24 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-20360
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Three Generalizations of Erdős Szekeres: k k -Modal Subsequences Charles Gong Abstract Erdős and Szekeres showed that given a permutation p p of [ n ] [n] , and the sequence defined by ( p ( 1 ) , p ( 2 ) , … , p ( n ) ) (p(1),p(2),\ldots,p(n)) , there exists either a decreasing or increasing subsequence, not necessarily contiguous, of length at least n \sqrt{n} . Fan Chung considered subsequences that can have at most one change of direction, i.e. an increasing and then decreasing subsequence, or a decreasing and then increasing subsequence. She called these unimodal subsequences, and showed there exists a unimodal subsequence of length at least 3 n \sqrt{3n} , up to some constants [ 1 ] . She conjectured that a permutation of n n contains a k k -modal (at most k k changes in direction) subsequence of length at least ( 2 k + 1 ) n \sqrt{(2k+1)n} up to some constants. Zijian Xu proved this conjecture in 2024 [ 2 ] , and we will provide another substantially different proof using ”sophisticated labeling arguments” instead of ”underlying poset structures behind k-modal subsequences.” We also show that there exists an increasing first k k -modal subsequence of length at least 2 k n \sqrt{2kn} . 1 Definitions We write a sequence of length n as (a_{1},a_{2},\ldots,a_{n}) . Such a sequence is a permutation if a_{i}\in[n] for all i\in[n] , and for each b\in[n] , there exists at least one i such that a_{i}=b . A sequence (a_{1},a_{2},\ldots,a_{n}) is increasing if a_{i}<a_{i+1} for all i\in[n-1] . It is decreasing if a_{i}>a_{i+1} for all i\in[n-1] . Formally, for k\in\mathbb{N} we define a k -modal subsequence of (a_{1},a_{2},\ldots,a_{n}) as a sequence (a_{i_{1}},a_{i_{2}},\ldots,a_{i_{m}}) such that i_{j}\in[n] for all j\in[m] , and for all j\in[m-1] we have i_{j}<i_{j+1} (i.e. it’s a subsequence). Furthermore, there exists a sequence of indices (i_{j_{1}},i_{j_{2}},\ldots,i_{j_{p}}) where p\leq k (at most k indices), and i_{j_{\ell}}\in[m] for all \ell\in[p] , and for all \ell\in[p-1] we have i_{j_{\ell}}<i_{j_{\ell+1}} , such that for all \ell\in[p-1] we have (a_{i_{1}},a_{i_{2}},\ldots,a_{i_{j_{1}}}),(a_{i_{j_{1}}},a_{i_{j_{1}+1}},\ldots,a_{i_{j_{2}}}),\ldots,(a_{i_{j_{p}}},a_{i_{j_{p}+1}},\ldots,a_{i_{m}}) are either increasing or decreasing (i.e., at most k changes in direction). We call such a subsequence increasing first if (a_{i_{1}},a_{i_{2}},\ldots,a_{i_{j_{1}}}) is increasing, and decreasing if (a_{i_{1}},a_{i_{2}},\ldots,a_{i_{j_{1}}}) is decreasing. Note a subsequence of length 1 is both increasing and decreasing, which means in general that any k -modal subsequence is both an increasing first and a decreasing first k+1 -modal subsequence. Also, the subsequences (a_{i_{1}},a_{i_{2}},\ldots,a_{i_{j_{1}}}),(a_{i_{j_{1}}},a_{i_{j_{1}+1}},\ldots,a_{i_{j_{2}}}),\ldots, (a_{i_{j_{p}}},a_{i_{j_{p}+1}},\ldots,a_{i_{m}}) form the p+1 ”parts” of the k -modal subsequence. 2 \sqrt{2kn} Increasing First k -modal Subsequences Theorem 1 . In any permutation of [n] , there exists an increasing first k -modal subsequence of length at least \sqrt{2kn} , up to some constants. Proof. We proceed by induction. The case where k=0 is trivial. We start with our base case set at k=1 for illustrative purposes. For the permutation (a_{1},a_{2},\ldots,a_{n}) , define the function x:[n]\rightarrow[n] where x(a_{i}) is the maximum length of an increasing subsequence ending at a_{i} , including a_{i} . So for example in (1,5,3,2,4) , we have x(4)=3 because of the subsequence (1,3,4) . Define y:[n]\rightarrow[n] where y(a_{i}) is the maximum length of a decreasing subsequence starting at a_{i} , including a_{i} . Note that x(a_{i})+y(a_{i})-1 is the length of an increasing first 1 -modal subsequence where it ”changes direction” at a_{i} . We claim that the function f:[n]\rightarrow[n]\times[n] defined by f(a_{i})=(x(a_{i}),y(a_{i})) is an injection. Without loss of generality, assume i\leq j . Assume (x(a_{i}),y(a_{i}))=(x(a_{j}),y(a_{j})) . From x(a_{i})=x(a_{j}) , we know that a_{i}\geq a_{j} ; this is because if a_{i}<a_{j} , we would know that x(a_{j})\geq x(a_{i})+1 , because for any increasing subsequence ending at a_{i} , we can get a longer one by appending a_{j} . Using similar reasoning, y(a_{i})=y(a_{j}) implies that a_{i}\leq a_{j} . This shows that a_{i}=a_{j} , and thus f is injective. Define N to be the maximum length of an increasing first 1 -modal subsequence. As mentioned above, for each a_{i} we have x(a_{i})+y(a_{i})-1\leq N , or x(a_{i})+y(a_{i})\leq N+1 . Furthermore, we know x(a_{i}),y(a_{i})\geq 1 for any i . Thus, f is an injective function mapping a_{i} to the triangular region defined by x+y\leq N+1 , x,y\geq 1 . There’s at \frac{N(N+1)}{2} points in this triangle. By the injectivity of f , we have that n\leq\frac{N(N+1)}{2} , and this gives us the \sqrt{2n}\leq N bound up to some constants. Instead, we use the area of the triangle n\leq\frac{N^{2}}{2} to get the bound \sqrt{2n}\leq N exactly, which is potentially wrong, but will make things look nicer later. From now on, we will approximate the number of lattice points in rectangular and triangular regions by the areas of those regions. Now we go on to the induction step. Assume for any permutation of length n , there exists an increasing first k -modal subsequence of length at least \sqrt{2kn} . We claim for any permutation of length n , there exists a decreasing first k -modal subsequence of length at least \sqrt{2kn} . We prove this by flipping the permutation, i.e. converting (a_{1},a_{2},\ldots a_{n}) to (n+1-a_{1},n+1-a_{2},\ldots,n+1-a_{n}) , which is also a permutation, finding a length \sqrt{2kn} increasing subsequence (n+1-a_{1},n+1-a_{2},\ldots,n+1-a_{n}) , and finally flipping again to get a length \sqrt{2kn} decreasing subsequence in (a_{1},a_{2},\ldots a_{n}) . Now we show there exists an increasing first k+1 -modal subsequence of length at least \sqrt{2(k+1)n} . Define x(a_{i}) to be the maximum length of an increasing subsequence ending at a_{i} . Define y(a_{i}) to be the maximum length of a decreasing first k -modal subsequence starting at a_{i} . Define N to be the maximum length of an increasing first k+1 -modal subsequence. Again, note that x(a_{i})+y(a_{i})-1\leq N , and that using similar arguments in the k=1 case, we can show f:[n]\rightarrow[n]\times[n] defined by f(a_{i})=(x(a_{i}),y(a_{i})) is injective. So again, we are mapping a_{i} to a triangular region. We claim that there are at most \frac{kN^{2}}{2(k+1)^{2}} points (x(a_{i}),y(a_{i})) where y(a_{i})<\frac{kN}{k+1} : this is because by the induction hypothesis, among the a_{i} satisfying y(a_{i})<\frac{kN}{k+1} , there is a decreasing first k -modal susbequence of length at least \sqrt{2k(\frac{kN^{2}}{2(k+1)^{2}})}=\frac{kN}{k+1} (note to apply the induction hypthesis, we implicitly used a map g which maps the a_{i} satisfying y(a_{i})<\frac{kN}{k+1} to a permutation which preserves pairwise comparisons, i.e. a_{i}<a_{j} if and only if g(a_{i})<g(a_{j}) ). Note there are roughly \frac{1}{2}(N-\frac{kN}{k+1})^{2}=\frac{N^{2}}{2(k+1)^{2}} integer lattice points in the region defined by y\geq\frac{kN}{k+1} , x+y\leq N+1 . This gives the bound n\leq\frac{kN^{2}}{2(k+1)^{2}}+\frac{N^{2}}{2(k+1)^{2}}=\frac{N^{2}}{2(k+1)} and so \sqrt{2(k+1)n}\leq N , as required. ∎ We now give a family of permutations that roughly achieve the \sqrt{2kn} bound. We decided to describe this family, parametrized by t , using python code. def strongMake(k, t): kstrong = [] count = 1 if k % 2 == 0: for i in range(t * (k // 2)): for j in reversed(range(count, count + t)): kstrong.append(j) count = count + t else: for i in range(t * (k // 2)): for j in reversed(range(count, count + t)): kstrong.append(j) count = count + t for i in reversed(range(t)): for j in reversed(range(count, count + i)): kstrong.append(j) count = count + i return kstrong kstrong is the permutation parametrized by t . The name is a remnant of Fan Chung’s