Polytopes and Graphs

Polytopes and Graphs

Cambridge University Press, 2024, 480 pp.

Guillermo Pineda Villavicencio

Polytopes, which are $d$-dimensional analogues of convex polygons, have attracted attention for millennia. There are the famous Platonic solids—the tetrahedron, cube, octahedron, dodecahedron, and icosahedron—which appear in popular culture as common shapes for dice used in board games. Salvador Dalí blended religious imagery with a net of a tesseract in his painting Crucifixion (Corpus Hypercubus). The dodecahedron has even appeared at Burning Man in the form of the sculpture Unfolding Humanity; see Figure 1. There is an aesthetic appeal to polytopes; some ascribe an almost supernatural meaning to them. From time to time, they are even useful.

Polytopes have an enormous array of connections to various parts of mathematics. Their symmetries can be encoded by Coxeter groups; they appear in mathematical physics in the form of reflexive polytopes, the amplituhedron AHT14, cosmological polytopes AHBP17, and more; they can be viewed as cell complexes homeomorphic to a ball; and there are a plethora of other combinatorial connections. Learning about polytopes is an adventure, and Polytopes and Graphs provides a map between, well, polytopes and graphs.

Pineda Villavicencio intends this book for “undergraduate and graduate students, as well as any researcher interested in the fascinating world of graphs of polytopes.” It’s a daunting task, but he achieves it. This text could easily be used as part of a one- or two-semester course on polytopes and their graphs, providing lots of room for flexibility. Most chapters have roughly $15$ to $20$ exercises at the end, though one chapter has just three and another has five. The book also serves as a one-stop shop for state-of-the-art results, e.g., Xue’s proof of Grünbaum’s lower bound conjecture for faces of certain polytopes.

I found myself comparing this book with two classic texts on this topic: Lectures on Polytopes by Günter Ziegler Zie95 and Convex Polytopes by Branko Grünbaum Grü03. These are classics for a reason: they are accessible and thorough, and they touch on recent developments in the study of polytopes. However, as the world of polytopes is lively and new results appear frequently, an up-to-date text is welcome.

Figure 1.

Unfolding Humanity.

This is one of the biggest advantages of Polytopes and Graphs: it provides readers an accessible way to learn about polytopes, and it guides them to recent work. The book assumes familiarity with basic graph theory, but it kindly includes any necessary graph-theoretic background in an appendix. Of course, not every result can be proven in full detail, sometimes due to space and other times due to requiring techniques that stray too far from the central themes of the book. To remedy this, there are a generous number of footnote references and end-of-chapter discussions that point the reader to additional sources.

The first chapter contains some essential background on linear subspaces, relevant topological notions, as well as the fundamentals of affine, projective, and convex geometry. A researcher could easily skip this chapter or simply refer back to it as needed, but I strongly recommend students start here. While there are a lot of topics to cover, there are plenty of illustrations to help the readers build their intuition. At the same time, the chapter’s postscript—as with every chapter’s postscript—provides the interested reader with numerous sources for additional reading.

Momentum builds in the second chapter, where polyhedra are defined and studied carefully. They can be represented in two ways: one, using a finite set of linear equalities and inequalities, called the $H$-representation, and two, the sum of a cone and the convex hull of a finite set of points, called the $V$-representation. It’s nontrivial to show that every polyhedron has both an $H$-representation and $V$-representation, and the author takes time emphasizing the differences between the two.

Much of the rest of the chapter focuses on polytopes specifically. A polytope in $\mathbb{R}^n$ is simply a bounded polyhedron. It is sometimes helpful to refer to a polytope $P$ as a $d$-polytope if the dimension of the affine span of $P$ is $d$. Additionally, one may construct the graph of $P$ by using the vertices of $P$ as the vertices of the graph and declaring two vertices in the graph adjacent if and only if they share an edge in $P$. See Figure 2 for the graph of the icosahedron.

To help the reader become comfortable working with polytopes, Pineda Villavicencio introduces large classes of them and operations on them: simplices, (bi)pyramids, prisms, wedges, (polar) duals, Cartesian products, direct sums, free joins, subdivisions, shellings, and more are all included. He discusses ways to obtain combinatorial information about polytopes—such as face figures, Schlegel diagrams, and Gale diagrams—since, of course, once the dimension of a polytope exceeds three, it becomes much more difficult to envision. To illustrate, a Schlegel diagram of a $3$-polytope $P$ is a $2$-dimensional figure in which the graph of $P$ is easily viewable. Figure 2 is a concrete example: it can be viewed as not only the graph of the icosahedron, but as a Schlegel diagram of the icosahedron as well. Schlegel diagrams for $4$-polytopes are three-dimensional figures that, while not polytopes themselves, allow the viewer to identify which faces of the original polytope are included in higher-dimensional faces. In general, a Schlegel diagram of a $d$-polytope $P$ is a $(d-1)$-dimensional figure that captures the combinatorial structure of $P$.

Figure 2.

The graph of the icosahedron. When including the bounded faces of the graph, this is also a Schlegel diagram for the icosahedron.

This chapter provides a thorough treatment that prepares the reader with a strong foundation to continue. It is also in this chapter that hints of monumental results appear: it touches on computing face numbers, simple and simplicial polytopes, cyclic polytopes, the Euler-Poincaré-Shläfli equation, and the Dehn-Sommervile equations, among others.

Chapter 3 is where the first seminal result is presented. Indeed, I view this chapter as a story with Steinitz’s Theorem as its climax.

Theorem 1 (Steinitz, 1922 Ste22).

A graph is the graph of a $3$-polytope if and only if it is planar and $3$-connected.

Naturally, building up to this theorem requires establishing realizability results on graphs. A key piece is Tutte’s Realization Theorem, which establishes that every $3$-connected planar graph can be given a certain planar realization so that every edge is a line segment and every interior face is strictly convex. The proof of this theorem is presented in full, and though it can get fairly technical, clear and detailed examples are provided along the way. Elsewhere in the chapter, the reader encounters discussions of excess degrees, cycles in polytopes, the cycle space of a graph, and additional results on plane graphs. Alternative perspectives, consequences, and limits of Steinitz’s Theorem are included as well.

At this point, the reader has been exposed to a lot of results relating polytopes and graphs. Each subsequent chapter addresses a new viewpoint, highlighting both classical and modern results. Take Chapter 4: all of the attention given to $3$-connectivity of graphs thus far naturally leads one to wonder what the relationship is between $d$-connected graphs and $d$-polytopes. Pineda Villavicencio presents Balinski’s classic $1961$ result that $d$-polytopes have $d$-connected graphs, then follows up with a series of results on edge connectivity of graphs of $d$-polytopes.

The back half of the chapter puts more focus on $k$-linkedness in polytopes. Given a set $X$ of $2k$ vertices of a graph $G$ and a set of pairings $Y = \{\{s_1,t_1\},\dots ,\{s_k,t_k\}\}$ of the vertices in $X$, call $Y$ linked in $G$ if there are pairwise-disjoint $s_i$-$t_i$ paths in $G$ for all $1 \leq i \leq k$. Call $G$ $k$-linked if $G$ has at least $2k$ vertices, and, for every set $X$ of $2k$ vertices in $G$, every set of pairings $Y$ of $X$ as above is linked in $G$. This definition can be extended to polytopes: a polytope is $k$-linked if its graph is $k$-linked. It turns out that every simplicial $d$-polytope is $\lfloor (d+1)/2\rfloor$-linked. It is timely to study $k$-linkedness, as it has been recently shown that this is true for cubical polytopes: polytopes in which every face is a (combinatorial) cube.

Theorem 2 (Bui et al., 2024 BPVU24).

For every $d \neq 3$, a cubical $d$-polytope is $\lfloor (d+1)/2\rfloor$-linked. This is best possible in the sense that there exist cubical $d$-polytopes whose graphs are not $(d+1)$-connected.

Chapter 5 addresses a significantly different problem: if we only know the $k$-skeleton of the polytope, meaning the set of faces of dimension at most $k$, how much can actually be said about the polytope itself? Having the $(d-1)$-skeleton of a $d$-polytope certainly allows us to reconstruct the rest of it: after all, the only face missing is the polytope itself. Grünbaum showed that a $d$-polytope can still be reconstructed if only the $(d-2)$-skeleton is known. However, knowing the $(d-3)$-skeleton is not enough, and demonstrating so is nontrivial. Pineda Villavicencio shows the reader how to obtain these nonisomorphic polytopes with isomorphic $(d-3)$-skeletons before examining conditions in which reconstructing a polytope from a low-dimension skeleton is possible. While much of the background is standard, the chapter does provide newer updates. A nice recent result shows that a polytope can be reconstructed with minimal information if we know it is not too far from being simple.

Theorem 3 (Doolittle et al., 2018 DNPV$^{+}$19).

The face lattice of a polytope with at most one nonsimple vertex can be reconstructed from its dimension and its graph.

Earlier in the book, we learn how to put two polytopes together in various ways. Another important way is this: the Minkowski sum of polytopes $P, Q \subseteq \mathbb{R}^d$ is

$$\begin{equation*} P + Q = \{p + q \mid p \in P, q \in Q\}. \end{equation*}$$

Such a construction arises when, say, examining the Newton polytope $N(f)$ of a polynomial $f$. If $g$ is another polynomial in the same ring, then $N(fg) = N(f) + N(g)$. It may come as no surprise that trying to decompose a polytope into a Minkowski sum of other polytopes is no easy feat.

Chapter 6 studies this operation in greater depth, particularly in identifying when a polytope can be decomposed as a Minkowski sum. Although polytopes can exist in any dimension, their decomposability into a Minkowski sum can be detected just by their graphs.

Theorem 4 (Shephard, 1963 She63).

A polytope is a Minkowski sum if and only if its graph is decomposable.

This chapter proves the result and examines (in)decomposability criteria of various classes of polytopes.

While Chapter 7 is titled “Diameter,” I viewed it more as a condensed history of the Hirsch Conjecture and its variants. Given a connected graph $G$, the distance between two vertices $v$ and $w$ is the length of the shortest path between them. The diameter of $G$ is then the maximum distance over all choices of $v$ and $w$. One may extend this definition to polytopes and define the diameter of a polytope to be the diameter of its graph.

Hirsch conjectured that each $d$-dimensional polyhedron with $n$ facets, that is, its inclusion-maximal proper faces, has diameter at most $n-d$. This conjecture is not true: for unbounded polyhedra, Klee and Walkup disproved it in 1967, but it was not until over fifty years later that Santos disproved the conjecture for polytopes. In this chapter, Pineda Villavicencio presents Klee and Walkup’s counterexample to the unbounded case, their reduction of the bounded case to the $d$-step conjecture, the equivalence to the nonrevisiting conjecture, and finally Santos’s constructions disproving the bounded case.

Theorem 5 (Santos, 2012 San12).

There exists a $43$-dimensional polytope with $86$ facets and diameter $44$, thereby disproving the bounded Hirsch conjecture. Moreover, given any $d$-polytope $P$ with $n$ facets and diameter $(1+\varepsilon )(n-d)$ for $\varepsilon > 0$, the $k$-fold Cartesian product of $P$ is a $kd$-polytope with $kn$ facets and diameter $(1+\varepsilon )(kn-kd)$.

Modified versions of Hirsch’s original conjecture remain open.

Conjecture 6.

The diameter of the graph of a $d$-polytope with $n$ facets is at most polynomial in $d$ and $n$.

In fact, it remains open to determine whether “polynomial” can be replaced with “linear.”

The eighth and final chapter of the book returns to discussing faces of polytopes, this time focusing on face numbers and attempts at classifying valid sequences of face numbers of polytopes. More precisely, for a $d$-polytope $P$, its $f$-vector is $f(P) = (f_0,f_1,\dots , f_{d-1})$ where $f_i$ is the number of $i$-dimensional faces. Steinitz gave a complete characterization of $f$-vectors for $3$-polytopes, and various partial results for $4$-polytopes were found in the subsequent $100$ years. Only within the last ten years have partial characterizations for $f$-vectors of $5$-polytopes been established.

Theorem 7 (Pineda Villavicencio et al., 2018 PVUY18, Kusunoki and Murai, 2019 KM19).

There is a $5$-polytope $P$ with $f_0$ vertices and $f_1$ edges if and only if

$$\begin{equation*} 15 \leq \frac{5}{2}f_0 \leq f_1 \leq \binom{f_0}{2}, \qquad f_1 \neq \left\lfloor \frac{5}{2}f_0 + 1\right\rfloor , \end{equation*}$$

and $(f_0,f_1) \notin \{(8,20), (9,25), (13,35)\}$.

Of course, any chapter on face numbers of polytopes must—in this reviewer’s opinion—present the Upper Bound Theorem and the $g$-theorem for simplicial polytopes, since attempts to extend them to simplicial spheres inspired an enormous amount of research culminating in the works of Stanley Sta75 and Adiprasito, Papadakis, and Petrotou APP21. Fortunately, the author does so, but more importantly, he takes a portion of the chapter to present Xue’s proof of a 54-year-old conjecture by Grünbaum.

Theorem 8 (Xue, 2021 Xue21).

Suppose $d \geq 2$ and $1 \leq s \leq d$. If $P$ is a $d$-polytope with $d+s$ vertices, then

$$\begin{equation*} f_k(P) \geq \binom{d+1}{k+1} + \binom{d}{k+1} - \binom{d+1-s}{k+1} \end{equation*}$$

for all $k = 1, \dots , d-1$. Moreover, equality occurs for some $k \leq d-2$ exactly when $P$ is a $(d-s)$-fold pyramid over a simplicial $s$-prism.

Finally, there are three appendices: one collecting the open problems encountered throughout the text; one providing the necessary topological background; and one consisting of background on graph theory.

As delightful as this book is, it cannot possibly cover every topic that relates polytopes and graphs. One of the more notable absences—which may be glaring only to me due to my own mathematical biases—is the class of graph associahedra, which includes the permutohedron (see Figure 3) and the associahedron.

Figure 3.

The $3$-dimensional permutohedron.

Given a graph $G = ([n], E)$ where $[n] = \{1,\dots ,n\}$, let $\Delta _I \subseteq \mathbb{R}^n$ denote the convex hull of the standard basis vectors indexed by $I \subseteq [n]$. The corresponding graph associahedron $P_G$ is the Minkowski sum of all simplices $\Delta _I$ for which the subgraph of $G$ induced by $I$ is connected. The permutohedron arises when $G$ is a complete graph and the classical associahedron arises when $G$ is a path. Graph associahedra were introduced by Carr and Devadoss in $2006$ and became of great interest, notably as examples of generalized permutohedra Pos09.

Graph associahedra have graphs that are of interest in their own right: for example, each edge in the (classical) permutohedron corresponds to a pair of permutations $\pi _1\dots \pi _n$, $\sigma _1\dots \sigma _n$, written as words, which differ in exactly two positions $i < j$ such that $| \pi _i - \pi _j | = | \sigma _i - \sigma _j | = 1$. The graph of the classical associahedron coincides with the Hasse diagram of the Tamari lattice.

I should also note that there are occasional typos to keep an eye out for. The author encourages readers to point these out, and he keeps a list of errata on his website. None of the errata I have observed result in any significant drawback for the reader; they are typically superficial and the intended meaning is easily understood.

Ultimately, Pineda Villavicencio has produced a most welcome addition to the mathematical literature on polytopes. It is accessible and thorough, and it underscores developments from the past two decades: in other words, this book fills a gap within the existing set of texts. The book points the interested reader in numerous directions for further investigation and provides challenging exercises. I highly recommend it to anyone wishing to explore the world of polytopes, especially students.