Existence / non-existence of a sequence with short longest increasing subsequence and decreasing subsequence?

Question

Can there exist any integer sequence $A$ of length $N$ with all unique elements such that the length of its Longest Increasing Subsequence as well as that of its Longest Decreasing Subsequence is less than $ \displaystyle \lfloor \frac{N}{2} \rfloor $?

If yes, then give an example of such a sequence. Otherwise, can anyone present a proof that there cannot exist such a sequence?

(Just to add some substance, can it be shown there can exist such sequences, given any arbitrary value of $ N > 1 $?)

Answer 1

The answer to the OP's question is, no if $N\le 7$ and yes otherwise.

---

For given any positive integer $r$ and $s$, the celebrated Erdős–Szekeres theorem shows that for any sequence of distinct real numbers with length at least $(r − 1)(s − 1) + 1$ contains an increasing subsequence of length $r$ or a decreasing subsequence of length $s$.

It turns out that bound, $(r-1)(s-1)+1$ is tight. That is, for any positive number $r$ and $s$, there is a sequence of distinct numbers with length $(r-1)(s-1)$ that contains no increasing subsequence of length $r$ and no decreasing subsequence of length $s$.

Here is such an example.

$$\begin{array} {} &s-1, &s-2, &\cdots,&2, &1\\ &2(s-1), &(s-1)+ s-2, &\cdots, &(s-1)+ 2, &(s-1)+ 1\\ &\vdots &\vdots &\vdots &\vdots &\vdots \\ &(r-2)(s-1), &(r-3)(s-1)+s-2, &\cdots, &(r-3)(s-1)+2, &(r-3)(s-1)+1\\ &(r-1)(s-1), &(r-2)(s-1)+s-2, &\cdots, &(r-2)(s-1)+2, &(r-2)(s-1)+1\\ \end{array}$$

Consider the numbers above, reading from left to right and then from top to bottom. In other words, the sequence is $s-1$ down to $1$, followed by $2(s-1)$ down to $(s-1)+1$, etc and finally followed by $(r-1)(s-1)$ down to $(r-2)(s-1)+1$, all in step of $1$.

It is easy to see that there is no increasing subsequence of length r and no decreasing subsequence of length $s$.

For example, when $r=s=5$, we have $$4,3,2,1,\ \, 8,7,6,5,\ \,12,11,10,9,\ \,16,15,14,13$$ which does not have increasing subsequence of length $5$ nor decreasing subsequence of length $5$.

---

If we let $r=s$, the section above implies that, for any positive number $N$, there exists an integer sequence of length $N$ with all unique elements such that the length of its longest increasing subsequence as well as that of its longest decreasing subsequence is at most $\lceil\sqrt N\rceil$. And $\lceil\sqrt N\rceil$ is the tight upper bound.

Since $$\lceil\sqrt N\rceil\ge \lfloor\frac N2\rfloor\ \text{ for all } N\le 7$$ and $$\lceil\sqrt N\rceil\lt \lfloor\frac N2\rfloor\ \text{ for all } N\gt 7,$$ the answer to the OP's question is, no if $N\le 7$ and yes otherwise.

For example, for $N=8$, we have sequence $3,2,1,6,5,4,9,8,7$.

Answer 2

Here's a direct construction of such a sequence for any multiple of four. It's made up of four equally sized runs of consecutive integers.

The first and third runs are increasing. The second and fourth runs are decreasing. The runs use ranges of numbers such that $R_2 < R_3 < R_1 < R_4$. For example, with $4n=16$,

$$ 9,10,11,12 |4,3,2,1|5,6,7,8|16, 15,14,13 $$

The longest increasing subsequence is length $n+2$. For example, in the above where $4n=16$, the longest increasing subsequence has length $6$ ($1| 5, 6, 7, 8|16$). No increasing subsequence is longer:

• It's not possible to pick an element from both increasing runs, since any element in the first increasing run disqualifies all of them from the second increasing run.
• It's not possible to pick more than one element from either decreasing run

A symmetric argument applies for the decreasing subsequences.

Since $n+2 << 2n$, this works as a counterexample for any multiple-of-four sequence. You can easily pad with extra sequence elements for non-multiple-of-four lengths.

I came across this construction by considering a sequence that was a "hill" (increasing, then decreasing), which meets your condition perfectly. Breaking up those long runs could be done making two hills (increasing, decreasing, increasing, decreasing), which this sequence does by ensuring the up/down slope of one 'hill' isn't continued by the other.

Answer 3

There are also short sequences that satisfy your request. Consider for example the first 16 terms of the binary Van der Corput sequence $$ 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15. $$ In general there exists a sequence $T$ of length $n\geq1$ containing a longest increasing subsequence of length $x\geq 1$ and a longest decreasing subsequence of length $y\geq 1$ if and only if the numbers $x$, $y$ and $n$ satisfy the conditions $x\cdot y\geq n$ and $x+y\leq n+1$, see here. Notice that the reference gives a constructive proof.

Answer 4

Such sequences do exist. It suffices to generate a large enough random sequence. If you check Dan Romik's book, The Surprising Mathematics of Longest Increasing Subsequences, Theorem 1.1 states that

$$\frac {\ell_n} {\sqrt n} \to 2,$$

where $\ell_n$ is an expected length of increasing subsequence in a random permutation of size $n$. The same for decreasing. Therefore, for large enough $n$ there must exist a sequence with both increasing and decreasing sequences of lengths at most $5 \sqrt n$, otherwise:

$$2 E[\ell_n] = E[|decr_n| + |incr_n|] \ge 5 \sqrt n,$$

which contradicts the theorem.