2
$\begingroup$

Fix natural numbers $k,n$, with $k. I want to find a permutation in $S_n$ that contains fewest monotone (increasing or decreasing) subsequences of length $k$.

For example the permutation 45123 contains only $1$ monotone subsequence of length $3$ (namely 123), so it is a minimal case for $k =3$, $n=5$: any permutation of length $5$ contains at least one monotone subsequence of length $3$ by the Erdős-Szekeres theorem.

Problem 1 Can we find such permutation when $n$ becomes very large with respect to $k$?

Problem 2 Moreover can we calculate their proportion in $S_n$?

By "$n$ is very large", I mean $n>\mathrm{poly}(k)$

For example for 3 monotone subsequence (the following result lacks rigorous proof)
The 123456, 1234567 and 12345678 are trivial maximal cases as they contain ${n \choose 3}$ monotone sequence at length $3$

  • when $n=6$ one of the minimal cases is 321654 containing $2$ monotone subsequences of length $3$. They are 321 and 654.

  • when $n=7$ one of the seeming minimal cases is 4321765 containing $5$ monotone subsequences of length $3$ They are 432 431 421 321 and 765.

  • when $n=8$ one of the seeming minimal cases is 43218765 containing $8$ monotone subsequences of length $3$ They are 432 431 421 321 765 876 875 and 865.

What are the minimal cases when $n>8$? Can we explicitly give the minimal case and give the number of monotone subsequence $k$ contained in the minimal case ?


If possible, I hope we can specialize the solution to some fixed position in the permutation. Suppose the 1st 3rd 5th 7th number of a permutation consists of a monotone sequence,can we design a minima permutation for such condition?

Hope you have some idea for this problem.

Observe that the extremal Erdős-Szekeres cases have a zero proportional compared to $n!$ when $n$ becomes infinite.

  • 0
    @Marc van Leeuwen The minimal case mentioned is the permutation $S_n$ itself.The \emph{number} of monotone subsequence at length 3 matters, not the \emph{length} of the longest monotone subsequence. I call the my examples as minimal case for they \emph{have fewest monotone sequence at length \mathbf{3},not at other length such as$4$or 5 }. Maybe my english is not pretty enough to describe my question.2012-02-21

1 Answers 1

2

The question is not very clear what it means by a minimum case for 3-monotone sequence; it seems that it means this is a case where the longest monotone sequence is as short as it can be: no permutation of $5$ has only monotone sequences of length${}<3$. By the Erdős–Szekeres theorem, whenever $n>(k-1)^2$ every permutation of $n$ has at least one monotone sequence of length $k$.

In fact for every $n$ with $(k-1)^2, one can find all permutations for which the maximal length monotone subsequences are of length $k$ by first forming all the partitions $\lambda$ of $n$ into at most $k$ parts of size at most $k$, for each such $\lambda$ take all pairs of standard Young tableaux $P,Q$ of shape $\lambda$, and apply the inverse Schensted correspondence ot $(P,Q)$. This gives quite a lot of permutations, but I would not be surprised if their proportion of all $n!$ permutations nevertheless goes to $0$ as $n\to\infty$ (probabilists almost certainly know the answer to this question;-).

As for permutations where the maximal length monotone subsequence is both minimal and unique, these are of course much more rare, and certainly don't exist for every $n$. However they do exist for $n=k^2+1$, where one has $\begin{align} (&k,k-1,\ldots,1\\ ,&2k,2k-1\ldots,k+1\\,&3k,\ldots,2k+1\\ &\ldots\\,&k^2-k,\ldots,(k-1)k+1\\ ,& k^2+1,k^2,k^2-1,\ldots k^2-k+1)\end{align} $ whose unique monotone subsequence of length $k+1$ is formed by its final portion.

  • 0
    I'm sorry, I just can't figure out what you are asking.2012-02-18