The use of multivariate methods for analytic combinatorics is an up-and-coming part of enumerative combinatorics. As such, there are few texts on the subject, thus this book is both timely and important. The authors explore the key question of how to use techniques for computing the asymptotics of the coefficients of multivariate generating functions.
The book builds the theory from the ground up, with two background sections leading to a final research-driven section. The authors outline their basic six-step method in Section 1.3. The method applies only to the class of rational functions that have singularities, for which the dominant singularity is a pole. In their words, the six steps are:
(i) Use the multidimensional Cauchy integral (1.3.1) to express [the generating function coefficient] ar as an integral over a d-dimensional torus T in . (ii) Observe that T may be replaced by any cycle homologous to [T] in Hd(), where is the domain of holomorphy of the integrand. (iii) Deform the cycle to lower the modulus of the integrand as much as possible; use Morse theoretic methods to characterize the minimax cycle in terms of critical points. (iv) Use algebraic methods to find the critical points; these are points of that depend on the direction of the asymptotics and are saddle points for the magnitude of the integrand. (v) Use topological methods to locate one or more contributing critical points zj and replace the integral over T by an integral over quasi-local cycles C(zj) near each zj. (vi) Evaluate the integral over each C(zj) by a combination of residue and saddle point techniques.
The book is a proof of the validity of these methods and a prescription for using them. Part 1 presents background knowledge in classical enumerative combinatorics in the style of Stanley’s Enumerative combinatorics [1]. Part 2 gives results from the complex analysis. Part 3 contains the meat of the book: an exposition of the recent research results implementing the method described above.
Chapter 1 introduces generating functions, the asymptotics of generating functions, and the proposed six-step method. Chapter 2 covers generating functions in depth, including rational operations on them, algebraic generating functions, D-finite functions, and P-recursiveness. Chapter 3 describes univariate asymptotics along the lines of the material in Flajolet and Sedgwick’s Analytic combinatorics [2]. This chapter covers saddle point methods, circle methods, and transfer theorems.
Chapters 4 and 5 provide background on noncombinatorial mathematics, saddle point approximation, univariates and multivariates, and Fourier-Laplace asymptotics. However, much of the treatment is new in terms of both what is included and how it is presented. This is a good example of one of the strengths of this book, which is to show material in the right light to derive the asymptotics. Chapter 6 introduces symbolic computation for this area. Another strength of this book is how seamlessly the authors integrate symbolic computation commands (for Maple, although other computer algebra packages are discussed) into the text. The chapter itself concerns Gröbner bases and how to use them to compute solutions to suitable algebraic equations. In chapter 7, the authors discuss Laurent series and related concepts, which are the final background pieces required for their theory.
Chapter 8 marks the transition to the third part of the book with an introduction to more required background, namely Morse theory. Chapters 9 to 11 present particular cases of choosing the right contours of integration to asymptotically evaluate the Cauchy integral, as required in the six-step method. Much of the material in these chapters is from the authors’ own research, and all of it is recent (mostly since 2000). Chapter 12 presents a number of worked examples, also mostly drawn directly from their own research. Chapter 13 is a collection of additional methods that can be used in some particular cases.
The book is detailed, self-contained, and clearly written. It would be suitable for a graduate course on the topic, or as a handbook for a mathematician in a related field who wants to conduct research in this area. The book is packed with examples, but the number of homework problems is sparse and no solutions are provided. However, this is a minor issue. Overall, the book would be a welcome addition to the bookshelf of any enumerative combinatoralist. As the authors themselves say, “This book is ... an invitation to join the authors in further development of this research area.”
