Large Deviations for Permutations Avoiding Monotone Patterns

2016/06/25 by Madras, Neal, Pehlivan, Lerna
#05A05 (Primary) 60C05 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1606.07906

Abstract

For a given permutation τ, let P_N^τ be the uniform probability distribution on the set of N-element permutations σ that avoid the pattern τ. For τ=μ_k:=123⋯ k, we consider P_N^μ_k(σ_I=J) where I∼ γN and J∼ δN for γ,δ∈ (0,1). If γ+δ≠ 1 then we are in the large deviations regime with the probability decaying exponentially, and we calculate the limiting value of P_N^μ_k(σ_I=J)^1/N. We also observe that for τ= λ_k,ℓ := 12…ℓ k(k-1)…(ℓ+1) and γ+δ<1, the limit of P_N^τ(σ_I=J)^1/N is the same as for τ=μ_k.

Related

• Large deviations for the longest alternating and the longest increasing subsequence in a random permutation avoiding a pattern of length three
• Large deviation principle for random permutations
• Sharp Large Deviations for the Number of Descents and the Major Index in a Random Permutation
• The order of large random permutations with cycle weights
• About universality of large deviation principles for conjugacy invariant permutations