Guillermo Pineda Villavicencio: “Polytopes and Graphs”

A polytope is the convex hull of finitely many points in a Euclidean space \(\mathbb{R}^{d}\). From this elementary definition the relevance of that concept in modern mathematics is all but obvious. In fact, the Platonic solids and their variations have been studied since antiquity. However, the deeper mathematical content remained dormant until the first modern monograph on the subject, by Branko Grünbaum, was published in 1967; for the revised and extended version see [4]. Grünbaum established polytope theory as subfield of mathematics. He explained where polytopes are located in the larger world of general convexity and analysis. That book also contains lots of constructions which are now standard, first classification results, open problems and more. It took some decades for the next textbook to appear, written by Günter M. Ziegler [10]. His book highlights the connections to linear programming, combinatorial topology and extremal combinatorics. Published shortly after Ziegler’s text, Günter Ewald’s book [2] can maybe considered the third one in this line. He explores the connection between polytope theory and algebraic geometry through toric varieties.

The book under review is different from its predecessors. Instead of adding more and more connections to further areas of mathematics, its first goal is to make the theory of polytopes widely accessible. To this end the author takes some time to recall the foundations from linear algebra and to develop the basic properties of polytopes slowly and carefully. In this way it takes him two chapters and 154 pages to arrive at Gale diagrams. It is instructive to compare this with the other books. In Ewald’s book [2] Gale transforms appear on page 52. In [10] Gale diagrams are defined only on page 168. However, in the chapters before that page Ziegler essentially browses through all the topics that occur in the book by Pineda Villavicencio. For sure such page numbers are not a good way to measure the quality of any book. Yet, I think, they help to show what sets the book under review apart from the others.

The second goal of “Polytopes and Graphs” can be deduced from its title, namely to describe polytope theory from a decidedly combinatorial angle. To explain what this means, I need to talk a bit more about polytopes. What makes them so useful is the fact that they are hybrid beings which live right at the border between geometry and combinatorics. Let \(P\subset \mathbb{R}^{d}\) be some polytope; we may assume that \(P\) affinely spans the entire space. Any affine hyperplane ℋ subdivides \(\mathbb{R}^{d}\) into two closed affine halfspaces, \(\mathcal{H}^{+}\) and \(\mathcal{H}^{-}\). Now ℋ is a supporting hyperplane of \(P\) if \(P\cap \mathcal{H}\neq \emptyset \) but \(P\) is entirely contained in \(\mathcal{H}^{+}\) or \(\mathcal{H}^{-}\). That intersection \(P\cap \mathcal{H}\) is the proper face of \(P\) cut out by ℋ. Faces are polytopes again, and they are partially ordered by inclusion. Adding \(\emptyset \) and \(P\) as non-proper faces yields a finite lattice, the face lattice \(\mathcal{F}(P)\). The faces are ranked by their dimensions, i.e., the dimensions of their affine hulls. More details can be found in §1.9 of the book under review. For instance, the regular icosahedron (which is one of the Platonic solids mentioned before) is the convex hull of 12 points in \(\mathbb{R}^{3}\), these form the 12 faces of dimension zero. In addition there are 20 triangular faces of dimension two and 30 faces of dimension one. Perturbing the 12 points slightly, and taking their convex hull, gives a different polytope, but, in this case, the face lattice remains the same. Passing from polytopes to their face lattices marks the transition from geometry to combinatorics. A good deal of modern polytope theory revolves around the question: What can we tell about a polytope when we only have its face lattice? And a variation of the same is: Given a lattice, is this the face lattice of some polytope?

The book under review takes the two questions above one step further. The faces of dimension zero are the vertices of a polytope \(P\), and the faces of dimension one are the edges. Together they form the vertex-edge graph \(G(P)\). By construction \(G(P)\) corresponds to the two lowest (proper) levels of the face lattice \(\mathcal{F}(P)\). That is, \(\mathcal{F}(P)\) determines \(G(P)\) but usually not the other way around. So “Polytopes and Graphs” actually studies the following questions: What properties does \(G(P)\) have? What can we tell about \(\mathcal{F}(P)\) from \(G(P)\)? Given a graph \(G\), does there exist some polytope \(P\) with \(G(P)=G\)?

Now we are equipped to discuss the contents of the book by Pineda Villavicencio more closely. To abbreviate we use the shortcut \(d\)-polytope instead of “\(d\)-dimensional polytope”. The first two chapters summarize the basics on convexity and polytopes, up to and including shellings, the equations of Euler and Dehn–Sommerville, and the Gale transforms mentioned above. It should be noted that in the first chapter many proofs are omitted and replaced by references to Roger Webster’s book on convexity [8].

Chapter 3 “Polytopal Graphs” sets the stage for the rest of the book. One focus here are the classical results of Steinitz and Tutte which say that, for 3-polytopes, the graph determines the entire face lattice. Moreover, there is an explicit procedure which starts from the vertex-edge graph of a 3-polytope, given as an abstract graph, and which yields coordinates for the vertices. A first non-standard topic is Sect. 3.4 on the “excess degrees” of graphs; this is about quantifying the deviation of the vertex-edge graph of a \(d\)-polytope from being \(d\)-regular.

Chapter 4 “Connectivity” forms a direct continuation of the previous one. The chapter title refers to the graph-theoretic notion: A graph is \(k\)-connected if removing any \(k{-}1\) of its vertices leaves the rest connected. For instance, the vertex-edge graphs of 3-polytopes are characterized by the property of being 3-connected and planar. The core of this chapter is another classical theorem, obtained by Balinski: The vertex-edge graph of a \(d\)-polytope is \(d\)-connected.

In Chap. 5 “Reconstruction” the author pursues the question to what extent the graph \(G(P)\) determines the face lattice \(\mathcal{F}(P)\), as well as some variations. The discussion starts out with a summary of results from Grünbaum’s book [4, §12.1]. From this it becomes obvious that, e.g., there are very many polytopes with distinct face lattices which share the same vertex-edge graphs. The point of departure for the rest of that chapter is a landmark result of Blind–Mani [1] that confirmed a conjecture of Perles: If \(P\) is a simple polytope, then \(G(P)\) defines \(\mathcal{F}(P)\) uniquely. Here a \(d\)-polytope is simple if its vertex-edge graph \(G(P)\) is \(d\)-regular. The icosahedron is not a simple polytope, but its polar dual, the dodecahedron is simple; it is a 3-polytope with a 3-regular vertex-edge graph. Shortly after [1] was published Kalai gave a spectacular new proof of the Blind–Mani result; that proof also occurs in [10, §3.4]. That proof is simple and deep at the same time, and it sparked a considerable amount of subsequent research on variations and improvements. Pineda Villavicencio collects many of these results and puts them into one uniform perspective. A highlight is Theorem 5.2.1 which says that every polytope which is not too far apart from a simple polytope can be reconstructed from its dimension and its 2-skeleton. The proof employs an algorithm of Friedman [3] in a crucial way. The \(k\)-skeleton of a polytope is the face lattice truncated to faces of dimension at most \(k\). Another interesting detail is a slight generalization of Kalai’s proof of the Blind–Mani theorem in Theorem 5.2.4.

Chapter 6 “Decomposition” is devoted to Minkowski sums of polytopes and, conversely, decompositions of polytopes into Minkowski summands.

The topic of Chap. 7 “Diameter” can again be guessed: it is about the diameter of the vertex-edges graph, i.e., the maximal length of a shortest path between any two vertices. That number plays a role in the complexity analysis of linear programming. The latter task is concerned with optimizing a linear objective function over a domain given by finitely many affine inequalities. It is a fundamental fact (Theorem 2.2.2, whose proof is offered per reference to [10, §1.3]) that each polytope (which affinely spans the space) agrees with the intersection of the affine halfspaces which correspond to those supporting hyperplanes which cut out proper faces of maximal dimension. In particular, each polytope arises as the feasible region of a linear program. The simplex method is a procedure which starts at some vertex and moves along improving edges to an optimal vertex; a summary of this algorithm from the geometric point of view is given, e.g., in [10, §3.2]. And so the diameter of \(G(P)\) is a lower bound on the number of simplex steps for a linear program with feasible region \(P\), in the worst case. This connection to linear programming is one reason for the interest in vertex-edge graphs of polytopes in the first place. The author collects several classical results, most of which can also be found in [10]. However, some new developments are covered, too. Most importantly, Santos’s celebrated counter-example to the Hirsch conjecture [6] is covered in §7.5. Moreover, the fairly recent strong general upper bound for the diameter by Todd [7] occurs as Theorem 7.4.8. To the best of my knowledge, this is the first time that these important results occur in a textbook.

The final Chap. 8 “Faces” is about the most fundamental statistics of polytopes. The \(f\)-vector counts the faces of a polytope by dimension. For instance, the \(f\)-vector of the dodecahedron reads \((20,30,12)\). The question which vectors arise as \(f\)-vectors of all polytopes or certain subclasses was, and continues to be, a fruitful source for inspiration. Pineda Villavicencio gives a comprehensive survey about what is known on this subject, including very recent results such as Xue’s proof of Grünbaum’s lower bound conjecture for general polytopes [9]. However, most proofs are again omitted.

These eight chapters are followed by an appendix, which is subdivided into three sections. They cover open problems, some topology and basic notions from graph theory, respectively. Each chapter follows the same pattern, in that there are two special sections at the end of each. One of the sections contains a list of problems, the other one adds references to the literature. Many interesting polytopes are given with explicit coordinates, e.g., the 5-prismatoid with 25 vertices and width six of Matschke–Santos–Weibel [5], which forms the building block of an improved counter-example to the Hirsch conjecture.

This finally leaves the question how this book can or should be used. In the preface the author describes how he envisions to use “Polytopes and Graphs” as a textbook for a course. Yet it is important to keep in mind that the author decided to omit many proofs at the beginning, in order to create space for recent developments. In my opinion, this makes this book a very good second source for a course on polytopes, in combination with one of the older books such as [4] or [10]. At any rate it is a very welcome addition to my bookshelf.