Longest increasing subsequences in pattern-restricted permutations
From MaRDI portal
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 ErdH os-Szekeres.
Recommendations
- 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
Cited in
(30)- The shape of random pattern-avoiding permutations
- On three different notions of monotone subsequences
- Pattern avoiding permutations with a unique longest increasing subsequence
- Strategy-indifferent games of best choice
- Bijections for refined restricted permutations
- Pattern-avoiding permutations and Brownian excursion. I: Shapes and fluctuations.
- The Longest Almost-Increasing Subsequence
- Longest monotone subsequences and rare regions of pattern-avoiding permutations
- Avoiding patterns and making the best choice
- Longest Increasing Subsequences of Randomly Chosen Multi-Row Arrays
- Unique longest increasing subsequences in 132-avoiding permutations
- Enumerating longest increasing subsequences and patience sorting
- Large deviations for the longest alternating and the longest increasing subsequence in a random permutation avoiding a pattern of length three
- Refined sign-balance on 321-avoiding permutations
- A Galton-Watson tree approach to local limits of permutations avoiding a pattern of length three
- Permutations with short monotone subsequences
- The feasible regions for consecutive patterns of pattern-avoiding permutations
- Monotone subsets in lattices and the Schensted shape of a Sós permutation
- Commentary on ``Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem by David Aldous and Persi Diaconis
- Inversions and longest increasing subsequence for \(k\)-card-minimum random permutations
- Longest alternating subsequences in pattern-restricted permutations
- Longest alternating subsequences of \(k\)-ary words
- Longest increasing subsequences in involutions avoiding patterns of length three
- Permutations avoiding 312 and another pattern, Chebyshev polynomials and longest increasing subsequences
- The surprising mathematics of longest increasing subsequences
- The Preisach graph and longest increasing subsequences
- On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation
- Longest increasing subsequences of random colored permutations
- Edit distance between unlabeled ordered trees
- Power-law bounds for increasing subsequences in Brownian separable permutons and homogeneous sets in Brownian cographons
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)
