Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Fix natural numbers $k,n$, with $k<n$. 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.

share|improve this question
    
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 subject –  Yao Wang Feb 15 '12 at 3:23
    
I think you mean the Robinson-Schensted correspondence. –  Marc van Leeuwen Feb 15 '12 at 12:42
    
Yeah,you are right. Thanks for comment. Any related research would be precious. –  Yao Wang Feb 16 '12 at 20:18
    
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. –  Marc van Leeuwen Feb 18 '12 at 9:57
    
@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. –  Yao Wang Feb 21 '12 at 6:38

1 Answer 1

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<n\leq k^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.

share|improve this answer
    
Thanks 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 –  Yao Wang Feb 17 '12 at 19:25
    
d。Maybe I should show a case that what will happen when n becomes larger than $(k-1)^2+1$ –  Yao Wang Feb 17 '12 at 19:32
    
still, 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]( –  Yao Wang Feb 17 '12 at 19:41
    
A paper by Dan romic containing your result can be found here (sciencedirect.com/science/article/pii/S0196885806000583) –  Yao Wang Feb 17 '12 at 19:45
    
I'm sorry, I just can't figure out what you are asking. –  Marc van Leeuwen Feb 18 '12 at 9:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.