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

The authors consider the length, lN, 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 lN, 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 lN.