Skip to Main Content

Bulletin of the American Mathematical Society

The Bulletin publishes expository articles on contemporary mathematical research, written in a way that gives insight to mathematicians who may not be experts in the particular topic. The Bulletin also publishes reviews of selected books in mathematics and short articles in the Mathematical Perspectives section, both by invitation only.

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

The 2020 MCQ for Bulletin of the American Mathematical Society is 0.84.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
HTML articles powered by AMS MathViewer

by David Aldous and Persi Diaconis PDF
Bull. Amer. Math. Soc. 36 (1999), 413-432 Request permission

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
  • 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, DOI 10.1007/BF01204214
  • B.C. Arnold, N. Balakrishnan, and H.N. Nagarajo. Records. Wiley, 1998.
  • 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.
  • 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.
  • J. Baik and E.M. Rains. Algebraic aspects of increasing subsequences. Technical Report math.CO/9905083, XXX Math Archive, 1999.
  • J. Baik and E.M. Rains. Generalized increasing subsequence problems II. Asymptotic results. Technical report, Courant Institute, 1999.
  • Patrick Billingsley, Convergence of probability measures, John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR 0233396
  • A. Borodin. Longest increasing subsequences of random colored permutations. Technical Report math.CO/9902001, XXX Math Archive, 1999.
  • A. Borodin, A. Okounkov, and G. Olshanski. On asymptotics of Plancherel measures for symmetric groups. Technical Report math.CO/9905032, XXX Math Archive, 1999.
  • D. Critchlow. Ulam’s metric. In Encyclopedia of Statistical Sciences, volume 9, pages 379–380. Wiley, 1988.
  • A. De Masi, N. Ianiro, A. Pellegrinotti, and E. Presutti, A survey of the hydrodynamical behavior of many-particle systems, Nonequilibrium phenomena, II, Stud. Statist. Mech., XI, North-Holland, Amsterdam, 1984, pp. 123–294. MR 757003
  • Richard Durrett, Oriented percolation in two dimensions, Ann. Probab. 12 (1984), no. 4, 999–1040. MR 757768
  • Richard Durrett, Probability, The Wadsworth & Brooks/Cole Statistics/Probability Series, Wadsworth & Brooks/Cole Advanced Books & Software, Pacific Grove, CA, 1991. Theory and examples. MR 1068527
  • Ron Engelen, Paul Tommassen, and Wim Vervaat, Ignatov’s theorem: a new and short proof, J. Appl. Probab. Special Vol. 25A (1988), 229–236. A celebration of applied probability. MR 974584, DOI 10.1017/s0021900200040389
  • P. A. Ferrari and L. R. G. Fontes, Poissonian approximation for the tagged particle in asymmetric simple exclusion, J. Appl. Probab. 33 (1996), no. 2, 411–419. MR 1385350, DOI 10.1017/s0021900200099824
  • Michael L. Fredman, On computing the length of longest increasing subsequences, Discrete Math. 11 (1975), 29–35. MR 354386, DOI 10.1016/0012-365X(75)90103-X
  • Ira M. Gessel, Symmetric functions and P-recursiveness, J. Combin. Theory Ser. A 53 (1990), no. 2, 257–285. MR 1041448, DOI 10.1016/0097-3165(90)90060-A
  • J. M. Hammersley, First-passage percolation, J. Roy. Statist. Soc. Ser. B 28 (1966), 491–496. MR 214163, DOI 10.1111/j.2517-6161.1966.tb00661.x
  • 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
  • Gordon James and Adalbert Kerber, The representation theory of the symmetric group, Encyclopedia of Mathematics and its Applications, vol. 16, Addison-Wesley Publishing Co., Reading, Mass., 1981. With a foreword by P. M. Cohn; With an introduction by Gilbert de B. Robinson. MR 644144
  • T. A. Jenkyns and E. R. Muller, A probabilistic analysis of clock solitaire, Math. Mag. 54 (1981), no. 4, 202–208. MR 627454, DOI 10.2307/2689633
  • K. Johansson. Shape fluctuations and random matrices. Technical report, Royal Inst. Technology, Stockholm, 1999.
  • Norman L. Johnson, Samuel Kotz, and N. Balakrishnan, Continuous univariate distributions. Vol. 2, 2nd ed., Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics, John Wiley & Sons, Inc., New York, 1995. A Wiley-Interscience Publication. MR 1326603
  • A. M. Vershik and S. V. Kerov, Asymptotic theory of the characters of a symmetric group, Funktsional. Anal. i Prilozhen. 15 (1981), no. 4, 15–27, 96 (Russian). MR 639197
  • Harry Kesten, On the speed of convergence in first-passage percolation, Ann. Appl. Probab. 3 (1993), no. 2, 296–338. MR 1221154
  • Jeong Han Kim, On increasing subsequences of random permutations, J. Combin. Theory Ser. A 76 (1996), no. 1, 148–155. MR 1405997, DOI 10.1006/jcta.1996.0095
  • C. Kuykendall. Analyzing solitaire. Science, 283(5403):794–795, Feb. 5, 1999.
  • Thomas M. Liggett, Interacting particle systems, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 276, Springer-Verlag, New York, 1985. MR 776231, DOI 10.1007/978-1-4613-8542-4
  • 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, DOI 10.1016/0001-8708(77)90030-5
  • I. G. Macdonald, Symmetric functions and Hall polynomials, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1979. MR 553598
  • C.L. Mallows. Problem 62-2, patience sorting. SIAM Review, 5:375–376, 1963.
  • C.L. Mallows. Patience sorting. Bull. Inst. Math. Appl., 9:216–224, 1973.
  • R. Daniel Mauldin and S. M. Ulam, Mathematical problems and games, Adv. in Appl. Math. 8 (1987), no. 3, 281–344. MR 898709, DOI 10.1016/0196-8858(87)90026-1
  • S. P. Meyn and R. L. Tweedie, Markov chains and stochastic stability, Communications and Control Engineering Series, Springer-Verlag London, Ltd., London, 1993. MR 1287609, DOI 10.1007/978-1-4471-3267-7
  • Albert H. Morehead and Geoffrey Mott-Smith. The Complete Book of Solitaire and Patience Games. Bantam, 1973.
  • A.M. Odlyzko, B. Poonen, H. Widom, and H. Wilf. On the distribution of longest increasing subsequences in random permutations. In Preparation, 1998.
  • A.M. Odlyzko and E.M. Rains. On longest increasing subsequences in random permutations. Technical report, AT&T Labs, 1998.
  • A. Okounkov. Random matrices and random permutations. Technical Report math.CO/9903176, XXX Math Archive, 1999.
  • David Partlett. Solitaire: Aces Up and 399 Other Card Games. Pantheon, 1979.
  • Shaiy Pilpel, Descending subsequences of random permutations, J. Combin. Theory Ser. A 53 (1990), no. 1, 96–116. MR 1031615, DOI 10.1016/0097-3165(90)90022-O
  • A. Rabb. A probabilistic analysis of the game of solitaire, 1989. Undergraduate Honors Thesis, Harvard.
  • E. M. Rains, Increasing subsequences and the classical groups, Electron. J. Combin. 5 (1998), Research Paper 12, 9. MR 1600095, DOI 10.37236/1350
  • H. Rost, Nonequilibrium behaviour of a many particle process: density profile and local equilibria, Z. Wahrsch. Verw. Gebiete 58 (1981), no. 1, 41–53. MR 635270, DOI 10.1007/BF00536194
  • 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
  • C. Schensted, Longest increasing and decreasing subsequences, Canadian J. Math. 13 (1961), 179–191. MR 121305, DOI 10.4153/CJM-1961-015-3
  • T. Seppäläinen, Hydrodynamic scaling, convex duality and asymptotic shapes of growth models, Markov Process. Related Fields 4 (1998), no. 1, 1–26. MR 1625007
  • R. Stanley. Enumerative Combinatorics, Vol. 2. Cambridge University Press, 1999.
  • Richard P. Stanley, Enumerative combinatorics. Vol. I, The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, CA, 1986. With a foreword by Gian-Carlo Rota. MR 847717, DOI 10.1007/978-1-4615-9763-6
  • Dennis Stanton and Dennis White, Constructive combinatorics, Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1986. MR 843332, DOI 10.1007/978-1-4612-4968-9
  • Craig A. Tracy and Harold Widom, Level-spacing distributions and the Airy kernel, Comm. Math. Phys. 159 (1994), no. 1, 151–174. MR 1257246, DOI 10.1007/BF02100489
  • C.A. Tracy and H. Widom. Random unitary matrices, permutations and Painlevé. Technical Report math.CO/9811154, XXX Math Archive, 1998.
  • 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.
  • S.M. Ulam. Some ideas and prospects in biomathematics. Ann. Rev. Biophys. Bioeng., 1:277–292, 1972.
  • 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.
  • 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.
  • Pascual Llorente, Some problems in the theory of algebraic numbers, Publ. Sec. Mat. Univ. Autònoma Barcelona 23 (1981), 101–132 (Spanish). MR 766674
  • M.S. Waterman and M. Vingron. Sequence comparison significance and Poisson approximation. Statist. Science, 9:367–381, 1994.
Similar Articles
Additional Information
  • David Aldous
  • Affiliation: Departments of Mathematics and Statistics, Stanford University, Stanford, CA 94305
  • MR Author ID: 24555
  • Email: aldous@stat.berkeley.edu
  • Persi Diaconis
  • Affiliation: Departments of Mathematics and Statistics, Stanford University, Stanford, CA 94305
  • MR Author ID: 57595
  • Received by editor(s): May 17, 1999
  • Published electronically: July 21, 1999
  • Additional Notes: Research supported by NSF Grant MCS 96-22859.
  • © Copyright 1999 American Mathematical Society
  • Journal: Bull. Amer. Math. Soc. 36 (1999), 413-432
  • MSC (1991): Primary 60C05, 05E10, 15A52, 60F05
  • DOI: https://doi.org/10.1090/S0273-0979-99-00796-X
  • MathSciNet review: 1694204