Three Generalizations of Erdős Szekeres: k-Modal Subsequences

Erdős and Szekeres showed that given a permutation p of $[n]$, and the sequence defined by (p(1), p(2), …, p(n)), there exists either a decreasing or increasing subsequence, not necessarily contiguous, of length at least √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 √3n, up to some constants {chung}. She conjectured that a permutation of n contains a k-modal (at most k changes in direction) subsequence of length at least √(2k+1)n up to some constants. Zijian Xu proved this conjecture in 2024 {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 √2kn.