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

Baik, Jinho; Deift, Percy; Johansson, Kurt

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

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Browser Compatibility Info Help
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
Posted: June 24, 1999
MathSciNet review: 1682248
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The authors consider the length, , of the longest increasing subsequence of a random permutation of numbers. The main result in this paper is a proof that the distribution function for , 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 .

[AS] Handbook of mathematical functions, with formulas, graphs, and mathematical tables, Edited by Milton Abramowitz and Irene A. Stegun, Dover Publications Inc., New York, 1966. MR 0208797 (34 #8606)
[AD] D. Aldous and P. Diaconis, Hammersley’s interacting particle process and longest increasing subsequences, Probab. Theory Related Fields 103 (1995), no. 2, 199–213. MR 1355056 (96k:60017), http://dx.doi.org/10.1007/BF01204214
[BB] R. M. Baer and P. Brock, Natural sorting over permutation spaces, Math. Comp. 22 (1968), 385–410. MR 0228216 (37 #3800), http://dx.doi.org/10.1090/S0025-5718-1968-0228216-8
[BDJ] J.Baik, P.Deift and K.Johansson, On the distribution of the length of the second row of a Young diagram under Plancherel measure, preprint, LANL E-print math.CO/9901118.
[BR] J.Baik and E.Rains, Symmetrized increasing subsequence problems, in preparation.
[BC] R. Beals and R. R. Coifman, Scattering and inverse scattering for first order systems, Comm. Pure Appl. Math. 37 (1984), no. 1, 39–90. MR 728266 (85f:34020), http://dx.doi.org/10.1002/cpa.3160370105
[Bo] A.Borodin, Longest increasing subsequences of random colored permutations, Electron. J. Combin., 6 (1), R13, (1999). CMP 99:07
[CG] Kevin F. Clancey and Israel Gohberg, Factorization of matrix functions and singular integral operators, Operator Theory: Advances and Applications, vol. 3, Birkhäuser Verlag, Basel, 1981. MR 657762 (84a:47016)
[De] Percy Deift, Integrable Hamiltonian systems, equations (Berkeley, CA, 1994) Lectures in Appl. Math., vol. 31, Amer. Math. Soc., Providence, RI, 1996, pp. 103–138. MR 1363027 (96i:58071)
[DIZ] P. A. Deift, A. R. It\cydots, and X. Zhou, Long-time asymptotics for integrable nonlinear wave equations, Important developments in soliton theory, Springer Ser. Nonlinear Dynam., Springer, Berlin, 1993, pp. 181–204. MR 1280475 (95h:35031)
[DKM] P.A.Deift, T.Kriecherbauer and K.T-R McLaughlin, New Results on the Equilibrium Measure for Logarithmic potentials in the Presence of an External Field, J. Approx. Theory, 95, no.3, 388-475, (1998). CMP 99:05
[DKMVZ1] P. Deift, T. Kriecherbauer, K. T-R McLaughlin, S. Venakides, and X. Zhou, Asymptotics for polynomials orthogonal with respect to varying exponential weights, Internat. Math. Res. Notices 16 (1997), 759–782. MR 1472344 (99g:34038), http://dx.doi.org/10.1155/S1073792897000500
[DKMVZ2] P.A.Deift, T.Kriecherbauer, K.T-R McLaughlin, S.Venakides and X.Zhou, Strong Asymptotics for Orthogonal Polynomials with respect to Varying Exponential Weights via Riemann-Hilbert Techniques, To appear in Comm. Pure. Appl. Math.
[DKMVZ3] P.A.Deift, T.Kriecherbauer, K.T-R McLaughlin, S.Venakides and X.Zhou, Uniform Asymptotics for Polynomials Orthogonal with respect to Varying Exponential Weights and Applications to Universality Questions in Random Matrix Theory, To appear in Comm. Pure. Appl. Math.
[DVZ1] P. Deift, S. Venakides, and X. Zhou, The collisionless shock region for the long-time behavior of solutions of the KdV equation, Comm. Pure Appl. Math. 47 (1994), no. 2, 199–206. MR 1263128 (95f:35220), http://dx.doi.org/10.1002/cpa.3160470204
[DVZ2] P. Deift, S. Venakides, and X. Zhou, New results in small dispersion KdV by an extension of the steepest descent method for Riemann-Hilbert problems, Internat. Math. Res. Notices 6 (1997), 286–299. MR 1440305 (98b:35155), http://dx.doi.org/10.1155/S1073792897000214
[DZ1] P. Deift and X. Zhou, A steepest descent method for oscillatory Riemann-Hilbert problems. Asymptotics for the MKdV equation, Ann. of Math. (2) 137 (1993), no. 2, 295–368. MR 1207209 (94d:35143), http://dx.doi.org/10.2307/2946540
[DZ2] P. A. Deift and X. Zhou, Asymptotics for the Painlevé II equation, Comm. Pure Appl. Math. 48 (1995), no. 3, 277–337. MR 1322812 (96d:34004), http://dx.doi.org/10.1002/cpa.3160480304
[DeZe1] Jean-Dominique Deuschel and Ofer Zeitouni, Limiting curves for i.i.d. records, Ann. Probab. 23 (1995), no. 2, 852–878. MR 1334175 (96h:60086)
[DeZe2] J.-D.Deuschel and O.Zeitouni, On increasing subsequences of i.i.d. samples, preprint, (1997).
[DS] Persi Diaconis and Mehrdad Shahshahani, On the eigenvalues of random matrices, J. Appl. Probab. 31A (1994), 49–62. Studies in applied probability. MR 1274717 (95m:60011)
[ES] P.Erdös and G.Szekeres, A combinatorial theorem in geometry, Compositio Math., 2, 463-470, (1935).
[FN] Hermann Flaschka and Alan C. Newell, Monodromy- and spectrum-preserving deformations. I, Comm. Math. Phys. 76 (1980), no. 1, 65–116. MR 588248 (82g:35103)
[FIK] A. S. Fokas, A. R. It\cydots, and A. V. Kitaev, Discrete Painlevé equations and their appearance in quantum gravity, Comm. Math. Phys. 142 (1991), no. 2, 313–344. MR 1137067 (93a:58080)
[FMZ] A. S. Fokas, Ugurhan Muğan, and Xin Zhou, On the solvability of Painlevé 𝐼,𝐼𝐼𝐼 and 𝑉, Inverse Problems 8 (1992), no. 5, 757–785. MR 1185598 (93h:35154)
[FZ] A. S. Fokas and Xin Zhou, On the solvability of Painlevé 𝐼𝐼 and 𝐼𝑉, Comm. Math. Phys. 144 (1992), no. 3, 601–622. MR 1158763 (93d:34004)
[Ge] Ira M. Gessel, Symmetric functions and P-recursiveness, J. Combin. Theory Ser. A 53 (1990), no. 2, 257–285. MR 1041448 (91c:05190), http://dx.doi.org/10.1016/0097-3165(90)90060-A
[GWW] Ira Gessel, Jonathan Weinstein, and Herbert S. Wilf, Lattice walks in 𝑍^{𝑑} and permutations with no long ascending subsequences, Electron. J. Combin. 5 (1998), Research Paper 2, 11 pp. (electronic). MR 1486395 (98j:05007)
[GK] Israel Gohberg and Naum Krupnik, One-dimensional linear singular integral equations. I, Operator Theory: Advances and Applications, vol. 53, Birkhäuser Verlag, Basel, 1992. Introduction; Translated from the 1979 German translation by Bernd Luderer and Steffen Roch and revised by the authors. MR 1138208 (93c:47061)
Israel Gohberg and Naum Krupnik, One-dimensional linear singular integral equations. Vol. II, Operator Theory: Advances and Applications, vol. 54, Birkhäuser Verlag, Basel, 1992. General theory and applications; Translated from the 1979 German translation by S. Roch and revised by the authors. MR 1182987 (93k:47059)
[GW] D.J.Gross and E.Witten, Possible third-order phase transition in the large N lattice gauge theory, Phys. Rev. D, 21, 446-453, (1980).
[Ha] J. M. Hammersley, A few seedlings of research, and Probability (Univ. California, Berkeley, Calif., 1970/1971) Univ. California Press, Berkeley, Calif., 1972, pp. 345–394. MR 0405665 (53 #9457)
[HM] S. P. Hastings and J. B. McLeod, A boundary value problem associated with the second Painlevé transcendent and the Korteweg-de\thinspace Vries equation, Arch. Rational Mech. Anal. 73 (1980), no. 1, 31–51. MR 555581 (81i:34024), http://dx.doi.org/10.1007/BF00283254
[Hi] Masato Hisakado, Unitary matrix models and Painlevé III, Modern Phys. Lett. A 11 (1996), no. 38, 3001–3010. MR 1426091 (97h:81200), http://dx.doi.org/10.1142/S0217732396002976
[IN] Alexander R. Its and Victor Yu. Novokshenov, The isomonodromic deformation method in the theory of Painlevé equations, Lecture Notes in Mathematics, vol. 1191, Springer-Verlag, Berlin, 1986. MR 851569 (89b:34012)
[JMU] Michio Jimbo, Tetsuji Miwa, and Kimio Ueno, Monodromy preserving deformation of linear ordinary differential equations with rational coefficients. I. General theory and 𝜏-function, Phys. D 2 (1981), no. 2, 306–352. MR 630674 (83k:34010a), http://dx.doi.org/10.1016/0167-2789(81)90013-0
[Jo1] Kurt Johansson, The longest increasing subsequence in a random permutation and a unitary random matrix model, Math. Res. Lett. 5 (1998), no. 1-2, 63–82. MR 1618351 (99e:60033)
[Jo2] K.Johansson, Shape fluctuations and random matrices, preprint, 1999.
[Jo3] K.Johansson, Transversal fluctuations for increasing subsequences on the plane, preprint, 1999.
[Ka] Spyridon Kamvissis, On the long time behavior of the doubly infinite Toda lattice under initial data decaying at infinity, Comm. Math. Phys. 153 (1993), no. 3, 479–519. MR 1218930 (94c:58086)
[Ki] J.-H. Kim, On the longest increasing subsequence of random permutations - a concentration result, J. Comb. Th. A, vol. 76, 148-155, (1996).
[Kn] Donald E. Knuth, The art of computer programming. Volume 3, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. Sorting and searching; Addison-Wesley Series in Computer Science and Information Processing. MR 0445948 (56 #4281)
[LS] B. F. Logan and L. A. Shepp, A variational problem for random Young tableaux, Advances in Math. 26 (1977), no. 2, 206–222. MR 1417317 (98e:05108), http://dx.doi.org/10.1016/0001-8708(77)90030-5
[Me] Madan Lal Mehta, Random matrices, 2nd ed., Academic Press Inc., Boston, MA, 1991. MR 1083764 (92f:82002)
[OPWW] A.M.Odlyzko, B.Poonen, H.Widom and H.S.Wilf, On the distribution of longest increasing subsequences in random permutations, unpublished manuscript.
[OR] A.M.Odlyzko and E.M.Rains, On longest increasing subsequences in random permutations, in preparation.
[Ok] A.Okounkov, Random matrices and random permutations, preprint, 1999.
[PS] V.Periwal and D.Shevitz, Unitary-Matrix Models as Exactly Solvable String Theories, Phys. Rev. Lett., 64, 1326-1329, (1990).
[Ra] E. M. Rains, Increasing subsequences and the classical groups, Electron. J. Combin. 5 (1998), Research Paper 12, 9 pp. (electronic). MR 1600095 (98k:05146)
[ST] E.B.Saff and V.Totik, Logarithmic Potentials with External Fields, Springer-Verlag, New York, 1997. CMP 98:05
[Sa] Bruce E. Sagan, The symmetric group, The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Advanced Books & Software, Pacific Grove, CA, 1991. Representations, combinatorial algorithms, and symmetric functions. MR 1093239 (93f:05102)
[Sc] C. Schensted, Longest increasing and decreasing subsequences, Canad. J. Math. 13 (1961), 179–191. MR 0121305 (22 #12047)
[Se1] Timo Seppäläinen, A microscopic model for the Burgers equation and longest increasing subsequences, Electron. J. Probab. 1 (1996), no. 5, approx. 51 pp. (electronic). MR 1386297 (97d:60162), http://dx.doi.org/10.1214/EJP.v1-5
[Se2] T.Seppäläinen, Large deviations for increasing sequences on the plane, Probab. Theory Related Fields, 112, no.2, 221-244, (1998). CMP 99:04
[Si] Barry Simon, Representations of finite and compact groups, Graduate Studies in Mathematics, vol. 10, American Mathematical Society, Providence, RI, 1996. MR 1363490 (97c:22001)
[Sz1] Gábor Szegő, Orthogonal polynomials, 4th ed., American Mathematical Society, Providence, R.I., 1975. American Mathematical Society, Colloquium Publications, Vol. XXIII. MR 0372517 (51 #8724)
[Sz2] G. Szegö, On certain Hermitian forms associated with the Fourier series of a positive function, Comm. Sém. Math. Univ. Lund [Medd. Lunds Univ. Mat. Sem.] 1952 (1952), no. Tome Supplementaire, 228–238. MR 0051961 (14,553d)
[TW1] Craig A. Tracy and Harold Widom, Level-spacing distributions and the Airy kernel, Comm. Math. Phys. 159 (1994), no. 1, 151–174. MR 1257246 (95e:82003)
[TW2] C.A.Tracy and H.Widom, Random unitary matrices, permutations and Painlevé, preprint, LANL E-print math.CO/9811154.
[Ul] Stanislaw M. Ulam, Monte Carlo calculations in problems of mathematical physics, Modern mathematics for the engineer: Second series, McGraw-Hill, New York, 1961, pp. 261–281. MR 0129165 (23 #B2202)
[VK1] A. M. Veršik and S. V. Kerov, Asymptotic behavior of the Plancherel measure of the symmetric group and the limit form of Young tableaux, Dokl. Akad. Nauk SSSR 233 (1977), no. 6, 1024–1027 (Russian). MR 0480398 (58 #562)
[VK2] A. M. Vershik and S. V. Kerov, Asymptotic behavior of the maximum and generic dimensions of irreducible representations of the symmetric group, Funktsional. Anal. i Prilozhen. 19 (1985), no. 1, 25–36, 96 (Russian). MR 783703 (86k:11051)
[Wi] H.Widom, personal communication.

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