Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Journal of the American Mathematical Society
Journal of the American Mathematical Society
ISSN 1088-6834(online) ISSN 0894-0347(print)

 

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


Authors: Jinho Baik, Percy Deift and Kurt Johansson
Journal: J. Amer. Math. Soc. 12 (1999), 1119-1178
MSC (1991): Primary 05A05, 15A52, 33D45, 45E05, 60F99
Published electronically: June 24, 1999
MathSciNet review: 1682248
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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$.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (1991): 05A05, 15A52, 33D45, 45E05, 60F99

Retrieve articles in all journals with MSC (1991): 05A05, 15A52, 33D45, 45E05, 60F99


Additional Information

Jinho Baik
Affiliation: Courant Institute of Mathematical Sciences, New York University, New York, New York 10012
Email: baik@cims.nyu.edu

Percy Deift
Email: deift@cims.nyu.edu

Kurt Johansson
Affiliation: Department of Mathematics, Royal Institute of Technology, S-100 44 Stockholm, Sweden
Email: kurtj@math.kth.se

DOI: http://dx.doi.org/10.1090/S0894-0347-99-00307-0
PII: S 0894-0347(99)00307-0
Keywords: Random permutations, orthogonal polynomials, Riemann-Hilbert problems, random matrices, steepest descent method
Received by editor(s): July 20, 1998
Received by editor(s) in revised form: March 30, 1999
Published electronically: June 24, 1999
Additional Notes: The authors would like to acknowledge many extremely useful and enlightening conversations with Persi Diaconis and Andrew Odlyzko. Special thanks are due to Andrew Odlyzko and Eric Rains for providing us with the results of their Monte Carlo simulations.
The work of the second author was supported in part by NSF grant #DMS-9500867.
The work of the third author was supported in part by the Swedish Natural Research Council (NFR)
Article copyright: © Copyright 1999 American Mathematical Society