Combinatorics and Random Matrix Theory

The book is built around two classic combinatorial problems. The first is Ulam’s problem. For a permutation \(p\) of length \(n\), let \(X_n(p)\) denote the length of the longest increasing subsequence of \(p\). What can we say about the expectation, the variance, and in general, about the distribution of \(X_n\) as \(n\) goes to infinity?

The second problem is that of random tilings of the Aztec diamond. Let us consider the planar region of points \((x,y)\) that is defined by the inequality \(|x|+|y|\leq n+1\). Let us tile this region (called the Aztec diamond) with \(2\times 1\) dominoes, placed vertically or horizontally, so that they lie entirely within the region, and the corners have integer coordinates. It can be shown that the number of such tilings is \(2^{n(n+1)/2}\). The following result is even more interesting. Every tiling determines a partition of the Aztec diamond into five regions. The four “outer” or “polar” regions consist of tiles that line up with nearby tiles, and the “central” region, in which every horizontal tile touches a vertical tile and vice versa. Furthermore, if \(n\) is large enough, then for most tilings the central region becomes arbitrarily close to a circle of radius \(n/2\). In this book, a more general distribution of tilings is considered, one that generalizes the uniform distribution, and in that more general setup, the central circle becomes a central ellipse.

After introducing these two fascinating problems, the authors show how to translate them into the theory of random matrices, and how several properties of the mentioned objects can be studied through analyzing eigenvalues of random matrices. The tools get very deep and diverse: symmetric functions, algebraic combinatorics, measure theory, complex analysis, orthogonal polynomials, Brownian motion, to name a few.

The book covers exciting results, and has a wealth of information. The authors state that a reader with two-three years of graduate school can learn the subject directly from the text. This reviewer agrees, if the reader has two-three years of experience in each of the areas from which the authors take their tools.

Buy Now

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