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), 11191178
MSC (1991):
Primary 05A05, 15A52, 33D45, 45E05, 60F99
Published electronically:
June 24, 1999
MathSciNet review:
1682248
Fulltext 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 TracyWidom 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 RiemannHilbert problems, introduced by Deift and Zhou in 1993 in the context of integrable systems. The applicability of the RiemannHilbert 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/S00255718196802282168
 [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 Eprint 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, BaselBoston, Mass., 1981. MR 657762
(84a:47016)
 [De]
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. MR 1363027
(96i:58071)
 [DIZ]
P.
A. Deift, A.
R. It\cydots, and X.
Zhou, Longtime 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.TR McLaughlin, New Results on the Equilibrium Measure for Logarithmic potentials in the Presence of an External Field, J. Approx. Theory, 95, no.3, 388475, (1998). CMP 99:05
 [DKMVZ1]
P.
Deift, T.
Kriecherbauer, K.
TR 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.TR McLaughlin, S.Venakides and X.Zhou, Strong Asymptotics for Orthogonal Polynomials with respect to Varying Exponential Weights via RiemannHilbert Techniques, To appear in Comm. Pure. Appl. Math.
 [DKMVZ3]
P.A.Deift, T.Kriecherbauer, K.TR 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 longtime 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 RiemannHilbert 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 RiemannHilbert
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]
JeanDominique
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, 463470, (1935).
 [FN]
Hermann
Flaschka and Alan
C. Newell, Monodromy and spectrumpreserving 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 Precursiveness, J. Combin.
Theory Ser. A 53 (1990), no. 2, 257–285. MR 1041448
(91c:05190), http://dx.doi.org/10.1016/00973165(90)90060A
 [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, Onedimensional 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, Onedimensional 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 thirdorder phase transition in the large N lattice gauge theory, Phys. Rev. D, 21, 446453, (1980).
 [Ha]
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. MR 0405665
(53 #9457)
 [HM]
S.
P. Hastings and J.
B. McLeod, A boundary value problem associated with the second
Painlevé transcendent and the Kortewegde\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, SpringerVerlag, 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/01672789(81)900130
 [Jo1]
Kurt
Johansson, The longest increasing subsequence in a random
permutation and a unitary random matrix model, Math. Res. Lett.
5 (1998), no. 12, 63–82. MR 1618351
(99e:60033), http://dx.doi.org/10.4310/MRL.1998.v5.n1.a6
 [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, 148155, (1996).
 [Kn]
Donald
E. Knuth, The art of computer programming. Volume 3,
AddisonWesley Publishing Co., Reading, Mass.LondonDon Mills, Ont., 1973.
Sorting and searching; AddisonWesley 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/00018708(77)900305
 [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, UnitaryMatrix Models as Exactly Solvable String Theories, Phys. Rev. Lett., 64, 13261329, (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, SpringerVerlag, 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.v15
 [Se2]
T.Seppäläinen, Large deviations for increasing sequences on the plane, Probab. Theory Related Fields, 112, no.2, 221244, (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, Levelspacing 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 Eprint math.CO/9811154.
 [Ul]
Stanislaw
M. Ulam, Monte Carlo calculations in problems of mathematical
physics, Modern mathematics for the engineer: Second series,
McGrawHill, 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.
 [AS]
 M.Abramowitz and I.A.Stegun, Handbook of Mathematical Functions, Dover Publications, New York, (1965). MR 34:8606
 [AD]
 D.Aldous and P.Diaconis, Hammersley's Interacting Particle Process and Longest Increasing Subsequences, Prob. Th. and Rel. Fields, 103, 199213, (1995). MR 96k:60017
 [BB]
 R.M.Baer and P.Brock, Natural sorting over permutation spaces, Math. Comp., 22, 385410, (1968). MR 37:3800
 [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 Eprint math.CO/9901118.
 [BR]
 J.Baik and E.Rains, Symmetrized increasing subsequence problems, in preparation.
 [BC]
 R.Beals and R.Coifman, Scattering and inverse scattering for first order systems, Comm. Pure Appl. Math., 37, 3990, (1984). MR 85f:34020
 [Bo]
 A.Borodin, Longest increasing subsequences of random colored permutations, Electron. J. Combin., 6 (1), R13, (1999). CMP 99:07
 [CG]
 K.Clancey and I.Gohberg, Factorization of Matrix Functions and Singular Integral Operators, Birkhäuser, (1981). MR 84a:47016
 [De]
 P.A.Deift, Integrable Hamiltonian systems. Dynamical systems and probabilistic methods in partial differential equations, 103138, in Lectures in Applied Mathematics, 31, edited by P.A.Deift, C.D.Levermore and C.E.Wayne, American Mathematical Society, Providence, RI, 1996. MR 96i:58071
 [DIZ]
 P.A.Deift, A.R.Its and X.Zhou, Longtime Asymptotics for Integrable Nonlinear Wave Equations, in Important Development in Soliton Theory, 2nd Edition, edited by A.S.Fokas and V.E.Zakharov, SpringerVerlag, to be published. MR 95h:35031 (1st Edition)
 [DKM]
 P.A.Deift, T.Kriecherbauer and K.TR McLaughlin, New Results on the Equilibrium Measure for Logarithmic potentials in the Presence of an External Field, J. Approx. Theory, 95, no.3, 388475, (1998). CMP 99:05
 [DKMVZ1]
 P.A.Deift, T.Kriecherbauer, K.TR McLaughlin, S.Venakides and X.Zhou, Asymptotics for Polynomials Orthogonal with respect to Varying Exponential Weights, Internat. Math. Res. Notices, no. 16, 759782, (1997). MR 99g:34038
 [DKMVZ2]
 P.A.Deift, T.Kriecherbauer, K.TR McLaughlin, S.Venakides and X.Zhou, Strong Asymptotics for Orthogonal Polynomials with respect to Varying Exponential Weights via RiemannHilbert Techniques, To appear in Comm. Pure. Appl. Math.
 [DKMVZ3]
 P.A.Deift, T.Kriecherbauer, K.TR 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.A.Deift, S.Venakides and X.Zhou, The collisionless shock region for the longtime behavior of solutions of the KdV equation, Comm. Pure Appl. Math., 47 no. 2, 199206, (1994). MR 95f:35220
 [DVZ2]
 P.A.Deift, S.Venakides and X.Zhou, New Results in Small Dispersion KdV by an Extension of the Steepest Descent Method for RiemannHilbert Problems, Internat. Math. Res. Notices, no. 6, 285299, (1997). MR 98b:35155
 [DZ1]
 P.A.Deift and X.Zhou, A Steepest Descent Method for Oscillatory RiemmanHilbert Problems; Asymptotics for the MKdV Equation, Ann. Math., 137, 295368, (1993). MR 94d:35143
 [DZ2]
 P.A.Deift and X.Zhou, Asymptotics for the Painlevé II Equation, Comm. Pure. Appl. Math., 48, 277337, (1995). MR 96d:34004
 [DeZe1]
 J.D.Deuschel and O.Zeitouni, Limiting curves for i.i.d. records, Ann. Probab., 23, 852878, (1995). MR 96h:60086
 [DeZe2]
 J.D.Deuschel and O.Zeitouni, On increasing subsequences of i.i.d. samples, preprint, (1997).
 [DS]
 P.Diaconis and M.Shahshahani, On the Eigenvalues of Random matrices, J. Appl. Prob. 31, 4961, (1994). MR 95m:60011
 [ES]
 P.Erdös and G.Szekeres, A combinatorial theorem in geometry, Compositio Math., 2, 463470, (1935).
 [FN]
 H.Flaschka and A.Newell, Monodromy and spectrum preserving deformations, I, Comm. Math. Phy., 76, no.1, 67116, (1980). MR 82g:35103
 [FIK]
 A.S.Fokas, A.R.Its and V.E.Kitaev, Discrete Painlevé equations and their appearance in quantum gravity, Comm. Math. Phy., 142, 313344, (1991). MR 93a:58080
 [FMZ]
 A.S.Fokas, U.Mugan and X.Zhou, On the Solvability of Painlevé I, III and V, Inverse Problems, 8, 757785, (1992). MR 93h:35154
 [FZ]
 A.S.Fokas and X.Zhou, On the Solvability of Painlevé II and IV, Comm. Math. Phy., 144, 601622, (1992). MR 93d:34004
 [Ge]
 I.M.Gessel, Symmetric functions and Precursiveness, J. Combin. Theory. Ser. A, 53, 257  285, (1990). MR 91c:05190
 [GWW]
 I.M.Gessel, J.Weinstein and H.S.Wilf, Lattice walks in and permutations with no long ascending subsequences, Electr. J. Combin., 5(1), (1998). MR 98j:05007
 [GK]
 I.Gohberg and N.Krupnik, OneDimensional Linear Singular Integral Equations vol.I and II, Operator theory, advances and applications; v. 5354, Birkhäuser Verlag, Basel, 1992 MR 93c:47061; MR 93k:47059
 [GW]
 D.J.Gross and E.Witten, Possible thirdorder phase transition in the large N lattice gauge theory, Phys. Rev. D, 21, 446453, (1980).
 [Ha]
 J.M.Hammersley, A few seedlings of research, Proc. Sixth Berkeley Symp. Math. Statist. and Probability, Vol. 1, 345394, University of California Press, 1972. MR 53:9457
 [HM]
 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, 3151, (1980). MR 81i:34024
 [Hi]
 M.Hisakado, Unitary matrix models and Painlevé III, Modern Phys. Lett. A, 11, no.38, 30013010, (1996). MR 97h:81200
 [IN]
 A.R.Its and V.Yu.Novokshenov, The Isomonodromic Deformation Method in the Theory of Painlevé Equations, Lecture Notes in Math.1191, SpringerVerlag, Berlin, Heidelberg, 1986. MR 89b:34012
 [JMU]
 M.Jimbo, T.Miwa and K.Ueno, Monodromy preserving deformations of linear ordinary differential equations with rational coefficients, I. General theory and function, Physica D, 2, no.2, 306352, (1981). MR 83k:34010a
 [Jo1]
 K.Johansson, The Longest Increasing Subsequence in a Random Permutation and a Unitary Random Matrix Model, Math. Res. Lett., 5, no.12, 6382, (1998). MR 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]
 S.Kamvissis, On the Long Time Behavior of the Doubly Infinite Toda Lattice under Initial Data Decaying at Infinity, Comm. Math. Phy., 153, 479519, (1993). MR 94c:58086
 [Ki]
 J.H. Kim, On the longest increasing subsequence of random permutations  a concentration result, J. Comb. Th. A, vol. 76, 148155, (1996).
 [Kn]
 D.E.Knuth, The art of computer programming, vol. 3: sorting and searching, 2nd ed., Addison Wesley, Reading, Mass., 1973. MR 56:4281
 [LS]
 B.F.Logan and L.A.Shepp, A variational problem for random Young tableaux, Advances in Math., 26, 206222, (1977). MR 98e:05108
 [Me]
 M.L.Mehta, Random Matrices, Second Edition, Academic Press, San Diego, 1991. MR 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, UnitaryMatrix Models as Exactly Solvable String Theories, Phys. Rev. Lett., 64, 13261329, (1990).
 [Ra]
 E.M.Rains, Increasing subsequences and the classical groups, Electron. J. of Combinatorics, 5(1), R12, (1998). MR 98k:05146
 [ST]
 E.B.Saff and V.Totik, Logarithmic Potentials with External Fields, SpringerVerlag, New York, 1997. CMP 98:05
 [Sa]
 B.Sagan, The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, WadsworthBooks/Cole, Pacific Grove, Calif., 1991. MR 93f:05102
 [Sc]
 C.Schensted, Longest increasing and decreasing subsequences, Canad. J. Math., 13, 179  191, (1961). MR 22:12047
 [Se1]
 T.Seppäläinen, A microscopic model for the Burgers equation and longest increasing subsequences, Electron. J. Prob., 1, no.5, (1996) MR 97d:60162
 [Se2]
 T.Seppäläinen, Large deviations for increasing sequences on the plane, Probab. Theory Related Fields, 112, no.2, 221244, (1998). CMP 99:04
 [Si]
 B.Simon, Representations of Finite and Compact Groups, Graduate Studies in Mathematics vol. 10, American Mathematical Society, 1996. MR 97c:22001
 [Sz1]
 G.Szegö, Orthogonal Polynomials, American Mathematical Society Colloquium Publications, Vol 23, 4th Ed, Providence, RI, 1975. MR 51:8724
 [Sz2]
 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, 228237, (1952) (or Gabor Szego: Collected Papers  Vol 3 (19451972), 270280, Birkhäuser, 1982). MR 14:553d
 [TW1]
 C.A.Tracy and H.Widom, LevelSpacing distributions and the Airy kernel, Comm. Math. Phys., 159, 151174, (1994). MR 95e:82003
 [TW2]
 C.A.Tracy and H.Widom, Random unitary matrices, permutations and Painlevé, preprint, LANL Eprint math.CO/9811154.
 [Ul]
 S.M.Ulam, Monte Carlo calculations in problems of mathematical physics, in Modern Mathematics for the Engineers, E.F.Beckenbach, ed., McGrawHill, 261281, 1961. MR 23:B2202
 [VK1]
 A.M.Vershik and S.V.Kerov, Asymptotics of the Plancherel measure of the symmetric group and the limiting form of Young tables, Soviet Math. Dokl., 18, 527531, (1977). MR 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, Functional Anal. Appl., 19, no.1, 2131, (1985). MR 86k:11051
 [Wi]
 H.Widom, personal communication.
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, S100 44 Stockholm, Sweden
Email:
kurtj@math.kth.se
DOI:
http://dx.doi.org/10.1090/S0894034799003070
PII:
S 08940347(99)003070
Keywords:
Random permutations,
orthogonal polynomials,
RiemannHilbert 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 #DMS9500867.
The work of the third author was supported in part by the Swedish Natural Research Council (NFR)
Article copyright:
© Copyright 1999
American Mathematical Society
