zbMATH — the first resource for mathematics

Permutations with short monotone subsequences. (English) Zbl 1109.05015
Summary: We consider permutations of \(1,2,\dots ,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, and other properties of these extremal permutations.

05A05 Permutations, words, matrices
Full Text: DOI
[1] Edelman, P.H.; Greene, C., Balanced tableaux, Adv. math., 63, 42-99, (1987) · Zbl 0616.05005
[2] Knuth, D.E., The art of computer programming, vol. 3: sorting and searching, (1998), Addison-Wesley
[3] B.G. Pittel, D. Romik, Limit shapes for random square Young tableaux, Adv. in Appl. Math., in press · Zbl 1122.60009
[4] Romik, D., The number of steps in the robinson – schensted algorithm, Funct. anal. appl., 39, 152-155, (2005) · Zbl 1117.05006
[5] Stanley, R.P., Enumerative combinatorics, vol. 2, (1999), Cambridge Univ. Press · Zbl 0928.05001
[6] R.P. Stanley, Private communication, 2005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.