Dan Romik - Permutations with short monotone subsequences

dmtcs:3421 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3421
Permutations with short monotone subsequences

Authors: Dan Romik 1

  • 1 Mathematical Sciences Research Institute

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


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: Robinson-Schensted correspondence,Erdős-Szekeres theorem,limit shape,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV 1511.01076
Source : ScholeXplorer IsRelatedTo DOI 10.46298/dmtcs.1328
  • 1511.01076
  • 10.46298/dmtcs.1328
  • 10.46298/dmtcs.1328
An Erd\H{o}s--Hajnal analogue for permutation classes

Consultation statistics

This page has been seen 130 times.
This article's PDF has been downloaded 153 times.