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

著者: David Aldous, Persi Diaconis - Bulletin of the American Mathematical Society 1999 被引用: 431

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.