Fix natural numbers $k,n$, with $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 are321
and654
.when $n=7$ one of the seeming minimal cases is
4321765
containing $5$ monotone subsequences of length $3$ They are432
431
421
321
and765
.when $n=8$ one of the seeming minimal cases is
43218765
containing $8$ monotone subsequences of length $3$ They are432
431
421
321
765
876
875
and865
.
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.