Skip to Main content Skip to Navigation
Conference papers

Permutations with short monotone subsequences

Abstract : 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$.
Complete list of metadata

Cited literature [3 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184378
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Friday, August 14, 2015 - 11:38:29 AM
Last modification on : Saturday, December 8, 2018 - 2:16:01 PM
Long-term archiving on: : Sunday, November 15, 2015 - 11:03:52 AM

File

dmAE0112.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Dan Romik. Permutations with short monotone subsequences. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.57-62, ⟨10.46298/dmtcs.3421⟩. ⟨hal-01184378⟩

Share

Metrics

Record views

70

Files downloads

350