Return to Answer

The $N(n)$ is exponential in $n$. First, I present a lower bound. The construction is recursive. Call a sequence whose first differences are monotone, $1$-monotone. Suppose $\mathbf{a}=a_1,\dotsc,a_M$ is a sequence that contains no $1$-monotone $N$-term subsequence. Pick an number $R$ that is larger than $\max_{i,j}(a_i-a_j)$. Then the sequence $\mathbf{b}=a_1,\dotsc,a_M,a_1+R,\dotsc,a_M+R$ contains no $1$-monotone subsequence of length $N+1$. Indeed, the subsequence cannot contain $N$ elements from the same half of $\mathbf{b}$. Hence, it must contain at least $2$ elements from each of the halves, which is impossible by the choice of $R$.

The upper bound is also recursive. We will find a monotone increasing subsequence with a stronger property that either $a_i-a_1\leq a_{i+1}-a_i$ or $a_{last}-a_i\leq a_i-a_{i-1}$. Suppose we are given a sequence $\mathbf{a}$. We may assume that it is monotone increasing (by losing only a square, and reversing the sequence if necessary). Let $X$ be the median of $\mathbf{a}$. The median splits $\mathbf{a}$ into two equally long sequences $\mathbf{b}$ and $\mathbf{c}$. By induction we can find $1$-monotone subsequences $\mathbf{b}'$ and $\mathbf{c}'$ in $\mathbf{b}$ and $\mathbf{c}$ respectively. If $X-a_1\leq a_{last}-X$, then the concatenation of $\mathbf{b}'$ with $a_{last}$ is the desired sequence. If $X-a_1\geq a_{last}-X$ then the concatenation of $a_1$ with $\mathbf{c}'$ is a desired subsequence.

The $N(n)$ is exponential in $n$. First, I present a lower bound. The construction is recursive. Call a sequence whose first differences are monotone, $1$-monotone. Suppose $\mathbf{a}=a_1,\dotsc,a_M$ is a sequence that contains no $1$-monotone $N$-term subsequence. Pick an number $R$ that is larger than $\max_{i,j}(a_i-a_j)$. Then the sequence $\mathbf{b}=a_1,\dotsc,a_M,a_1+R,\dotsc,a_M+R$ contains no $1$-monotone subsequence of length $N+1$. Indeed, the subsequence cannot contain $N$ elements from the same half of $\mathbf{b}$. Hence, it must contain at least $2$ elements from each of the halves, which is impossible by the choice of $R$.

The upper bound is also recursive. We will find a monotone increasing subsequence with a stronger property that either $a_i-a_1\leq a_{i+1}-a_i$ (fast-increasing) or $a_{last}-a_i\leq a_i-a_{i-1}$ (fast-decreasing). It suffices to only work with the sequences that are monotone increasing (by losing only a square, and reversing the sequence if necessary). Let $N(I,D)$ be the length of the longest monotone sequence without a fast-increasing subsequence of length $I$, and without fast-decreasing subsequence of length $D$. I claim that $N(I,D)\leq N(I-1,D)+N(I,D-1)$ (and so $N(n,n)$ is bounded by an exponential function). Suppose $\mathbf{a}$ is a monotone increasing sequence. Let $X$ be the median of $\mathbf{a}$. The median splits $\mathbf{a}$ into two equally long sequences $\mathbf{b}$ and $\mathbf{c}$. By induction applied to $\mathbf{b}$ we can find either fast-increasing sequence of length $I-1$ or fast-decreasing sequence of length $D$. In the latter case, we are done. Else, let $\mathbf{b}'$ be the fast-increasing subsequence of $\mathbf{b}$. Similarly, there is $\mathbf{c}'$ in $\mathbf{c}$ that is fast-decreasing. If $X-a_1\leq a_{last}-X$, then the concatenation of $\mathbf{b}'$ with $a_{last}$ is the desired sequence. If $X-a_1\geq a_{last}-X$ then the concatenation of $a_1$ with $\mathbf{c}'$ is a desired subsequence.

The $N(n)$ is exponential in $n$. First, I present a lower bound. The construction is recursive. Call a sequence whose first differences are monotone, $1$-monotone. Suppose $\mathbf{a}=(a_1,\dotsc,a_N)$ is a sequence that contains no $1$-monotone $n$-term subsequence. Pick an number $R$ that is larger than $\max_{i,j}(a_i-a_j)$. Then the sequence $\mathbf{b}=(a_1,\dotsc,a_N,a_1+R,\dotsc,a_N+R)$ contains no $1$-monotone subsequence of length $n+1$. Indeed, the subsequence cannot contain $n$ elements from the same half of $\mathbf{b}$. Hence, it must contain at least $2$ elements from each of the halves, which is impossible by the choice of $R$.

The upper bound is also exponential. Suppose we are given a sequence $\mathbf{a}$. We may assume that it is monotone (by losing only a square). Then write $\mathbf{a}$ as a concatenation of two sequences $\mathbf{b}$ and $\mathbf{c}$. By induction we can find $1$-monotone subsequences $\mathbf{b}'$ and $\mathbf{c}'$ in $\mathbf{b}$ and $\mathbf{c}$ respectively. Then the concatenation of the last element of $\mathbf{c}$ with $\mathbf{b}'$, or the first element of $\mathbf{b}$ with $\mathbf{c}'$ is a desired subsequence.

The $N(n)$ is exponential in $n$. First, I present a lower bound. The construction is recursive. Call a sequence whose first differences are monotone, $1$-monotone. Suppose $\mathbf{a}=a_1,\dotsc,a_M$ is a sequence that contains no $1$-monotone $N$-term subsequence. Pick an number $R$ that is larger than $\max_{i,j}(a_i-a_j)$. Then the sequence $\mathbf{b}=a_1,\dotsc,a_M,a_1+R,\dotsc,a_M+R$ contains no $1$-monotone subsequence of length $N+1$. Indeed, the subsequence cannot contain $N$ elements from the same half of $\mathbf{b}$. Hence, it must contain at least $2$ elements from each of the halves, which is impossible by the choice of $R$.

The upper bound is also recursive. We will find a monotone increasing subsequence with a stronger property that either $a_i-a_1\leq a_{i+1}-a_i$ or $a_{last}-a_i\leq a_i-a_{i-1}$. Suppose we are given a sequence $\mathbf{a}$. We may assume that it is monotone increasing (by losing only a square, and reversing the sequence if necessary). Let $X$ be the median of $\mathbf{a}$. The median splits $\mathbf{a}$ into two equally long sequences $\mathbf{b}$ and $\mathbf{c}$. By induction we can find $1$-monotone subsequences $\mathbf{b}'$ and $\mathbf{c}'$ in $\mathbf{b}$ and $\mathbf{c}$ respectively. If $X-a_1\leq a_{last}-X$, then the concatenation of $\mathbf{b}'$ with $a_{last}$ is the desired sequence. If $X-a_1\geq a_{last}-X$ then the concatenation of $a_1$ with $\mathbf{c}'$ is a desired subsequence.

The $N(n)$ is exponential in $n$. First, I present a lower bound. The construction is recursive. Call a sequence whose first differences are monotone, $1$-monotone. Suppose $\mathbf{a}=a_1,\dotsc,a_M$ is a sequence that contains no $1$-monotone $N$-term subsequence. Pick an number $R$ that is larger than $\max_{i,j}(a_i-a_j)$. Then the sequence $\mathbf{b}=a_1,\dotsc,a_M,a_1+R,\dotsc,a_M+R$ contains no $1$-monotone subsequence of length $N+1$. Indeed, the subsequence cannot contain $N$ elements from the same half of $\mathbf{b}$. Hence, it must contain at least $2$ elements from each of the halves, which is impossible by the choice of $R$.

The upper bound is also recursive. Suppose we are given a sequence $\mathbf{a}$. We may assume that it is monotone (by losing only a square). Then write $\mathbf{a}$ as a concatenation of two sequences $\mathbf{b}$ and $\mathbf{c}$. By induction we can find $1$-monotone subsequences $\mathbf{b}'$ and $\mathbf{c}'$ in $\mathbf{b}$ and $\mathbf{c}$ respectively. Then the concatenation of the last element of $\mathbf{c}$ with $\mathbf{b}'$, or the first element of $\mathbf{b}$ with $\mathbf{c}'$ is a desired subsequence.

The $N(n)$ is exponential in $n$. First, I present a lower bound. The construction is recursive. Call a sequence whose first differences are monotone, $1$-monotone. Suppose $\mathbf{a}=(a_1,\dotsc,a_N)$ is a sequence that contains no $1$-monotone $n$-term subsequence. Pick an number $R$ that is larger than $\max_{i,j}(a_i-a_j)$. Then the sequence $\mathbf{b}=(a_1,\dotsc,a_N,a_1+R,\dotsc,a_N+R)$ contains no $1$-monotone subsequence of length $n+1$. Indeed, the subsequence cannot contain $n$ elements from the same half of $\mathbf{b}$. Hence, it must contain at least $2$ elements from each of the halves, which is impossible by the choice of $R$.

The upper bound is also exponential. Suppose we are given a sequence $\mathbf{a}$. We may assume that it is monotone (by losing only a square). Then write $\mathbf{a}$ as a concatenation of two sequences $\mathbf{b}$ and $\mathbf{c}$. By induction we can find $1$-monotone subsequences $\mathbf{b}'$ and $\mathbf{c}'$ in $\mathbf{b}$ and $\mathbf{c}$ respectively. Then the concatenation of the last element of $\mathbf{c}$ with $\mathbf{b}'$, or the first element of $\mathbf{b}$ with $\mathbf{c}'$ is a desired subsequence.