Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)



Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem

Authors: David Aldous and Persi Diaconis
Journal: Bull. Amer. Math. Soc. 36 (1999), 413-432
MSC (1991): Primary 60C05, 05E10, 15A52, 60F05
Published electronically: July 21, 1999
MathSciNet review: 1694204
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We describe a simple one-person card game, patience sorting. Its analysis leads to a broad circle of ideas linking Young tableaux with the longest increasing subsequence of a random permutation via the Schensted correspondence. A recent highlight of this area is the work of Baik-Deift-Johansson which yields limiting probability laws via hard analysis of Toeplitz determinants.

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

  • 1. D.J. Aldous and P. Diaconis. Hammersley's interacting particle process and longest increasing subsequences. Probab. Th. Rel. Fields, 103:199-213, 1995. MR 96k:60017
  • 2. B.C. Arnold, N. Balakrishnan, and H.N. Nagarajo. Records. Wiley, 1998. CMP 98:15
  • 3. J. Baik, P.A. Deift, and K. Johansson. On the distribution of the length of the longest increasing subsequence of random permutations. Technical Report math.CO/9810105, XXX Math Archive, J. Amer. Math. Soc., 12:1119-1178, 1999.
  • 4. J. Baik, P.A. Deift, and K. Johansson. On the distribution of the length of the second row of a Young diagram under Plancherel measure. Technical Report math.CO/9901118, XXX Math Archive, 1999.
  • 5. J. Baik and E.M. Rains. Algebraic aspects of increasing subsequences. Technical Report math.CO/9905083, XXX Math Archive, 1999.
  • 6. J. Baik and E.M. Rains. Generalized increasing subsequence problems II. Asymptotic results. Technical report, Courant Institute, 1999.
  • 7. P. Billingsley. Convergence of Probability Measures. Wiley, 1968. MR 38:1718
  • 8. A. Borodin. Longest increasing subsequences of random colored permutations. Technical Report math.CO/9902001, XXX Math Archive, 1999.
  • 9. A. Borodin, A. Okounkov, and G. Olshanski. On asymptotics of Plancherel measures for symmetric groups. Technical Report math.CO/9905032, XXX Math Archive, 1999.
  • 10. D. Critchlow. Ulam's metric. In Encyclopedia of Statistical Sciences, volume 9, pages 379-380. Wiley, 1988.
  • 11. A. De Masi, N. Ianiro, A. Pellegrinotti, and E. Presutti. A survey of the hydrodynamical behavior of many particle systems. In J.L. Lebowitz and E.W. Montrell, editors, Nonequilibrium Phenomena II: From Stochastics to Hydrodynamics, volume 11 of Studies in Statistical Mechanics, pages 123-294. North-Holland, Amsterdam, 1984. MR 86g:82003
  • 12. R. Durrett. Oriented percolation in two dimensions. The Annals of Probability, 12:999 - 1040, 1984. MR 86g:60117
  • 13. R. Durrett. Probability: Theory and Examples. Wadsworth, Pacific Grove, CA, 1991. MR 91m:60002
  • 14. R. Engelen, P. Tommassen, and W. Vervaat. Ignatov's theorem; a new and short proof. J. Appl. Probab., 25A:229-236, 1988. MR 90a:60094
  • 15. P.A. Ferrari and L.R.G. Fontes. Poissonian approximation for the tagged particle in asymmetric simple exclusion. J. Appl. Probab., 33:411-419, 1996. MR 97j:60183
  • 16. M.L. Fredman. On computing the length of the longest increasing subsequence. Discrete Math., 11:29-35, 1975. MR 50:6865
  • 17. I.M. Gessel. Symmetric functions and $P$-recursiveness. J. Combin. Theory Ser. A, 53:257-285, 1990. MR 91c:05190
  • 18. J.M. Hammersley. First-passage percolation. J. Roy. Statist. Soc. B, 28:491-496, 1966. MR 35:5014
  • 19. J.M. Hammersley. A few seedlings of research. In Proc. Sixth Berkeley Symp. Math. Statist. and Probability, Volume 1, pages 345-394. University of California Press, 1972. MR 53:9457
  • 20. G. James and A. Kerber. The Representation Theory of the Symmetric Group. Addison-Wesley, Reading, MA, 1981. MR 83k:20003
  • 21. T.A. Jenkyns and E.R. Muller. A probabilistic analysis of clock solitaire. Math. Magazine, 54:202-208, 1981. MR 83h:60015
  • 22. K. Johansson. Shape fluctuations and random matrices. Technical report, Royal Inst. Technology, Stockholm, 1999.
  • 23. N. L. Johnson and S. Kotz. Continuous Univariate Distributions, volume 2. Wiley, 1970. MR 96j:62029
  • 24. S.V. Kerov and A.M. Vershik. Asymptotic theory of the characters of the symmetric group. Functional Anal. Appl., 15:246-255, 1981. MR 84a:22016
  • 25. H. Kesten. On the speed of convergence in first-passage percolation. Ann. Appl. Probab., 3:296-338, 1993. MR 94m:60205
  • 26. J. H. Kim. On increasing subsequences of random permutations. J. Combin. Theory Ser. A, 76:148-155, 1996. MR 97f:60024
  • 27. C. Kuykendall. Analyzing solitaire. Science, 283(5403):794-795, Feb. 5, 1999.
  • 28. T.M. Liggett. Interacting Particle Systems. Springer-Verlag, 1985. MR 86e:60089
  • 29. B.F. Logan and L.A. Shepp. A variational problem for random Young tableaux. Advances in Math., 26:206-222, 1977. MR 98e:05108
  • 30. I. MacDonald. Symmetric Functions and Hall Polynomials. Oxford University Press, 1979. MR 84g:05003
  • 31. C.L. Mallows. Problem 62-2, patience sorting. SIAM Review, 5:375-376, 1963.
  • 32. C.L. Mallows. Patience sorting. Bull. Inst. Math. Appl., 9:216-224, 1973.
  • 33. R. D. Mauldin and S.M. Ulam. Mathematical problems and games. Adv. Appl. Math., 8:281-344, 1987. MR 89g:04005
  • 34. S.P. Meyn and R.L. Tweedie. Markov Chains and Stochastic Stability. Springer-Verlag, 1993. MR 95j:60103
  • 35. Albert H. Morehead and Geoffrey Mott-Smith. The Complete Book of Solitaire and Patience Games. Bantam, 1973.
  • 36. A.M. Odlyzko, B. Poonen, H. Widom, and H. Wilf. On the distribution of longest increasing subsequences in random permutations. In Preparation, 1998.
  • 37. A.M. Odlyzko and E.M. Rains. On longest increasing subsequences in random permutations. Technical report, AT&T Labs, 1998.
  • 38. A. Okounkov. Random matrices and random permutations. Technical Report math.CO/9903176, XXX Math Archive, 1999.
  • 39. David Partlett. Solitaire: Aces Up and 399 Other Card Games. Pantheon, 1979.
  • 40. S. Pilpel. Descending subsequences of random permutations. J. Combinatorial Th. A, 53:96-116, 1990. MR 91d:05001
  • 41. A. Rabb. A probabilistic analysis of the game of solitaire, 1989. Undergraduate Honors Thesis, Harvard.
  • 42. E. M. Rains. Increasing subsequences and the classical groups. Electron. J. Combinatorics, 5:R12, 1998. MR 98k:05146
  • 43. H. Rost. Nonequilibrium behavior of a many particle process: Density profile and local equilibrium. Z. Wahrsch. Verw. Gebiete, 58:41-53, 1981. MR 83a:60176
  • 44. B.E. Sagan. The Symmetric Group: Representations, Combinatorial Algorithms and Symmetric Functions. Wadsworth, 1991. MR 93f:05102
  • 45. C. Schensted. Longest increasing and decreasing subsequences. Canad. J. Math., 13:179-191, 1961. MR 22:12047
  • 46. T. Seppäläinen. Hydrodynamic scaling, convex duality and asymptotic shapes of growth models. Markov Process. Related Fields, 4:1-26, 1998. MR 99e:60221
  • 47. R. Stanley. Enumerative Combinatorics, Vol. 2. Cambridge University Press, 1999. CMP 99:09
  • 48. R. P. Stanley. Enumerative Combinatorics, Vol I. Wadsworth & Brooks/Cole, Monterey, California, 1986. MR 87j:05003
  • 49. D. Stanton and D. White. Constructive Combinatorics. Undergraduate Texts in Mathematics. Springer-Verlag, 1986. MR 88a:05001
  • 50. C.A. Tracy and H. Widom. Level-spacing distributions and the Airy kernel. Comm. Math. Phys., 159:151-174, 1994. MR 95e:82003
  • 51. C.A. Tracy and H. Widom. Random unitary matrices, permutations and Painlevé. Technical Report math.CO/9811154, XXX Math Archive, 1998.
  • 52. C.A. Tracy and H. Widom. On the distribution of the lengths of the longest monotone subsequences in random words. Technical Report math.CO/9904042, XXX Math Archive, 1999.
  • 53. S.M. Ulam. Some ideas and prospects in biomathematics. Ann. Rev. Biophys. Bioeng., 1:277-292, 1972.
  • 54. R. Venkatsubramani. Hydrodynamic Limit for the Asymmetric Exclusion Process with Deterministic Initial Data and the Hammersley Process on $S^1$. Ph.D. thesis, New York University, 1995.
  • 55. 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:527-531, 1977. Translation of Dokl. Acad. Nauk. SSSR 233 (1977) 1024-1027.
  • 56. 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:21-31, 1985. MR 85k:11051
  • 57. M.S. Waterman and M. Vingron. Sequence comparison significance and Poisson approximation. Statist. Science, 9:367-381, 1994. CMP 95:10

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (1991): 60C05, 05E10, 15A52, 60F05

Retrieve articles in all journals with MSC (1991): 60C05, 05E10, 15A52, 60F05

Additional Information

David Aldous
Affiliation: Departments of Mathematics and Statistics, Stanford University, Stanford, CA 94305

Persi Diaconis
Affiliation: Departments of Mathematics and Statistics, Stanford University, Stanford, CA 94305

Received by editor(s): May 17, 1999
Published electronically: July 21, 1999
Additional Notes: Research supported by NSF Grant MCS 96-22859.
Article copyright: © Copyright 1999 American Mathematical Society