On the Distribution of the Length of the Longest Increasing Subsequence of Random Permutations

1998/10/31 by Jinho Baik, Percy Deift, Kurt Johansson · 17 citations
Mathematics · Physics and Astronomy · #math.CO #math-ph #math.MP #nlin.SI #solv-int #msc:05A05 #msc:15A52 #msc:33D45 #msc:45E05 #msc:60F99

paper · pdf

published as J. Amer. Math. Soc. 12 (1999), no. 4, 1119--1178 · 60 pages, 14 figures, AMS-LaTeX, typo correstions, new references

arxiv created 1999/03/26 · arxiv updated 2009/11/30

Abstract

The authors consider the length, l_N, of the length of the longest increasing subsequence of a random permutation of N numbers. The main result in this paper is a proof that the distribution function for l_N, suitably centered and scaled, converges to the Tracy-Widom distribution [TW1] of the largest eigenvalue of a random GUE matrix. The authors also prove convergence of moments. The proof is based on the steepest decent method for Riemann-Hilbert problems, introduced by Deift and Zhou in 1993 [DZ1] in the context of integrable systems. The applicability of the Riemann-Hilbert technique depends, in turn, on the determinantal formula of Gessel [Ge] for the Poissonization of the distribution function of l_N.

Cited by

• Asymptotics of the Longest Increasing Subsequence in Random Permutations
• A note on the distribution of the sum of lengths of the initial longest increasing sequences in cycles of random permutations
• Sum rules via large deviations: polynomial potentials and multi-cut regime on the unit circle
• Improved universality bounds for directed polymers in the intermediate disorder regime
• Derangement permutation matrices and orbit harmonics
• Quantitative Brownian regularity of the KPZ fixed point with arbitrary initial data
• Radon-Nikodym derivative of inhomogeneous Brownian last passage percolation
• A Riemann-Hilbert Approach to Asymptotic Analysis of Toeplitz+Hankel Determinants II
• Asymptotics of Jack measures with homogeneous specializations
• Multipoint distributions of the KPZ fixed point with compactly supported initial conditions
• Higher order linear differential equations for unitary matrix integrals: applications and generalisations
• On the multipoint distribution formulas of the parabolic Airy process
• Last passage percolation in lower triangular domain
• Dynamic scaling of growing interfaces
• Discrete and Continuous Muttalib--Borodin Process: Large Deviations and Limit Shape Analysis
• Asymptotics of the partition function of the perturbed Gross-Witten-Wadia unitary matrix model
• On two conjectures about pattern avoidance of cyclic permutations

Related

• Asymptotics of the Longest Increasing Subsequence in Random Permutations
• On the distribution of the length of the second row of a Young diagram under Plancherel measure
• The asymptotics of monotone subsequences of involutions
• Numerical study of higher order analogues of the Tracy-Widom distribution
• Longest increasing subsequences of random colored permutations