On the distribution of the length of the longest increasing subsequence of random permutations

1999/06/24 by Jinho Baik, Percy Deift, Kurt Johansson · 13 citations
Mathematics · Computer Science · #Random Matrices and Applications #Bayesian Methods and Mixture Models #Advanced Combinatorial Mathematics #Mathematics #Longest increasing subsequence #Random matrix #Subsequence #Permutation (music) #Distribution (mathematics) #Combinatorics #Random permutation #Integrable system #Context (archaeology) #Hessian matrix #Eigenvalues and eigenvectors #Pure mathematics #Mathematical analysis #Applied mathematics #Symmetric group

paper · doi:10.1090/s0894-0347-99-00307-0

openalex publication_date 1999/06/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/15

Abstract

The authors consider the length, l_N, 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 of the largest eigenvalue of a random GUE matrix. The authors also prove convergence of moments. The proof is based on the steepest descent method for Riemann-Hilbert problems, introduced by Deift and Zhou in 1993 in the context of integrable systems. The applicability of the Riemann-Hilbert technique depends, in turn, on the determinantal formula of Gessel for the Poissonization of the distribution function of l_N.

Citations

• Asymptotics for polynomials orthogonal with respect to varying exponential weights
• Random Matrices and Random Permutations
• A Steepest Descent Method for Oscillatory Riemann--Hilbert Problems. Asymptotics for the MKdV Equation
• Monodromy perserving deformation of linear ordinary differential equations with rational coefficients. II
• On increasing subsequences of iid samples
• Transversal fluctuations for increasing subsequences on the plane

Cited by

• Optimal rules for the sequential selection of monotone subsequences of maximum expected length
• Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
• A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length
• A survey of alternating permutations
• Tropical combinatorics and Whittaker functions
• Random walk generated by random permutations of 1, 2, 3, ,n+ 1
• Asymptotics for First-Passage Times on Delaunay Triangulations
• On the Collision between two PNG Droplets
• SPECTRAL DENSITY SCALING OF FLUCTUATING INTERFACES
• Vicious walkers and hook Young tableaux
• The Shape of Random Pattern-Avoiding Permutations
• Statistical self-similarity of one-dimensional growth processes
• Longest increasing subsequence [wikipedia]