On Increasing Subsequences of I.I.D. Samples
Jean‐Dominique Deuschel, Ofer Zeitouni · Combinatorics Probability Computing · 1999
We study the fluctuations, in the large deviations regime, of the longest increasing sub-sequence 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.