Permutations avoiding 312 and another pattern, Chebyshev polynomials and longest increasing subsequences

Abstract

We study the longest increasing subsequence problem for random permutations avoiding the pattern $312$ and another pattern $\tau$ under the uniform probability distribution. We determine the exact and asymptotic formulas for the average length of the longest increasing subsequences for such permutation classes specifically when the pattern $\tau$ is monotone increasing or decreasing, or any pattern of length four.

arXiv comment14 pages, 1 table, Lemma 2.1 added, some additions and minor corrections made

References in corpus (9)

• Level-Spacing Distributions and the Airy Kernel
• Level-Spacing Distributions and the Airy Kernel
• Universality for mathematical and physical systems
• Longest increasing subsequences in pattern-restricted permutations
• Patterns in random permutations avoiding the pattern 132
• Fixed points of 321-avoiding permutations
• Increasing subsequences of random walks
• Comments on David Aldous and Persi Diaconis' "Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem"
• Asymptotic distribution of fixed points of pattern-avoiding involutions

Cited by in corpus (3)

• Square permutations are typically rectangular
• Scaling limits of permutations avoiding long decreasing sequences
• Variations on Hammersley's interacting particle process