Graphs and Geometry

Lázló Lovász sets the goal clearly in the preface:

 

 

The author is a well-known master of leveraging this perspective, and in his book Graphs and Geometry he demonstrates to us how to apply it. However, geometry and graph theory are each broad topics, and the best way to connect them depends heavily on what kinds of questions you want to ask. As such, what we get is not so much a theory as a collection of tools with which one can make those connections.

 

Each chapter is a short but thorough survey of some connection between graphs and geometry, with references and suggestions for how to dig further, and each closes with numerous exercises. The topics may seem eclectic but there is a broader narrative at work. Indeed, it is the commitment to showing the ideas at multiple scales that makes this book remarkable. We have many specific results and proofs, but the author is continually reminding us how the ideas connect to one another, and which techniques are variants of approaches taken earlier.

 

Much of the first half of the book concerns planar graphs. One key recurring construction, for example, is the rubber band representation of a graph, obtained by nailing the nodes of a graph to fixed points and allowing the rest of the graph to find an equilibrium configuration as if the edges were idealized rubber bands. We might first see this as a visualization technique, but this equilibrium is really solving an energy minimization problem. And when we do that, we can start thinking about harmonic functions, and the analytic functions… and so on. Indeed, much of the book is devoted to discrete models of harmonic and analytic functions, including electric networks, square tilings, circle packings, domino tilings, and statistical physics.

 

After that, the orthogonal representation, in which the nodes of the graph are mapped to vectors that are orthogonal if the corresponding nodes are not adjacent, emerges as a key tool. This is used to define the theta function (elsewhere called the Lovász number), which roughly measures the smallest cone containing the orthogonal representation, which turns out to capture much information about the graph. These tools reveal relationships to chromatic number, stable sets, Shannon capacity (both classical and quantum), and semidefinite optimization (a generalization of linear programming). Other topics include metric embeddings, the Colin de Verdière number, matching, and covering. The book closes with some bigger picture observations about the graph and geometric connections and their current applications, real and potential.

 

The material is generally accessible, although one should at least come equipped with some familiarity with graph theory and linear algebra, and review chapters and appendices will help close many gaps. But there is a lot of territory to cover and many topics will call on further background, and the broad narrative means the chapters are not self-contained. Thus this is a book meant for practitioners, although it should appeal to a wide range of disciplines.

 

There are some minor miswordings and other mishaps but they are mostly harmless. The book is extensively referenced throughout, with a thorough bibliography as well as author and subject indexes. A notation index or glossary would have been helpful.

 

The material surveyed here runs broad and deep, and Lovász does a fine job keeping the forest and the trees in sight at all times. The connections illustrated here will enlighten anyone interested in the topics, but also emphasize the value -- and the joy -- of maintaining a broad toolset in mathematics.

---

 

Bill Wood is an associate professor of mathematics at the University of Northern Iowa. His mathematical interests span geometry of all sorts, with special attention to discrete conformal geometry and special functions. He lives in Cedar Falls with his family and board game collection.