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

  • HAL Id : hal-01184378, version 1

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. ⟨hal-01184378⟩

Share

Metrics

Record views

332

Files downloads

677