Fix natural numbers $k,n$, with $k For example the permutation 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) when $n=6$ one of the minimal cases is when $n=7$ one of the seeming minimal cases is when $n=8$ one of the seeming minimal cases is 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. 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.
The 123456, 1234567 and 12345678 are trivial maximal cases as they contain ${n \choose 3}$ monotone sequence at length $3$
321654 containing $2$ monotone subsequences of length $3$. They are 321 and 654.4321765 containing $5$ monotone subsequences of length $3$ They are 432 431 421 321 and 765.43218765 containing $8$ monotone subsequences of length $3$ They are 432 431 421 321 765 876 875 and 865.
Algorithm to find a permutation that contains the fewest possible monotone subsequences of length $k$
-
0Since we know that the Robinson Stone Correspondence from permutations to Young Tableau. How can the structure of Young Tableau can help us on this subject – 2012-02-15
-
0I think you mean the Robinson-Schensted correspondence. – 2012-02-15
-
0Yeah,you are right. Thanks for comment. Any related research would be precious. – 2012-02-16
-
0Your 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
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
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.
-
0Thanks for your answer very much. But as we know the Erdos Szekeres cases. I mean when n is very large,i.e. $n> k^k $. Thus, inevitably many monotone sequence appeared – 2012-02-17
-
0d。Maybe I should show a case that what will happen when n becomes larger than $(k-1)^2+1$ – 2012-02-17
-
0still, I am new here and your response seems it deserve some effort. There is a paper about building and counting the minimal case containing your result can be found [here]( – 2012-02-17
-
0A paper by Dan romic containing your result can be found here (http://www.sciencedirect.com/science/article/pii/S0196885806000583) – 2012-02-17
-
0I'm sorry, I just can't figure out what you are asking. – 2012-02-18