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/users/aldous/bibliog.html