Regular Graphs

The theory of graphs is one of the easiest sells as far as getting someone into mathematics is concerned, real mathematics, that is, not just the routines of solving problems similar to what an instructor has done on a blackboard (or a white board, or even a smart board, as things stand now — let’s hope that there are no power pointers in the game, in any case). Consider the birth of the subject itself: the Königsberg bridges problem solved so brilliantly by Euler. I had occasion to discuss this in a recent course on the history of mathematics, and will have again this semester: I love teaching this course since the students (more mature at this point) get to see what marvels are available to them at this stage of their mathematical lives and to witness some of the magic of the trailblazers. The best effects, really, come about when the material is apparently transparent, turns out to be far subtler and nastier than a first impression might convey, and is at last dealt with effectively by a tour de force that is imbued with, yes, transparency and subtlety. Euler’s entire mathematical life might be presented as exemplifying this modus operandi.

Graph theory itself can possibly be characterized similarly, at least to some extent. The famous resolution of the 4-color conjecture comes to mind right away. Factoring out by the use of computers to grind through the very many cases required, the first move in the solution is still very evocative and instructive: make the countries into vertices and their shared borders into edges, and then start coloring (certainly a gross oversimplification of what Appell and Haaken did, but so be it).

And then there is the classic book, Groups and Their Graphs, by Israel Grossman and Wilhelm Magnus, where one encounters Cayley diagrams or Cayley graphs. In my own past, I recall doing one of my undergraduate senior theses on this material, and having a marvelous time of it. The corresponding material starts on p. 191 of the book under review.

All this having been said, the present book is a welcome addition to the literature. Says the author: “This book has been written to be of use to scientists working in the theory of graph spectra.” This is already a bit on the sophisticated side, but it’s still graph theory and is therefore more forgiving than, say, the theory of strongly inaccessible cardinals in the theory of sets — much more so. The author goes on to assuage our worries even more: “In this book we investigate exactly one class of graphs (regular) by using exactly one approach (spectral).” And here are the definitions: a graph is regular of degree \(r\) iff all its vertices have degree \(r\) (the degree is number of edges coming out of the vertex), and a graph spectrum is in fact the familiar linear algebra spectrum of the corresponding graph matrix, or adjacency matrix associated to the given graph. The latter matrix is given as \((a_{ij})\), where \(a_{ij}=1\) if vertex \(i\) connects to vertex \)j\) by means of an edge, and \(a_{ij}=0\) otherwise. The results one gets in this setting are varied, heavily combinatorially flavored, to coin a phrase, and often quite striking. For example, recall that a graph is bipartite if its chromatic number (the smallest \(k\) such that the graph can be colored with \(k\) colors) is 1 or 2. Then a graph is \(k\)-partite if its “set of vertices can be partitioned into \(k\) parts such that no two vertices in the same part are adjacent,” and in this way we get the notion of a multipartite graph (pick some \(k>1\)). Now we have, e.g., “Theorem 3.4.9. [p. 73] A strongly regular graph has the eigenvalue 0 if and only if it is a complete multipartite graph.” For the meanings of “strongly regular” and “complete” consult the text …

So, all in all, it’s very interesting material, and the results that pepper the book get a lot trickier than the example just cited. You get a lot of fancy estimates, and connections with all sorts of exotica (at least to me, who am not a graph theorist by any stretch of the imagination). We get, for example, material on random walks, Cayley expanders, and codes. I am reminded of the boast on the part of G. H. Hardy that his work in number theory was singularly immune to application: I was raised with the same belief. But then coding theory got hold of the subject, and this is certainly true in spades about combinatorics and graph theory. “The times, they are a-changing.”

It’s a well written and serious book, on an intrinsically accessible subject, modulo one’s willingness to work, of course. The proofs are there, but are pretty crisp, and there are lots of (good) exercises: time to get your hands nice and dirty.

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