Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2508.20360 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912912477519872 |
|---|---|
| author | Gong, Charles |
| author_facet | Gong, Charles |
| contents | Erdős and Szekeres showed that given a permutation $p$ of $[n]$, and the sequence defined by \newline $(p(1), p(2), \ldots, p(n))$, there exists either a decreasing or increasing subsequence, not necessarily contiguous, of length at least $\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 $\sqrt{3n}$, up to some constants \cite{chung}. She conjectured that a permutation of $n$ contains a $k$-modal (at most $k$ changes in direction) subsequence of length at least $\sqrt{(2k+1)n}$ up to some constants. Zijian Xu proved this conjecture in 2024 \cite{xu}, 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$-modal subsequence of length at least $\sqrt{2kn}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_20360 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Three Generalizations of Erdős Szekeres: $k$-Modal Subsequences Gong, Charles Combinatorics Erdős and Szekeres showed that given a permutation $p$ of $[n]$, and the sequence defined by \newline $(p(1), p(2), \ldots, p(n))$, there exists either a decreasing or increasing subsequence, not necessarily contiguous, of length at least $\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 $\sqrt{3n}$, up to some constants \cite{chung}. She conjectured that a permutation of $n$ contains a $k$-modal (at most $k$ changes in direction) subsequence of length at least $\sqrt{(2k+1)n}$ up to some constants. Zijian Xu proved this conjecture in 2024 \cite{xu}, 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$-modal subsequence of length at least $\sqrt{2kn}$. |
| title | Three Generalizations of Erdős Szekeres: $k$-Modal Subsequences |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2508.20360 |