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

Baik, Jinho ¹   ; Deift, Percy   ; Johansson, Kurt ²

¹ Courant Institute of Mathematical Sciences, New York University, New York, New York 10012
² Department of Mathematics, Royal Institute of Technology, S-100 44 Stockholm, Sweden

Journal of the American Mathematical Society, Tome 12 (1999) no. 4, pp. 1119-1178

Résumé

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

Détail

DOI : 10.1090/S0894-0347-99-00307-0

Bibliographie

[1] Handbook of mathematical functions, with formulas, graphs, and mathematical tables 1966

[2] Aldous, D., Diaconis, P. Hammersley’s interacting particle process and longest increasing subsequences Probab. Theory Related Fields 1995 199 213

[3] Baer, R. M., Brock, P. Natural sorting over permutation spaces Math. Comp. 1968 385 410

[4] Beals, R., Coifman, R. R. Scattering and inverse scattering for first order systems Comm. Pure Appl. Math. 1984 39 90

[5] Clancey, Kevin F., Gohberg, Israel Factorization of matrix functions and singular integral operators 1981

[6] Deift, Percy Integrable Hamiltonian systems 1996 103 138

[7] Deift, P. A., It⋅S, A. R., Zhou, X. Long-time asymptotics for integrable nonlinear wave equations 1993 181 204

[8] Deift, P., Kriecherbauer, T., Mclaughlin, K. T-R, Venakides, S., Zhou, X. Asymptotics for polynomials orthogonal with respect to varying exponential weights Internat. Math. Res. Notices 1997 759 782

[9] Deift, P., Venakides, S., Zhou, X. The collisionless shock region for the long-time behavior of solutions of the KdV equation Comm. Pure Appl. Math. 1994 199 206

[10] Deift, P., Venakides, S., Zhou, X. New results in small dispersion KdV by an extension of the steepest descent method for Riemann-Hilbert problems Internat. Math. Res. Notices 1997 286 299

[11] Deift, P., Zhou, X. A steepest descent method for oscillatory Riemann-Hilbert problems. Asymptotics for the MKdV equation Ann. of Math. (2) 1993 295 368

[12] Deift, P. A., Zhou, X. Asymptotics for the Painlevé II equation Comm. Pure Appl. Math. 1995 277 337

[13] Deuschel, Jean-Dominique, Zeitouni, Ofer Limiting curves for i.i.d. records Ann. Probab. 1995 852 878

[14] Diaconis, Persi, Shahshahani, Mehrdad On the eigenvalues of random matrices J. Appl. Probab. 1994 49 62

[15] Flaschka, Hermann, Newell, Alan C. Monodromy- and spectrum-preserving deformations. I Comm. Math. Phys. 1980 65 116

[16] Fokas, A. S., It⋅S, A. R., Kitaev, A. V. Discrete Painlevé equations and their appearance in quantum gravity Comm. Math. Phys. 1991 313 344

[17] Fokas, A. S., Muğan, Ugurhan, Zhou, Xin On the solvability of Painlevé 𝐼,𝐼𝐼𝐼 and 𝑉 Inverse Problems 1992 757 785

[18] Fokas, A. S., Zhou, Xin On the solvability of Painlevé 𝐼𝐼 and 𝐼𝑉 Comm. Math. Phys. 1992 601 622

[19] Gessel, Ira M. Symmetric functions and P-recursiveness J. Combin. Theory Ser. A 1990 257 285

[20] Gessel, Ira, Weinstein, Jonathan, Wilf, Herbert S. Lattice walks in 𝑍^{𝑑} and permutations with no long ascending subsequences Electron. J. Combin. 1998

[21] Gohberg, Israel, Krupnik, Naum One-dimensional linear singular integral equations. I 1992 266

[22] Hammersley, J. M. A few seedlings of research 1972 345 394

[23] Hastings, S. P., Mcleod, J. B. A boundary value problem associated with the second Painlevé transcendent and the Korteweg-de Vries equation Arch. Rational Mech. Anal. 1980 31 51

[24] Hisakado, Masato Unitary matrix models and Painlevé III Modern Phys. Lett. A 1996 3001 3010

[25] Its, Alexander R., Novokshenov, Victor Yu. The isomonodromic deformation method in the theory of Painlevé equations 1986

[26] Jimbo, Michio, Miwa, Tetsuji, Ueno, Kimio Monodromy preserving deformation of linear ordinary differential equations with rational coefficients. I. General theory and 𝜏-function Phys. D 1981 306 352

[27] Johansson, Kurt The longest increasing subsequence in a random permutation and a unitary random matrix model Math. Res. Lett. 1998 63 82

[28] Kamvissis, Spyridon On the long time behavior of the doubly infinite Toda lattice under initial data decaying at infinity Comm. Math. Phys. 1993 479 519

[29] Knuth, Donald E. The art of computer programming. Volume 3 1973

[30] Logan, B. F., Shepp, L. A. A variational problem for random Young tableaux Advances in Math. 1977 206 222

[31] Mehta, Madan Lal Random matrices 1991

[32] Rains, E. M. Increasing subsequences and the classical groups Electron. J. Combin. 1998

[33] Sagan, Bruce E. The symmetric group 1991

[34] Schensted, C. Longest increasing and decreasing subsequences Canadian J. Math. 1961 179 191

[35] Seppäläinen, Timo A microscopic model for the Burgers equation and longest increasing subsequences Electron. J. Probab. 1996

[36] Simon, Barry Representations of finite and compact groups 1996

[37] Szegő, Gábor Orthogonal polynomials 1975

[38] Hebroni, P. Sur les inverses des éléments dérivables dans un anneau abstrait C. R. Acad. Sci. Paris 1939 285 287

[39] Tracy, Craig A., Widom, Harold Level-spacing distributions and the Airy kernel Comm. Math. Phys. 1994 151 174

[40] Ulam, Stanislaw M. Monte Carlo calculations in problems of mathematical physics 1961 261 281

[41] Veršik, A. M., Kerov, S. V. Asymptotic behavior of the Plancherel measure of the symmetric group and the limit form of Young tableaux Dokl. Akad. Nauk SSSR 1977 1024 1027

[42] Vershik, A. M., Kerov, S. V. Asymptotic behavior of the maximum and generic dimensions of irreducible representations of the symmetric group Funktsional. Anal. i Prilozhen. 1985