The Surprising Mathematics of Longest Increasing Subsequences

Ulam’s problem is a 70-year old problem in Combinatorics. It consists of describing the distribution of the length of a longest increasing subsequence of a random permutation of a given length. This is a very difficult problem, and so are the methods used to attack it. There have been a lot of results, especially since a seminal article by Baik, Deift and Johansson in 1999. So the area has certainly needed a book.

The question is, how can you write a book on such a difficult topic? The answer is: not very easily.

The book under review gets difficult by the middle of Chapter 1, which looks at the longest increasing subsequences of permutations. Even here, we read about continuous versions of objects that we normally see in discrete forms, like Standard Young Tableaux. Chapter 2 is about the main result of the mentioned seminal paper, and needless to say it is very difficult.

Chapter 3 discusses permutations whose Standard Young Tableaux have rectangular shapes, which are called Erdős-Szekeres permutations. Then we look at limit shapes at random Standard Young Tableaux, and finally we consider generalized permutations and Semistandard Young Tableaux. There are a fair number of exercises, which is good, and they are classified according to their level of difficulty, which is great, but they have no solutions in the book, which is too bad for a book at this difficulty level.

On the whole, the author did a great service to the community of specialists to by having written this book. It will be a great reference material, and some people will learn some of the techniques which are applied here. However, this reviewer finds the fact that the book was published in a textbook series rather amusing.

Miklós Bóna is Professor of Mathematics at the University of Florida.