1. On $k$-modal subsequences
- Author
-
Xu, Zijian
- Subjects
Mathematics - Combinatorics ,05D10 - Abstract
A $k$-modal sequence is a sequence of real numbers that can be partitioned into $k+1$ (possibly empty) monotone sections such that adjacent sections have opposite monotonicities. For every positive integer $k$, we prove that any sequence of $n$ pairwise distinct real numbers contains a $k$-modal subsequence of length at least $\sqrt{(2k+1)(n-\frac14)} - \frac{k}{2}$, which is tight in a strong sense. This confirms an old conjecture of F.R.K.Chung (J.Combin.Theory Ser.A, 29(3):267-279, 1980)., Comment: 20 pages, 2 figures
- Published
- 2024