LONGEST INCREASING SUBSEQUENCES: FROM PATIENCE SORTING TO THE
BAIK-DEIFT-JOHANSSON THEOREM
David Aldous and Persi Diaconis
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 asymptotic probability laws via hard analysis of
Toeplitz determinants.
aldous@stat.berkeley.edu
http://www.stat.berkeley.edu/~aldous/bibliog.html