Skip to main content
eScholarship
Open Access Publications from the University of California
Refine Search

UC Berkeley

UC Berkeley Previously Published Works bannerUC Berkeley

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

Published Web Location

https://doi.org/10.1090/s0273-0979-99-00796-x
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.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.


Top