On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation

DOI10.1002/RSA.20140MaRDI QIDQ5433259zbMATH OpenOpenAlexFDO

Authors Michael Albert

Publication date 8 January 2008

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0505485

zbMATH Keywords

distributionStanley-Wilf limit

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial probability (60C05)

Abstract: We consider the distribution of the length of the longest subsequence avoiding a given pattern in a random permutation of length n. The well-studied case of a longest increasing subsequence corresponds to avoiding the pattern 21. We show that there is some constant c such that the mean value of this length is asymptotic to twice the square root of c times n and that the distribution of the length is tightly concentrated around its mean. We observe some apparent connections between c and the Stanley-Wilf limit of the class of permutations avoiding the given pattern.

Recommendations

• Longest increasing subsequences in pattern-restricted permutations
• Longest alternating subsequences in pattern-restricted permutations
• Permutations avoiding 312 and another pattern, Chebyshev polynomials and longest increasing subsequences
• Longest monotone subsequences and rare regions of pattern-avoiding permutations
• scientific article; zbMATH DE number 1047715

Cites work

• Longest Increasing and Decreasing Subsequences
• Restricted permutations

Cited in

(19)

• Longest increasing subsequences in pattern-restricted permutations
• On the growth of merges and staircases of permutation classes
• Lower bounds for superpatterns and universal sequences
• Permutations avoiding 312 and another pattern, Chebyshev polynomials and longest increasing subsequences
• Average length of the longest \(k\)-alternating subsequence
• Longest alternating subsequences in pattern-restricted permutations
• Longest monotone subsequences and rare regions of pattern-avoiding permutations
• Unsplittable classes of separable permutations
• PERMUTATION CLASSES OF EVERY GROWTH RATE ABOVE 2.48188
• On the longest common pattern contained in two or more random permutations
• Growing at a perfect speed
• scientific article; zbMATH DE number 1515819 (Why is no real title available?)
• Generalized Coloring of Permutations
• Variations on Hammersley’s interacting particle process
• scientific article; zbMATH DE number 7250398 (Why is no real title available?)
• Generalized coloring of 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
• Descending subsequences of random permutations

This page was built for publication: On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5433259)