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

Abstract

We describe a simple one-person card game, <italic>patience sorting</italic>. 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.