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
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


Publisher files allowed on an open archive




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⟩



Record views


Files downloads