You are here

Zeta Functions of Graphs: A Stroll through the Garden

Audrey Terras
Cambrigde University Press
Publication Date: 
Number of Pages: 
Cambridge Studies in Advanced Mathematics 128
[Reviewed by
Michael Berg
, on

Being Audrey Terras’ PhD student was a lot of fun. Indeed, being part of the UCSD number theory community back in the early 1980s was one of the wonderful experiences of my mathematical life, and I often think back to those days with great fondness. 

Audrey was part of a trio, including also Harold Stark and Ronald Evans, who together ran the number theory concession, so to speak, with a flow of visitors in the game: I recall Sigurdur Helgason coming to visit, as well as Dennis Hejhal, and there were a lot of people around in neighboring areas who added incomparably to the whole experience. Topology and geometry were particularly busy areas, with Max Karoubi and Alain Connes visiting from France, for example.

UCSD’s Mathematics Department was a fantastic place to be, but the number theory group was special, I think: some very high-powered stuff was being done (and taught) in an almost disarmingly low-key way and just as the lectures and seminars were a lot of fun, they were certainly not for the timid.

Regarding Audrey herself, this was all of a piece: even as she was waging war on some very serious mathematics she was constitutionally incapable of keeping from giggling at least once during her lectures, often when bringing in idiosyncratic illustrations, sometimes including artwork of her own: see p. xi of the book under review, or p. 192.

Additionally, and somewhat mysteriously, her office whiteboard sported for years a color-marker rendering of a very large penguin. This was in contrast to her office blackboard which was generally reserved for mathematics proper: I recall that my weekly progress reports to Audrey often involved this classical prop even as I spied Audrey’s penguin looking at me from across the room.

Well, does this have anything to do with the book under review, Audrey’s recent publication, Zeta Functions of Graphs: A Stroll through the Garden? In a way, yes: elements of playfulness abound in its pages, even as it is manifestly a work of serious scholarship. True to form, Audrey also peppers he book with opportunities to compute, experiment, and explore things in the context of specific well-chosen examples, and a great number of examples and exercises call for some measure of computer expertise; software such as Mathematica, Matlab, and Scientific Workplace figure non-trivially in the pages of the book under review. This is of course fitting and proper for what the author characterizes as a stroll through a mathematical garden.

Regarding the specific content of the book, we read at the outset: “The goal of this book is to guide the reader in a stroll through the garden of zeta functions of graphs. The subject arose in the late part of the twentieth century and was modeled on the zetas found in other gardens.” Accordingly the stroll starts off, in Part I, with “[a] quick look at various [model] zeta functions,” namely those of Riemann, Ihara, Selberg, and Ruelle, capped off by material on quantum chaos and random matrices.

In the latter connection, see p. 36ff for a discussion one of the most marvelous episodes and tantalizing episodes in both modern analytic number theory and theoretical physics: the aftershocks of the famous chat, over tea at the Institute for Advanced Study, between Hugh Montgomery, who had just lectured on his work on the zeta function of Riemann, and the redoubtable Freeman J. Dyson, linking the statistics of the non-trivial zeroes of the zeta function to the energy levels of quantum systems. Specifically, and bringing us up to date, Terras points out that “[Andrew] Odlyzko’s experimental results show that the level spacings … [for the non-trivial zeroes of the zeta function high up the critical line] look like that of the Gaussian unitary ensemble, i.e. the eigenvalue distribution of a random complex Hermitian matrix.” What a supremely beautiful confluence of mathematical events! (The interested reader should take a look, also, at Dyson’s 2003 MSRI talk, “Random matrices, neutron capture levels, quasicrystals, and zeta function zeroes.”)

After this, Part II is devoted to Ihara’s zeta function and the prime number theorem for graph theory. Audrey starts off by observing that “[g]raph theory zetas first appeared in work of Ihara on p-adic groups in the 1960s … [while it was] Serre who made the connection with graph theory.” Then, after a rather thorough literature review, the fun starts: a lot of very evocative graph theory, well-chosen exercises, a discussion of how to phrase a Riemann hypothesis in these contexts (cf. the “weak graph theory RH” on p. 54), a good deal of material on Ramanujan graphs, and, in Chapter 10, a nice discussion of a graph theoretic prime number theorem. Subsequently a comparatively brief Part III is devoted to edge and path zeta functions.

I must say that my favorite part of Zeta Functions of Graphs: A Stroll through the Garden is Part IV, “Finite unramified Galois coverings of connected graphs,” largely for the same reason why, some thirty years ago, when it came time for me to write my thesis, I chose the eighth and last problem on Audrey’s list of thesis problem options: there is an abundance of algebraic number theory in play, even as the indicated methodology is far more eclectic. In this part of her book Audrey addresses not only graph theoretic counterparts to Galois theoretic objects (including FT Galois Theory), but also to, e.g., Frobenius automorphisms and Artin L-functions. She closes Part IV with three powerful themes: certain non-isomorphic regular graphs possessing the same Ihara zeta function, a Chebotarev density theorem, and a discussion of Siegel poles. Zeta Functions of Graphs: A Stroll through the Garden closes, in Part V’s “Last look at the garden,” with material on error-correcting codes, chaos, and, most tantalizingly, a section titled, “Final research problems.”

Thus in the compact space of about 230 pages, the author has presented us with a very expansive and varied collection of results centered on a single theme, zetas on graphs, making for a corresponding number of parallels with results and methods from, for lack of a better word, mainstream analytic number theory. In other words, given the importance and ubiquity of zeta functions as historical objects, equipped with their own orbit from Riemann though Artin to Grothendieck, it is useful indeed to be presented with parallel hard-core number theory in the present context of graph theory. Indeed, the ubiquity of mathematical objects that allow graph theoretic renderings is sufficient rationale in itself to justify the present undertaking.

Zeta Functions of Graphs: A Stroll through the Garden should serve very well as an introduction to this subject appropriate for arithmeticians, fledgling or otherwise, who want to do research in this area. As is her wont, Terras is scrupulous with her references, and many of the introductory remarks to each Part make for good road maps as well as good sketches of the landscape — even in parts of the garden not on the stroll’s itinerary.

Finally, the sufficiently mathematically mature reader (I would say at least a well-trained and suitably enthusiastic advanced graduate student) should be prepared to go through the book with care, the ubiquitous pencil and paper in hand, working through the exercises and examples so as to derive maximal benefit from the experience. With these hypotheses met it will be nigh on impossible for said reader not to join Audrey in the sheer fun she is having in these pages, even as a lot of serious mathematics is being done.

Michael Berg is Professor of Mathematics at Loyola Marymount University in Los Angeles, CA.

List of illustrations
Part I. A Quick Look at Various Zeta Functions: 1. Riemann's zeta function and other zetas from number theory
2. Ihara's zeta function
3. Selberg's zeta function
4. Ruelle's zeta function
5. Chaos
Part II. Ihara's Zeta Function and the Graph Theory Prime Number Theorem: 6. Ihara zeta function of a weighted graph
7. Regular graphs, location of poles of zeta, functional equations
8. Irregular graphs: what is the RH?
9. Discussion of regular Ramanujan graphs
10. The graph theory prime number theorem
Part III. Edge and Path Zeta Functions: 11. The edge zeta function
12. Path zeta functions
Part IV. Finite Unramified Galois Coverings of Connected Graphs: 13. Finite unramified coverings and Galois groups
14. Fundamental theorem of Galois theory
15. Behavior of primes in coverings
16. Frobenius automorphisms
17. How to construct intermediate coverings using the Frobenius automorphism
18. Artin L-functions
19. Edge Artin L-functions
20. Path Artin L-functions
21. Non-isomorphic regular graphs without loops or multiedges having the same Ihara zeta function
22. The Chebotarev Density Theorem
23. Siegel poles
Part V. Last Look at the Garden: 24. An application to error-correcting codes
25. Explicit formulas
26. Again chaos
27. Final research problems