Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
Authors:
- 21 July 1999
- journal article
- Published by American Mathematical Society (AMS) in Bulletin of the American Mathematical Society
- Vol. 36 (4) , 413-432
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.Keywords
This publication has 37 references indexed in Scilit:
- Analyzing SolitaireScience, 1999
- Hammersley's interacting particle process and longest increasing subsequencesProbability Theory and Related Fields, 1995
- Sequence Comparison Significance and Poisson ApproximationStatistical Science, 1994
- Level-spacing distributions and the Airy kernelCommunications in Mathematical Physics, 1994
- Symmetric functions and P-recursivenessJournal of Combinatorial Theory, Series A, 1990
- Mathematical problems and gamesAdvances in Applied Mathematics, 1987
- A Probabilistic Analysis of Clock SolitaireMathematics Magazine, 1981
- A variational problem for random Young tableauxAdvances in Mathematics, 1977
- On computing the length of longest increasing subsequencesDiscrete Mathematics, 1975
- Some Ideas and Prospects in BiomathematicsAnnual Review of Biophysics and Bioengineering, 1972