You are here

Algebraic Graph Theory: Morphisms, Monoids and Matrices

Ulrich Knauer
Walter de Gruyter
Publication Date: 
Number of Pages: 
Studies in Mathematics 41
[Reviewed by
Michael Berg
, on

The best mathematical biography ever written, Constance Reid’s Hilbert, contains a description of the physicist Max Born’s oral doctoral examination with David Hilbert. Hilbert asked Born earlier which part of mathematics he felt least prepared in, to which Born replied that it was the theory of ideals. According to Reid, Born optimistically inferred that Hilbert would let him off the hook as far as this part of mathematics was concerned, but he was in for a rude awakening. At the examination Hilbert focused exclusively on ideal theory! After it was all over, he said to the nonplussed Born: “Ja, ja, I just wanted to know how much you know about something about which you know nothing.” But of course Born did get his PhD and became a major player in physics (and the grandfather of Olivia Newton-John).

I feel a lot like the young Born in the presence of what I, as a number theorist, should know something about, but don’t: graph theory. I was schooled as an undergraduate in the ecumenical type of number theory that was practiced at UCLA in the 1970s, with E. G. Straus, Basil Gordon, Bruce Rothschild, and D. G. Cantor running part of the show. Thus combinatorics, Ramsey theory, and graph theory were everywhere. But so was algebraic number theory, in which these scholars were also wonderfully at home, of course. But there were others besides, notably Varadarajan and Steinberg, who were not so keen on the former areas, but hugely championed algebraic number theory, and I found myself in due course completely captivated by class field theory, algebraic number theory proper, and modular forms (the latter also being taught by Basil Gordon in his usual crystal clear fashion).

Nevertheless, I have always felt, and certainly still feel, that graph theory should be on my reading list. It is for this reason that I am excited about the book under review. I claim that there are a number of reasons why the book should appeal to a broader (and younger) audience: it presents an intrinsically appealing and accessible subject employing a well-developed algebraic machinery, thereby presenting the subject in a modern garb, making for connections with several exciting parts of mathematics that are currently undergoing a lot of growth.

Beyond this, the author of the book, Ulrich Knauer, offers it as a pedagogical opportunity in the sense that “[t]his book is a collection of the lectures I have given on algebraic graph theory … designed for mathematics students in a Master’s program but … also of interest to undergraduates in the final year of a Bachelor’s curriculum.” However he notes, too, that “[s]ome questions raised in the text could even be suitable as subjects of doctoral dissertations.” Thus, we have a classroom-tested text in our hands that affords us an exceptional flexibility, and it’s clearly not unreasonable that this should be so in an area such as graph theory. Knauer goes on to say that “[t]he advantage afforded by the field of algebraic graph theory is that it allows many questions to be understood from a general mathematical background and tackled almost immediately.” (And I recall that this was of course one of the most attractive features of the subject during my undergraduate days at UCLA: a lot of number theory enthusiasts were reeled in this way.)

On to the text proper, then. Knauer proposes to prepare his audience, students as well as other readers of the book, for research in algebraic graph theory and accordingly inserts “many ‘Questions’ as well as ‘Exercises,’ that lead to illuminating examples.” In addition, “Theorems for which [Knauer does] not give proofs are sometimes titled ‘Exerceorem,’ to stress their role in the development of the subject …” There are also “’Projects,’ which are designed as exercises to guide the reader in beginning their [sic] own research on the topic.” So there it is: a solid and sweeping introduction to an active and accessible area of research.

The book’s layout is really an interweaving of graph theory as such and the appropriate algebra. Knauer starts with directed and undirected graphs, then quickly gets to graphs and matrices. Next it’s some category theory, prior to the topic of binary graph operations. This is followed by unary graph operations, graphs and vector spaces, and then graphs, groups, and monoids. After all this it’s on to characteristic polynomials of graphs (something I think is intrinsically elegant), graphs and monoids, more on monoids, and finally three chapters dealing with different aspects of Cayley graphs.

It is clear, then, that Knauer’s book takes the reader on quite a voyage though the field, and provides a lot of opportunities for exploration and research. It is serious pedagogy as well as good scholarship. And it is indeed a good book for my aforementioned reading list.

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