MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

5 added 101 characters in body

The classical Erdős-Szekeres theorem says that any sequence of $n^2+1$ real numbers contains a monotonic $(n+1)$-term subsequence. Suppose, however, that we want to find a subsequence which is not necessarily monotonic itself, but has the sequence of its first differences monotonic. How long has the original sequence to be to ensure that such an $(n+1)$-term subsequence can be found?

For positive integer $n$, what is the smallest integer $N=N(n)$ such that every $N$-element sequence of real numbers contains an $n$-element subsequence $(a_1,\ldots,a_n)$ with either $a_2-a_1\le\dotsb\le a_n-a_{n-1}$, or $a_2-a_1\ge\dotsb\ge a_n-a_{n-1}$?

Trivially, we have $N(1)=1$, $N(2)=2$, and $N(3)=3$. However, I do not know the value of $N(4)$.

The state of the art as of 05.03.12. The nice argument of Boris Bukh (below) shows that $N(n)$ is exponential in $n$. Still, this does not completely settle the problem.

Updated 16.03.12: the absolutely beautiful, must-upvote solution by Sergey Norin is posted below.

4 added 182 characters in body

The classical Erdős-Szekeres theorem says that any sequence of $n^2+1$ real numbers contains a monotonic $(n+1)$-term subsequence. Suppose, however, that we want to find a subsequence which is not necessarily monotonic itself, but has the sequence of its first differences monotonic. How long has the original sequence to be to ensure that such an $(n+1)$-term subsequence can be found?

For positive integer $n$, what is the smallest integer $N=N(n)$ such that every $N$-element sequence of real numbers contains an $n$-element subsequence $(a_1,\ldots,a_n)$ with either $a_2-a_1\le\dotsb\le a_n-a_{n-1}$, or $a_2-a_1\ge\dotsb\ge a_n-a_{n-1}$?

Trivially, we have $N(1)=1$, $N(2)=2$, and $N(3)=3$. However, I do not know the value of $N(4)$.

The state of the art as of 05.03.12. The nice argument of Boris Bukh (below) shows that $N(n)$ is exponential in $n$. Still, this does not completely settle the problem.

3 deleted 2 characters in body

The classical Erdős-Szekeres theorem says that any sequence of $n^2+1$ real numbers contains a monotonic $n$-term (n+1)$-term subsequence. Suppose, however, that we want to find an$n$-term a subsequence which is not necessarily monotonic itself, but has the sequence of its first differences monotonic. How long has the original sequence to be to ensure that such an$n$-term (n+1)$-term subsequence can be found?

For positive integer $n$, what is the smallest integer $N=N(n)$ such that every $N$-element sequence of real numbers contains an $n$-element subsequence $(a_1,\ldots,a_n)$ with either $a_2-a_1\le\dotsb\le a_n-a_{n-1}$, or $a_2-a_1\ge\dotsb\ge a_n-a_{n-1}$?

Trivially, we have $N(1)=1$, $N(2)=2$, and $N(3)=3$. However, I do not know the value of $N(4)$.

2 edited title
1