The surprising mathematics of longest increasing subsequences.

*(English)*Zbl 1345.05003
Institute of Mathematical Statistics Textbooks 4. Cambridge: Cambridge University Press (ISBN 978-1-107-42882-9/pbk; 978-1-107-07583-2/hbk; 978-1-139-87200-3/ebook). xi, 353 p. (2015).

The author has written a wonderful book, both in terms of the subject matter covered as well as the style and presentation of the book. Inspite of choosing one question, on which to base an entire book on, the text is never boring and is a very important addition to the literature in analytic combinatorics. The level mentioned by the author is about graduate level with graduate level probability theory absolutely necessary to understand the contents of the book. However, even with the recommended level of knowledge this book is not for light reading. The way the topics are introduced makes the job a bit easier for the reader, with boxed information on some of the topics discussed and references for further or background study provides enough motivation for the reader to go through with reading the book. A very nice feature of the book is that the author proves almost all of the results he needs to prove the main theorem that is presented in each chapter. This makes the book more self-contained than what is expected of such a type of book.

The main point of interest in writing the book is the famous Baik-Deift-Johansson theorem which is the subject matter of Chapter 2 in the book. The theme as is evident from the title of the book are longest increasing subequences in a random permutation. If \(\sigma\) is a permutation in \(S_n\), then we denote by \(L(\sigma)\) the length of the maximal increasing subsequence of \(\sigma\), and similarly \(D(\sigma)\) denotes the length of the maximal decreasing subsequence of \(\sigma\). The object of interest is the quantity \[ \ell_n=\frac{1}{n!}\sum_{\sigma \in S_n}L(\sigma), \] the average of \(L(\sigma)\) over all permutations of order \(n\). The main result discussed in the book is about the asymptotic bahaviour of this quantity as \(n\) grows large. S. Ulam [“Monte Carlo calculations in problems of mathematical physics”, in: Modern mathematics for the engineers. 2nd series. New York, NY: McGraw Hill. 261–281 (1961)] was the first to suggest studying about the statistical distribution of the maximal monotone subsequence lengths in random permutations. This task was taken up by J. M. Hammersley [in: Proc. 6th Berkeley Sympos. math. Statist. Probab., Univ. Calif. 1970, 1, 345–394 (1972; Zbl 0236.00018)] and hence the problem is referred to as the Ulam-Hammersley problem in the book.

The final answer (or, at least one form of the answer) is presented in Chapter 2, which is the famous result of J. Baik et al. [J. Am. Math. Soc. 12, No. 4, 1119–1178 (1999; Zbl 0932.05001)]:

For each \(n\geq 1\), let \(\sigma_n\) denote a uniformly random permutation of order \(n\). Then, for any \(x \in \mathbb{R}\) as \(n\rightarrow \infty\), we have that \[ \mathbb{P}\left(\frac{L(\sigma_n)-2\sqrt{n}}{n^{1/6}}\leq x\right)\rightarrow F_2(x). \] Here, \(F_2(t)=\det (I-A_{|L^2(t,\infty)})\), and \(A\) is the Airy kernel.

But before that, in Chapter 1, the author proves the first step towards the Ulam-Hammersley problem, namely the following result which was proved by A. M. Vershik and S. V. Kerov [Sov. Math., Dokl. 18, 527–531 (1977; Zbl 0406.05008); translation from Dokl. Akad. Nauk SSSR 233, 1024–1027 (1977); Funct. Anal. Appl. 19, 21–31 (1985); translation from Funkts. Anal. Prilozh. 19, No. 1, 25–36 (1985; Zbl 0592.20015)] and independently by B. F. Logan and L. A. Shepp [Adv. Math. 26, 206–222 (1977; Zbl 0363.62068)]:

We have the limit \[ \frac{\ell_n}{\sqrt{n}}\rightarrow 2 \] as \(n\rightarrow \infty\). Also, if for each \(n\), \(\sigma_n\) denotes a uniformly random permutation in \(S_n\), then \(L(\sigma_n)/\sqrt{n}\rightarrow 2\) in probability as \(n\rightarrow \infty\).

The distinguishing feature of this book and the depth of the subjects that are related to the problem which the book devotes itself on is very clear in the first chapter itself. Even to prove the result of Vershik-Kerov and Logan-Shepp, we meet Poisson point processes, the Robinson-Schensted algorithm (the full Robinson-Schensted-Knuth algorithm also appears later in the book), the hook-length formula, plancheral measures (which is an integral part of the book) and limit shapes (which is presented quite nicely towards the end of the book). The techniques which are used to prove auxillary lemmas comes from calculus of variation, probability theory and a little bit of fractional calculus as well. The author, not only proves the result mentioned above, but even proves a limit shape theorem for Plancheral-random Young diagrams which is of independent interest as well.

In the proof of the Baik-Deift-Johansson theorem, we get to meet many different mathematical concepts like the Tracy-Wildom distribution, determinantal point processes and classical special function, the Bessel and Airy functions. The book gets difficult at this point and we are given a crash course on many different objects while obtaining the proof of the main result. As was the case in the first chapter, the author actually proves a much more stronger result than what suffices. This is a recurrent theme in the book, and the reviewer feels that this is a nice motivation for the reader as well to learn a bit more than what was expected.

At this point, the reader may be a bit worried that what would the remaining three chapters cover if the main result has already been proved. Like as in a fine dinner, so also in this book; the latter bit (the reviewer here alludes to the dessert) is as interesting if not more than what was covered in the first part.

Chapter 3 is devoted to a special class of permutations called Erdős-Szekeres permutations, these are the permutations where the longest monotone subsequence is the shortest possible ones, thus exhibiting extremal cases. The name comes from the celebrated theorem of Erdős and Szekeres which is also discussed in Chapter 1 of the book under review. The methods that were developed in Chapter 1 now comes in handy in this chapter as well. The first two sections of this chapter is devoted to characterizing the permutations under study combinatorially. The rest of the chapter is focused on limit shape theorems for random Erdős Szekeres permutations and for random square Young tableaux. It is advisable to read Chapter 1 before reading this chapter, to get a sense of what the author is trying to accomplish. Sometimes if one is not very careful, it is easy to get lost and forget the main purpose of all the hard work; this can be specially the case for non-experts in the field. The chapter ends with a short description of the so-called Arctic circle phenomenon, which appears when some results are interpreted by the asymptotic behaviour of interacting particle system. The arctic circle phenomenon for square Young tableau jump processes in proved at the end of the chapter.

Chapters 4 and 5 are devoted to corner growth processes and their limit shapes (in Chapter 4) and distribution (in Chapter 5). The corner growth process is a random walk on the Young Graph which is defined by the rule that each new cell is always added in a position chosen uniformly randomly among the available places. This is a different type of random walk than the one already considered in the first chapter of the book, to which we did not allude to earlier. The major focus in Chapter 4 is a result of H. Rost [Z. Wahrscheinlichkeitstheor. Verw. Geb. 58, 41–53 (1981; Zbl 0451.60097)] on the limit shape for the corner growth process:

For a Young diagram \(\lambda=(\lambda_1, \ldots, \lambda_k)\), let \(\text{set}_\lambda\) denote the planar set associated with \(\lambda\), defined as \[ \text{set}_\lambda=\cup_{1\leq j\leq k, 1\leq j\leq \lambda_i} ([i-1, i]\times [j-1, j]). \] Let \((\lambda^{(n)})_{n=1}^\infty\) denote the corner growth process, and define the set \(\Lambda_{CG}\) by \[ \Lambda_{CG}=\{(x,y)\in \mathbb{R}^2:x,y\geq 0, \sqrt{x}+\sqrt{y}\leq 6^{1/4}\}. \] Then, for any \(0<\epsilon <1\) a \(n\rightarrow \infty\) we have that \[ \mathbb{P}\left((1-\epsilon)\Lambda_{CG}\subseteq \frac{1}{\sqrt{n}}\text{set}_{\lambda^{(n)}}\subseteq(1+\epsilon)\Lambda_{CG}\right)\rightarrow 1. \]

While proving this theorem, we are led to interesting mathematics about Legendre transforms, last-passage percolation and exclusion processes. Towards the end of the chapter, some results on multicorner growth processes are also discussed.

In Chapter 5, the work of K. Johansson [Commun. Math. Phys. 209, No. 2, 437–476 (2000; Zbl 0969.15008)] on a connection between corner growth processes and longest increasing subsequences in generalized permutations are studied. This connection is studied via the Robinson-Schensted-Knuth (RSK) algorithm and this connection might also assuage some of the readers who might have been wondering what the corner growth process has to do with the subject of the book. While proving the main theorem of this chapter, the RSK algorithm is discussed, as well as semistandard young tableaux and orthogonal polynomials also make an appearance, Random matrix theory rears itself here and this may be a good motivation for some readers (like the reviewer himself) to learn a bit more of this area which is finding increasing applications in mathematics and physics.

The book as a whole, is a wonderful addition for the specialists as well as the motivated non-specialist. Although a thorough background in probability theory is essential for understanding the book, it should also be noted that this book is not for the faint of heart. There are numerous exercises after each chapter which adds upon some of the things discussed in the book. The exercises are marked in order of difficulty with coffee cups ranging from one to five (five for the research level problems). It may however be noted that some of the problems would require many more cups of coffee to solve, then is recommended by the author.

The main point of interest in writing the book is the famous Baik-Deift-Johansson theorem which is the subject matter of Chapter 2 in the book. The theme as is evident from the title of the book are longest increasing subequences in a random permutation. If \(\sigma\) is a permutation in \(S_n\), then we denote by \(L(\sigma)\) the length of the maximal increasing subsequence of \(\sigma\), and similarly \(D(\sigma)\) denotes the length of the maximal decreasing subsequence of \(\sigma\). The object of interest is the quantity \[ \ell_n=\frac{1}{n!}\sum_{\sigma \in S_n}L(\sigma), \] the average of \(L(\sigma)\) over all permutations of order \(n\). The main result discussed in the book is about the asymptotic bahaviour of this quantity as \(n\) grows large. S. Ulam [“Monte Carlo calculations in problems of mathematical physics”, in: Modern mathematics for the engineers. 2nd series. New York, NY: McGraw Hill. 261–281 (1961)] was the first to suggest studying about the statistical distribution of the maximal monotone subsequence lengths in random permutations. This task was taken up by J. M. Hammersley [in: Proc. 6th Berkeley Sympos. math. Statist. Probab., Univ. Calif. 1970, 1, 345–394 (1972; Zbl 0236.00018)] and hence the problem is referred to as the Ulam-Hammersley problem in the book.

The final answer (or, at least one form of the answer) is presented in Chapter 2, which is the famous result of J. Baik et al. [J. Am. Math. Soc. 12, No. 4, 1119–1178 (1999; Zbl 0932.05001)]:

For each \(n\geq 1\), let \(\sigma_n\) denote a uniformly random permutation of order \(n\). Then, for any \(x \in \mathbb{R}\) as \(n\rightarrow \infty\), we have that \[ \mathbb{P}\left(\frac{L(\sigma_n)-2\sqrt{n}}{n^{1/6}}\leq x\right)\rightarrow F_2(x). \] Here, \(F_2(t)=\det (I-A_{|L^2(t,\infty)})\), and \(A\) is the Airy kernel.

But before that, in Chapter 1, the author proves the first step towards the Ulam-Hammersley problem, namely the following result which was proved by A. M. Vershik and S. V. Kerov [Sov. Math., Dokl. 18, 527–531 (1977; Zbl 0406.05008); translation from Dokl. Akad. Nauk SSSR 233, 1024–1027 (1977); Funct. Anal. Appl. 19, 21–31 (1985); translation from Funkts. Anal. Prilozh. 19, No. 1, 25–36 (1985; Zbl 0592.20015)] and independently by B. F. Logan and L. A. Shepp [Adv. Math. 26, 206–222 (1977; Zbl 0363.62068)]:

We have the limit \[ \frac{\ell_n}{\sqrt{n}}\rightarrow 2 \] as \(n\rightarrow \infty\). Also, if for each \(n\), \(\sigma_n\) denotes a uniformly random permutation in \(S_n\), then \(L(\sigma_n)/\sqrt{n}\rightarrow 2\) in probability as \(n\rightarrow \infty\).

The distinguishing feature of this book and the depth of the subjects that are related to the problem which the book devotes itself on is very clear in the first chapter itself. Even to prove the result of Vershik-Kerov and Logan-Shepp, we meet Poisson point processes, the Robinson-Schensted algorithm (the full Robinson-Schensted-Knuth algorithm also appears later in the book), the hook-length formula, plancheral measures (which is an integral part of the book) and limit shapes (which is presented quite nicely towards the end of the book). The techniques which are used to prove auxillary lemmas comes from calculus of variation, probability theory and a little bit of fractional calculus as well. The author, not only proves the result mentioned above, but even proves a limit shape theorem for Plancheral-random Young diagrams which is of independent interest as well.

In the proof of the Baik-Deift-Johansson theorem, we get to meet many different mathematical concepts like the Tracy-Wildom distribution, determinantal point processes and classical special function, the Bessel and Airy functions. The book gets difficult at this point and we are given a crash course on many different objects while obtaining the proof of the main result. As was the case in the first chapter, the author actually proves a much more stronger result than what suffices. This is a recurrent theme in the book, and the reviewer feels that this is a nice motivation for the reader as well to learn a bit more than what was expected.

At this point, the reader may be a bit worried that what would the remaining three chapters cover if the main result has already been proved. Like as in a fine dinner, so also in this book; the latter bit (the reviewer here alludes to the dessert) is as interesting if not more than what was covered in the first part.

Chapter 3 is devoted to a special class of permutations called Erdős-Szekeres permutations, these are the permutations where the longest monotone subsequence is the shortest possible ones, thus exhibiting extremal cases. The name comes from the celebrated theorem of Erdős and Szekeres which is also discussed in Chapter 1 of the book under review. The methods that were developed in Chapter 1 now comes in handy in this chapter as well. The first two sections of this chapter is devoted to characterizing the permutations under study combinatorially. The rest of the chapter is focused on limit shape theorems for random Erdős Szekeres permutations and for random square Young tableaux. It is advisable to read Chapter 1 before reading this chapter, to get a sense of what the author is trying to accomplish. Sometimes if one is not very careful, it is easy to get lost and forget the main purpose of all the hard work; this can be specially the case for non-experts in the field. The chapter ends with a short description of the so-called Arctic circle phenomenon, which appears when some results are interpreted by the asymptotic behaviour of interacting particle system. The arctic circle phenomenon for square Young tableau jump processes in proved at the end of the chapter.

Chapters 4 and 5 are devoted to corner growth processes and their limit shapes (in Chapter 4) and distribution (in Chapter 5). The corner growth process is a random walk on the Young Graph which is defined by the rule that each new cell is always added in a position chosen uniformly randomly among the available places. This is a different type of random walk than the one already considered in the first chapter of the book, to which we did not allude to earlier. The major focus in Chapter 4 is a result of H. Rost [Z. Wahrscheinlichkeitstheor. Verw. Geb. 58, 41–53 (1981; Zbl 0451.60097)] on the limit shape for the corner growth process:

For a Young diagram \(\lambda=(\lambda_1, \ldots, \lambda_k)\), let \(\text{set}_\lambda\) denote the planar set associated with \(\lambda\), defined as \[ \text{set}_\lambda=\cup_{1\leq j\leq k, 1\leq j\leq \lambda_i} ([i-1, i]\times [j-1, j]). \] Let \((\lambda^{(n)})_{n=1}^\infty\) denote the corner growth process, and define the set \(\Lambda_{CG}\) by \[ \Lambda_{CG}=\{(x,y)\in \mathbb{R}^2:x,y\geq 0, \sqrt{x}+\sqrt{y}\leq 6^{1/4}\}. \] Then, for any \(0<\epsilon <1\) a \(n\rightarrow \infty\) we have that \[ \mathbb{P}\left((1-\epsilon)\Lambda_{CG}\subseteq \frac{1}{\sqrt{n}}\text{set}_{\lambda^{(n)}}\subseteq(1+\epsilon)\Lambda_{CG}\right)\rightarrow 1. \]

While proving this theorem, we are led to interesting mathematics about Legendre transforms, last-passage percolation and exclusion processes. Towards the end of the chapter, some results on multicorner growth processes are also discussed.

In Chapter 5, the work of K. Johansson [Commun. Math. Phys. 209, No. 2, 437–476 (2000; Zbl 0969.15008)] on a connection between corner growth processes and longest increasing subsequences in generalized permutations are studied. This connection is studied via the Robinson-Schensted-Knuth (RSK) algorithm and this connection might also assuage some of the readers who might have been wondering what the corner growth process has to do with the subject of the book. While proving the main theorem of this chapter, the RSK algorithm is discussed, as well as semistandard young tableaux and orthogonal polynomials also make an appearance, Random matrix theory rears itself here and this may be a good motivation for some readers (like the reviewer himself) to learn a bit more of this area which is finding increasing applications in mathematics and physics.

The book as a whole, is a wonderful addition for the specialists as well as the motivated non-specialist. Although a thorough background in probability theory is essential for understanding the book, it should also be noted that this book is not for the faint of heart. There are numerous exercises after each chapter which adds upon some of the things discussed in the book. The exercises are marked in order of difficulty with coffee cups ranging from one to five (five for the research level problems). It may however be noted that some of the problems would require many more cups of coffee to solve, then is recommended by the author.

Reviewer: Manjil Pratim Saikia (Vienna)

##### MSC:

05-02 | Research exposition (monographs, survey articles) pertaining to combinatorics |

05A05 | Permutations, words, matrices |

05A19 | Combinatorial identities, bijective combinatorics |

05A15 | Exact enumeration problems, generating functions |

60C05 | Combinatorial probability |