Longest increasing subsequences in pattern-restricted permutations

Abstract

Inspired by the results of Baik, Deift and Johansson on the limiting distribution of the lengths of the longest increasing subsequences in random permutations, we find those limiting distributions for pattern-restricted permutations in which the pattern is any one of the six patterns of length 3. We show that the (132)-avoiding case is identical to the distribution of heights of ordered trees, and that the (321)-avoiding case has interesting connections with a well known theorem of Erd\H os-Szekeres.

9 pages

Cited by in corpus (6)

• Patterns in random permutations avoiding the pattern 132
• Random walk generated by random permutations of {1,2,3, ..., n+1}
• Permutations avoiding 312 and another pattern, Chebyshev polynomials and longest increasing subsequences
• Positional strategies in games of best choice
• The Shape of Random Pattern-Avoiding Permutations
• Multiple pattern avoidance with respect to fixed points and excedances