×

zbMATH — the first resource for mathematics

On the distribution of the length of the longest increasing subsequence of random permutations. (English) Zbl 0932.05001
If \(\pi(1), \dots, \pi(n)\) is a permutation of \(1, \dots, n\), the subsequence \(\pi(i_1), \dots, \pi(i_k)\) is increasing if \(i_1< \cdots <i_k\) and \(\pi(i_1) <\cdots <\pi (i_k)\). Let \(l_n\) be the length of the longest increasing subsequence in a random permutation assigning equal probabilities \(1/n\)! to the permutations. The limiting distribution of \(l_n\) is determined, and all moments of \(l_n\) are shown to converge to the corresponding moments of the limiting distribution. This limiting distribution is equal to the limiting distribution of the largest eigenvalue of a random Hermitian \(n\times n\) matrix \(M\) with a probability density proportional to \(\exp[-\text{trace}(M^2)]\).

MSC:
05A05 Permutations, words, matrices
15B52 Random matrices (algebraic aspects)
33D45 Basic orthogonal polynomials and functions (Askey-Wilson polynomials, etc.)
45E05 Integral equations with kernels of Cauchy type
60F99 Limit theorems in probability theory
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Handbook of mathematical functions, with formulas, graphs, and mathematical tables, Edited by Milton Abramowitz and Irene A. Stegun, Dover Publications, Inc., New York, 1966.
[2] D. Aldous and P. Diaconis, Hammersley’s interacting particle process and longest increasing subsequences, Probab. Theory Related Fields 103 (1995), no. 2, 199 – 213. · Zbl 0836.60107 · doi:10.1007/BF01204214 · doi.org
[3] R. M. Baer and P. Brock, Natural sorting over permutation spaces, Math. Comp. 22 (1968), 385 – 410.
[4] 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. · Zbl 0971.05110
[5] J.Baik and E.Rains, Symmetrized increasing subsequence problems, in preparation.
[6] R. Beals and R. R. Coifman, Scattering and inverse scattering for first order systems, Comm. Pure Appl. Math. 37 (1984), no. 1, 39 – 90. · Zbl 0514.34021 · doi:10.1002/cpa.3160370105 · doi.org
[7] A.Borodin, Longest increasing subsequences of random colored permutations, Electron. J. Combin., 6 (1), R13, (1999). CMP 99:07 · Zbl 0923.05001
[8] 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-Boston, Mass., 1981. · Zbl 0428.45011
[9] Percy Deift, Integrable Hamiltonian systems, Dynamical systems and probabilistic methods in partial differential equations (Berkeley, CA, 1994) Lectures in Appl. Math., vol. 31, Amer. Math. Soc., Providence, RI, 1996, pp. 103 – 138. · Zbl 0847.58042
[10] P. A. Deift, A. R. It\cdot s, 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. · Zbl 0926.35132
[11] 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 · Zbl 0918.31001
[12] 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. · Zbl 0897.42015 · doi:10.1155/S1073792897000500 · doi.org
[13] 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. · Zbl 0897.42015
[14] 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. · Zbl 0944.42013
[15] 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. · Zbl 0797.35143 · doi:10.1002/cpa.3160470204 · doi.org
[16] 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. · Zbl 0873.65111 · doi:10.1155/S1073792897000214 · doi.org
[17] 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. · Zbl 0771.35042 · doi:10.2307/2946540 · doi.org
[18] P. A. Deift and X. Zhou, Asymptotics for the Painlevé II equation, Comm. Pure Appl. Math. 48 (1995), no. 3, 277 – 337. · Zbl 0869.34047 · doi:10.1002/cpa.3160480304 · doi.org
[19] Jean-Dominique Deuschel and Ofer Zeitouni, Limiting curves for i.i.d. records, Ann. Probab. 23 (1995), no. 2, 852 – 878. · Zbl 0834.60058
[20] J.-D.Deuschel and O.Zeitouni, On increasing subsequences of i.i.d. samples, preprint, (1997).
[21] Persi Diaconis and Mehrdad Shahshahani, On the eigenvalues of random matrices, J. Appl. Probab. 31A (1994), 49 – 62. Studies in applied probability. · Zbl 0807.15015
[22] P.Erdös and G.Szekeres, A combinatorial theorem in geometry, Compositio Math., 2, 463-470, (1935). · Zbl 0012.27010
[23] Hermann Flaschka and Alan C. Newell, Monodromy- and spectrum-preserving deformations. I, Comm. Math. Phys. 76 (1980), no. 1, 65 – 116. · Zbl 0439.34005
[24] A. S. Fokas, A. R. It\cdot s, and A. V. Kitaev, Discrete Painlevé equations and their appearance in quantum gravity, Comm. Math. Phys. 142 (1991), no. 2, 313 – 344. · Zbl 0742.35047
[25] A. S. Fokas, Ugurhan Muğan, and Xin Zhou, On the solvability of Painlevé \?,\?\?\? and \?, Inverse Problems 8 (1992), no. 5, 757 – 785. · Zbl 0754.35107
[26] A. S. Fokas and Xin Zhou, On the solvability of Painlevé \?\? and \?\?, Comm. Math. Phys. 144 (1992), no. 3, 601 – 622. · Zbl 0758.35058
[27] Ira M. Gessel, Symmetric functions and P-recursiveness, J. Combin. Theory Ser. A 53 (1990), no. 2, 257 – 285. · Zbl 0704.05001 · doi:10.1016/0097-3165(90)90060-A · doi.org
[28] 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., issn=1077-8926, review=\MR1486395,. · Zbl 0885.05010
[29] 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. 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. · Zbl 0743.45004
[30] 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).
[31] J. M. Hammersley, A few seedlings of research, Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability (Univ. California, Berkeley, Calif., 1970/1971) Univ. California Press, Berkeley, Calif., 1972, pp. 345 – 394.
[32] S. P. Hastings and J. B. McLeod, A boundary value problem associated with the second Painlevé transcendent and the Korteweg-de Vries equation, Arch. Rational Mech. Anal. 73 (1980), no. 1, 31 – 51. · Zbl 0426.34019 · doi:10.1007/BF00283254 · doi.org
[33] Masato Hisakado, Unitary matrix models and Painlevé III, Modern Phys. Lett. A 11 (1996), no. 38, 3001 – 3010. · Zbl 1022.81739 · doi:10.1142/S0217732396002976 · doi.org
[34] 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. · Zbl 0592.34001
[35] 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. , https://doi.org/10.1016/0167-2789(81)90013-0 Michio Jimbo and Tetsuji Miwa, Monodromy preserving deformation of linear ordinary differential equations with rational coefficients. II, Phys. D 2 (1981), no. 3, 407 – 448. , https://doi.org/10.1016/0167-2789(81)90021-X Michio Jimbo and Tetsuji Miwa, Monodromy preserving deformation of linear ordinary differential equations with rational coefficients. III, Phys. D 4 (1981/82), no. 1, 26 – 46. · Zbl 1194.34169 · doi:10.1016/0167-2789(81)90003-8 · doi.org
[36] 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. · Zbl 0923.60008 · doi:10.4310/MRL.1998.v5.n1.a6 · doi.org
[37] K.Johansson, Shape fluctuations and random matrices, preprint, 1999.
[38] K.Johansson, Transversal fluctuations for increasing subsequences on the plane, preprint, 1999.
[39] 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. · Zbl 0773.35074
[40] J.-H. Kim, On the longest increasing subsequence of random permutations - a concentration result, J. Comb. Th. A, vol. 76, 148-155, (1996).
[41] 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. · Zbl 0302.68010
[42] B. F. Logan and L. A. Shepp, A variational problem for random Young tableaux, Advances in Math. 26 (1977), no. 2, 206 – 222. · Zbl 0363.62068 · doi:10.1016/0001-8708(77)90030-5 · doi.org
[43] Madan Lal Mehta, Random matrices, 2nd ed., Academic Press, Inc., Boston, MA, 1991. · Zbl 0780.60014
[44] A.M.Odlyzko, B.Poonen, H.Widom and H.S.Wilf, On the distribution of longest increasing subsequences in random permutations, unpublished manuscript.
[45] A.M.Odlyzko and E.M.Rains, On longest increasing subsequences in random permutations, in preparation. · Zbl 0966.60010
[46] A.Okounkov, Random matrices and random permutations, preprint, 1999. · Zbl 1018.15020
[47] V.Periwal and D.Shevitz, Unitary-Matrix Models as Exactly Solvable String Theories, Phys. Rev. Lett., 64, 1326-1329, (1990).
[48] E. M. Rains, Increasing subsequences and the classical groups, Electron. J. Combin. 5 (1998), Research Paper 12, 9. · Zbl 0885.05112
[49] E.B.Saff and V.Totik, Logarithmic Potentials with External Fields, Springer-Verlag, New York, 1997. CMP 98:05 · Zbl 0881.31001
[50] 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. · Zbl 0823.05061
[51] C. Schensted, Longest increasing and decreasing subsequences, Canad. J. Math. 13 (1961), 179 – 191. · Zbl 0097.25202 · doi:10.4153/CJM-1961-015-3 · doi.org
[52] 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., issn=1083-6489, review=\MR1386297, doi=10.1214/EJP.v1-5,. · Zbl 0891.60093
[53] 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
[54] Barry Simon, Representations of finite and compact groups, Graduate Studies in Mathematics, vol. 10, American Mathematical Society, Providence, RI, 1996. · Zbl 0840.22001
[55] Gábor Szegő, Orthogonal polynomials, 4th ed., American Mathematical Society, Providence, R.I., 1975. American Mathematical Society, Colloquium Publications, Vol. XXIII. · JFM 65.0278.03
[56] G.Szegö, On Certain Hermitian Forms Associated with the Fourier Series of a Positive Function, Comm. Seminaire Math de l’Univ. de Lund, tome supplementaire, dedie a Marcel Riesz, 228-237, (1952) (or Gabor Szego: Collected Papers - Vol 3 (1945-1972), 270-280, Birkhäuser, 1982).
[57] Craig A. Tracy and Harold Widom, Level-spacing distributions and the Airy kernel, Comm. Math. Phys. 159 (1994), no. 1, 151 – 174. · Zbl 0789.35152
[58] C.A.Tracy and H.Widom, Random unitary matrices, permutations and Painlevé, preprint, LANL E-print math.CO/9811154. · Zbl 0965.60028
[59] 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.
[60] 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).
[61] 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).
[62] H.Widom, personal communication.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.