Longest increasing subsequences in pattern-restricted permutations
Summary: Inspired by the results of \textit{J. Baik, P. Deift} and \textit{K. Johansson} [J. Am. Math. Soc. 12, 1119-1178 (1999; Zbl 0932.05001)] 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 \textit{P. Erdős} and \textit{G. Szekeres} [Compos. Math. 2, 463-470 (1935; Zbl 0012.27010 and JFM 61.0651.04)].
- Longest alternating subsequences in pattern-restricted permutations
- On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation
- Permutations avoiding 312 and another pattern, Chebyshev polynomials and longest increasing subsequences
- On the distribution of the length of the longest increasing subsequence of random permutations
- Longest increasing subsequences in involutions avoiding patterns of length three
- Longest increasing subsequences of random colored permutations
- Avoiding patterns and making the best choice
- The feasible regions for consecutive patterns of pattern-avoiding permutations
- Pattern avoiding permutations with a unique longest increasing subsequence
- Strategy-indifferent games of best choice
- Permutations avoiding 312 and another pattern, Chebyshev polynomials and longest increasing subsequences
- Longest alternating subsequences in pattern-restricted permutations
- Longest monotone subsequences and rare regions of pattern-avoiding permutations
- Longest alternating subsequences of \(k\)-ary words
- Inversions and longest increasing subsequence for \(k\)-card-minimum random permutations
- The Preisach graph and longest increasing subsequences
- The surprising mathematics of longest increasing subsequences
- Enumerating longest increasing subsequences and patience sorting
- On three different notions of monotone subsequences
- Edit distance between unlabeled ordered trees
- The Longest Almost-Increasing Subsequence
- The shape of random pattern-avoiding permutations
- Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
- Commentary on ``Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem by David Aldous and Persi Diaconis
- Monotone subsets in lattices and the Schensted shape of a Sós permutation
- Longest increasing subsequences in involutions avoiding patterns of length three
- Longest Increasing Subsequences of Randomly Chosen Multi-Row Arrays
- On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation
- Refined sign-balance on 321-avoiding permutations
- Pattern-avoiding permutations and Brownian excursion. I: Shapes and fluctuations.
- Bijections for refined restricted permutations
- Power-law bounds for increasing subsequences in Brownian separable permutons and homogeneous sets in Brownian cographons
- Unique longest increasing subsequences in 132-avoiding permutations
- Large deviations for the longest alternating and the longest increasing subsequence in a random permutation avoiding a pattern of length three
- A Galton-Watson tree approach to local limits of permutations avoiding a pattern of length three
- Longest subsequence for certain repeated up/down patterns in random permutations avoiding a pattern of length three
- Permutations with short monotone subsequences
This page was built for publication: Longest increasing subsequences in pattern-restricted permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1871367)
