Geodesic
Permutations with short monotone subsequences
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005).

Voir la notice de l'article provenant de la source Episciences

We consider permutations of $1,2,...,n^2$ whose longest monotone subsequence is of length $n$ and are therefore extremal for the Erdős-Szekeres Theorem. Such permutations correspond via the Robinson-Schensted correspondence to pairs of square $n \times n$ Young tableaux. We show that all the bumping sequences are constant and therefore these permutations have a simple description in terms of the pair of square tableaux. We deduce a limit shape result for the plot of values of the typical such permutation, which in particular implies that the first value taken by such a permutation is with high probability $(1+o(1))n^2/2$. 
@article{DMTCS_2005_special_250_a30,
     author = {Romik, Dan},
     title = {Permutations with short monotone subsequences},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
     year = {2005},
     doi = {10.46298/dmtcs.3421},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3421/}
}
TY  - JOUR
AU  - Romik, Dan
TI  - Permutations with short monotone subsequences
JO  - Discrete mathematics & theoretical computer science
PY  - 2005
VL  - DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3421/
DO  - 10.46298/dmtcs.3421
LA  - en
ID  - DMTCS_2005_special_250_a30
ER  - 
%0 Journal Article
%A Romik, Dan
%T Permutations with short monotone subsequences
%J Discrete mathematics & theoretical computer science
%D 2005
%V DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3421/
%R 10.46298/dmtcs.3421
%G en
%F DMTCS_2005_special_250_a30
Romik, Dan. Permutations with short monotone subsequences. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005). doi : 10.46298/dmtcs.3421. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3421/

Cité par Sources :