DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

Permutations with short monotone subsequences

Dan Romik


We consider permutations of 1,2,...,n2 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× 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))n2/2.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional