Large deviations for the longest alternating and the longest increasing subsequence in a random permutation avoiding a pattern of length three

2023/09/01 by Ross G. Pinsky, Pinsky, Ross G.
Computer Science · Mathematics · #60C05 #60F10 #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.2309.00365

openalex publication_date 2023/09/01 · openalex created_date 2023/09/05 · openalex updated_date 2026/07/28

Abstract

We calculate the large deviations for the length of the longest alternating subsequence and for the length of the longest increasing subsequence in a uniformly random permutation that avoids a pattern of length three. We treat all six patterns in the case of alternating subsequences. In the case of increasing subsequences, we treat two of the three patterns for which a classical large deviations result is possible. The same rate function appears in all six cases for alternating subsequences. This rate function is in fact the rate function for the large deviations of the sum of IID symmetric Bernoulli random variables. The same rate function appears in the two cases we treat for increasing subsequences. This rate function is twice the rate function for alternating subsequences.

Related

• On increasing subsequences of iid samples
• Large Deviations for Permutations Avoiding Monotone Patterns
• Mean and variance of the longest alternating subsequence in a random separable permutation
• On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation
• Longest subsequence for certain repeated up/down patterns in random permutations avoiding a pattern of length three