The Surprising Mathematics of Longest Increasing Subsequences

Dan Romik is Professor of Mathematics at the University of California, Davis.

• 1. Longest increasing subsequences in random permutations; 2. The Baik–Deift–Johansson theorem; 3. Erdős–Szekeres permutations and square Young tableaux; 4. The corner growth process: limit shapes; 5. The corner growth process: distributional results; Appendix: Kingman's subadditive ergodic theorem.

'The story of longest monotone subsequences in permutations has been, for six decades, one of the most beautiful in mathematics, ranging from the very pure to the applied and featuring many terrific mathematicians, starting with Erdős–Szekeres's 'happy end theorem' and continuing through the Tracy–Widom distribution and the breakthrough of Baik–Deift–Johansson. With its connections to many areas of mathematics, to the Riemann hypothesis, and to high-energy physics we cannot foresee where the story is heading. Dan Romik tells the tale thus far - and teaches its rich multifaceted mathematics, a blend of probability, combinatorics, analysis, and algebra - in a wonderful way.' Gil Kalai, Hebrew University of Jerusalem