On increasing subsequences of iid samples

1998/03/10 by J. D. Deuschel, Deuschel, J. D., Ofer Zeitouni +2
Computer Science · Mathematics · #60F10 #60G70 #Bayesian Methods and Mixture Models #FOS: Mathematics #Probability (math.PR) #Random Matrices and Applications #Stochastic processes and statistical mechanics #math.PR #msc:60F10 #msc:60G70

paper · pdf · doi:10.48550/arxiv.math/9803035

16 pages

arxiv created 1998/03/10 · openalex publication_date 1998/03/10 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the fluctuations, in the large deviations regime, of the longest increasing subsequence of a random i.i.d. sample on the unit square. In particular, our results yield the precise upper and lower exponential tails for the length of the longest increasing subsequence of a random permutation.

Related

• Asymptotics of the Longest Increasing Subsequence in Random Permutations
• Large deviations for the longest alternating and the longest increasing subsequence in a random permutation avoiding a pattern of length three
• The longest increasing subsequence in involutions avoiding 3412 and another pattern
• 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