2
$\begingroup$

Fix natural numbers $k,n$, with $k$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
    Since we know that the Robinson Stone Correspondence from permutations to Young Tableau. How can the structure of Young Tableau can help us on this subject2012-02-15
  • 0
    I think you mean the Robinson-Schensted correspondence.2012-02-15
  • 0
    Yeah,you are right. Thanks for comment. Any related research would be precious.2012-02-16
  • 0
    Your cases $n=7,8$ are certainly not minimal; up to $n=9$ one can avoid monotone sequences of length $4$, for instance $321654978$ or $741852963$. Also _please state a precise question_.2012-02-18
  • 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