On the number of monotone sequences

Abstract

One of the most classical results in Ramsey theory is the theorem of Erdős and Szekeres from 1935, which says that every sequence of more than $k^2$ numbers contains a monotone subsequence of length $k+1$. We address the following natural question motivated by this result: Given integers $k$ and $n$ with $n\ge k^2+1$, how many monotone subsequences of length $k+1$ must every sequence of $n$ numbers contain? We answer this question precisely for all sufficiently large $k$ and $n\le k^2+c{k}^{3/2}/\log k$, where $c$ is some absolute positive constant.

24 pages, 2 figures

References in corpus (1)

• Minimum number of monotone subsequences of length 4 in permutations

Cited by in corpus (1)

• Minimum number of monotone subsequences of length 4 in permutations