Notices of the American Mathematical Society
Welcome to the Notices of the American Mathematical Society.
With support from AMS membership, we are pleased to share the journal with the global mathematical community.
PDFLINK |
Polytopes and Graphs
Communicated by Notices Associate Editor Emily Olson

Polytopes and Graphs
Cambridge University Press, 2024, 480 pp.
Guillermo Pineda Villavicencio
Polytopes, which are 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
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 to 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
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 representation, and two, the sum of a cone and the convex hull of a finite set of points, called the -representation. It’s nontrivial to show that every polyhedron has both an -representation and -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 is simply a bounded polyhedron. It is sometimes helpful to refer to a polytope as a polytope if the dimension of the affine span of - is Additionally, one may construct the graph of . by using the vertices of as the vertices of the graph and declaring two vertices in the graph adjacent if and only if they share an edge in 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 polytope - is a dimensional figure in which the graph of - 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 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 -polytope - is a dimensional figure that captures the combinatorial structure of - .
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.
A graph is the graph of a polytope if and only if it is planar and -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 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 connectivity of graphs thus far naturally leads one to wonder what the relationship is between -connected graphs and -polytopes. Pineda Villavicencio presents Balinski’s classic - result that polytopes have -connected graphs, then follows up with a series of results on edge connectivity of graphs of -polytopes. -
The back half of the chapter puts more focus on linkedness in polytopes. Given a set - of vertices of a graph and a set of pairings of the vertices in call , linked in if there are pairwise-disjoint - paths in for all Call . linked if - has at least vertices, and, for every set of vertices in every set of pairings , of as above is linked in This definition can be extended to polytopes: a polytope is .linked if its graph is -linked. It turns out that every simplicial -polytope is -linked. It is timely to study -linkedness, as it has been recently shown that this is true for cubical polytopes: polytopes in which every face is a (combinatorial) cube. -
For every a cubical ,polytope is -linked. This is best possible in the sense that there exist cubical -polytopes whose graphs are not -connected. -
Chapter 5 addresses a significantly different problem: if we only know the skeleton of the polytope, meaning the set of faces of dimension at most - how much can actually be said about the polytope itself? Having the ,skeleton of a -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 -polytope can still be reconstructed if only the -skeleton is known. However, knowing the -skeleton is not enough, and demonstrating so is nontrivial. Pineda Villavicencio shows the reader how to obtain these nonisomorphic polytopes with isomorphic -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. -
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 is
Such a construction arises when, say, examining the Newton polytope of a polynomial If . is another polynomial in the same ring, then 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.
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 the distance between two vertices , and is the length of the shortest path between them. The diameter of is then the maximum distance over all choices of and 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 dimensional polyhedron with - facets, that is, its inclusion-maximal proper faces, has diameter at most 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 .step conjecture, the equivalence to the nonrevisiting conjecture, and finally Santos’s constructions disproving the bounded case. -
There exists a dimensional polytope with - facets and diameter thereby disproving the bounded Hirsch conjecture. Moreover, given any ,polytope - with facets and diameter for the ,fold Cartesian product of - is a polytope with - facets and diameter .
Modified versions of Hirsch’s original conjecture remain open.
The diameter of the graph of a polytope with - facets is at most polynomial in and .
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 polytope - its ,vector is - where is the number of dimensional faces. Steinitz gave a complete characterization of -vectors for -polytopes, and various partial results for -polytopes were found in the subsequent - years. Only within the last ten years have partial characterizations for vectors of -polytopes been established. -
There is a polytope - with vertices and edges if and only if
and .
Of course, any chapter on face numbers of polytopes must—in this reviewer’s opinion—present the Upper Bound Theorem and the theorem for simplicial polytopes, since attempts to extend them to simplicial spheres inspired an enormous amount of research culminating in the works of Stanley -
Suppose and If . is a polytope with - vertices, then
for all Moreover, equality occurs for some . exactly when is a fold pyramid over a simplicial -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.
The dimensional permutohedron. -
Given a graph where let , denote the convex hull of the standard basis vectors indexed by The corresponding graph associahedron . is the Minkowski sum of all simplices for which the subgraph of induced by is connected. The permutohedron arises when is a complete graph and the classical associahedron arises when is a path. Graph associahedra were introduced by Carr and Devadoss in and became of great interest, notably as examples of generalized permutohedra
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 , written as words, which differ in exactly two positions , such that 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.
References
[ APP21] - Karim Adiprasito, Stavros Argyrios Papadakis, and Vasiliki Petrotou, Anisotropy, biased pairings, and the lefschetz property for pseudomanifolds and cycles, 2021, https://arxiv.org/abs/2101.07245.,
Show rawAMSref
\bib{gThm}{misc}{ author={Adiprasito, Karim}, author={Papadakis, Stavros~Argyrios}, author={Petrotou, Vasiliki}, title={Anisotropy, biased pairings, and the lefschetz property for pseudomanifolds and cycles}, date={2021}, url={https://arxiv.org/abs/2101.07245}, }
[ AHBP17] - Nima Arkani-Hamed, Paolo Benincasa, and Alexander Postnikov, Cosmological polytopes and the wavefunction of the universe, 2017, https://arxiv.org/abs/1709.02813.,
Show rawAMSref
\bib{cosmological}{misc}{ author={Arkani-Hamed, Nima}, author={Benincasa, Paolo}, author={Postnikov, Alexander}, title={Cosmological polytopes and the wavefunction of the universe}, date={2017}, url={https://arxiv.org/abs/1709.02813}, }
[ AHT14] - Nima Arkani-Hamed and Jaroslav Trnka, The amplituhedron, J. High Energy Phys. 2014 (2014/10/06), no. 10, 30.,
Show rawAMSref
\bib{amplituhedron}{article}{ author={Arkani-Hamed, Nima}, author={Trnka, Jaroslav}, title={The amplituhedron}, date={2014/10/06}, journal={J. High Energy Phys.}, volume={2014}, number={10}, pages={30}, url={https://doi.org/10.1007/JHEP10(2014)030}, }
[ BPVU24] - Hoa T. Bui, Guillermo Pineda-Villavicencio, and Julien Ugon, The linkedness of cubical polytopes: beyond the cube, Discrete Math. 347 (2024), no. 3, Paper No. 113801, 17, DOI 10.1016/j.disc.2023.113801. MR4669479,
Show rawAMSref
\bib{BuiCubical}{article}{ author={Bui, Hoa T.}, author={Pineda-Villavicencio, Guillermo}, author={Ugon, Julien}, title={The linkedness of cubical polytopes: beyond the cube}, journal={Discrete Math.}, volume={347}, date={2024}, number={3}, pages={Paper No. 113801, 17}, issn={0012-365X}, review={\MR {4669479}}, doi={10.1016/j.disc.2023.113801}, }
[ DNPV 19] - Joseph Doolittle, Eran Nevo, Guillermo Pineda-Villavicencio, Julien Ugon, and David Yost, On the reconstruction of polytopes, Discrete Comput. Geom. 61 (2019), no. 2, 285–302, DOI 10.1007/s00454-018-9997-9. MR3903790,
Show rawAMSref
\bib{DoolittleReconstruction}{article}{ author={Doolittle, Joseph}, author={Nevo, Eran}, author={Pineda-Villavicencio, Guillermo}, author={Ugon, Julien}, author={Yost, David}, title={On the reconstruction of polytopes}, journal={Discrete Comput. Geom.}, volume={61}, date={2019}, number={2}, pages={285--302}, issn={0179-5376}, review={\MR {3903790}}, doi={10.1007/s00454-018-9997-9}, }
[ Grü03] - Branko Grünbaum, Convex polytopes, 2nd ed., Graduate Texts in Mathematics, vol. 221, Springer-Verlag, New York, 2003. Prepared and with a preface by Volker Kaibel, Victor Klee and Günter M. Ziegler, DOI 10.1007/978-1-4613-0019-9. MR1976856,
Show rawAMSref
\bib{Grunbaum}{book}{ author={Gr\"{u}nbaum, Branko}, title={Convex polytopes}, series={Graduate Texts in Mathematics}, volume={221}, edition={2}, note={Prepared and with a preface by Volker Kaibel, Victor Klee and G\"{u}nter M. Ziegler}, publisher={Springer-Verlag, New York}, date={2003}, pages={xvi+468}, isbn={0-387-00424-6}, isbn={0-387-40409-0}, review={\MR {1976856}}, doi={10.1007/978-1-4613-0019-9}, }
[ KM19] - Takuya Kusunoki and Satoshi Murai, The numbers of edges of 5-polytopes with a given number of vertices, Ann. Comb. 23 (2019), no. 1, 89–101, DOI 10.1007/s00026-019-00417-y. MR3921338,
Show rawAMSref
\bib{KusunokiMurai}{article}{ author={Kusunoki, Takuya}, author={Murai, Satoshi}, title={The numbers of edges of 5-polytopes with a given number of vertices}, journal={Ann. Comb.}, volume={23}, date={2019}, number={1}, pages={89--101}, issn={0218-0006}, review={\MR {3921338}}, doi={10.1007/s00026-019-00417-y}, }
[ PVUY18] - Guillermo Pineda-Villavicencio, Julien Ugon, and David Yost, The excess degree of a polytope, SIAM J. Discrete Math. 32 (2018), no. 3, 2011–2046, DOI 10.1137/17M1131994. MR3840883,
Show rawAMSref
\bib{PV}{article}{ author={Pineda-Villavicencio, Guillermo}, author={Ugon, Julien}, author={Yost, David}, title={The excess degree of a polytope}, journal={SIAM J. Discrete Math.}, volume={32}, date={2018}, number={3}, pages={2011--2046}, issn={0895-4801}, review={\MR {3840883}}, doi={10.1137/17M1131994}, }
[ Pos09] - Alexander Postnikov, Permutohedra, associahedra, and beyond, Int. Math. Res. Not. IMRN 6 (2009), 1026–1106, DOI 10.1093/imrn/rnn153. MR2487491,
Show rawAMSref
\bib{PostnikovBeyond}{article}{ author={Postnikov, Alexander}, title={Permutohedra, associahedra, and beyond}, journal={Int. Math. Res. Not. IMRN}, date={2009}, number={6}, pages={1026--1106}, issn={1073-7928}, review={\MR {2487491}}, doi={10.1093/imrn/rnn153}, }
[ San12] - Francisco Santos, A counterexample to the Hirsch conjecture, Ann. of Math. (2) 176 (2012), no. 1, 383–412, DOI 10.4007/annals.2012.176.1.7. MR2925387,
Show rawAMSref
\bib{SantosHirsch}{article}{ author={Santos, Francisco}, title={A counterexample to the Hirsch conjecture}, journal={Ann. of Math. (2)}, volume={176}, date={2012}, number={1}, pages={383--412}, issn={0003-486X}, review={\MR {2925387}}, doi={10.4007/annals.2012.176.1.7}, }
[ She63] - G. C. Shephard, Decomposable convex polyhedra, Mathematika 10 (1963), 89–95, DOI 10.1112/S0025579300003995. MR172176,
Show rawAMSref
\bib{ShephardDecomposable}{article}{ author={Shephard, G. C.}, title={Decomposable convex polyhedra}, journal={Mathematika}, volume={10}, date={1963}, pages={89--95}, issn={0025-5793}, review={\MR {172176}}, doi={10.1112/S0025579300003995}, }
[ Sta75] - Richard P. Stanley, The upper bound conjecture and Cohen-Macaulay rings, Studies in Appl. Math. 54 (1975), no. 2, 135–142, DOI 10.1002/sapm1975542135. MR458437,
Show rawAMSref
\bib{StanleyUBC}{article}{ author={Stanley, Richard P.}, title={The upper bound conjecture and Cohen-Macaulay rings}, journal={Studies in Appl. Math.}, volume={54}, date={1975}, number={2}, pages={135--142}, issn={0022-2526}, review={\MR {458437}}, doi={10.1002/sapm1975542135}, }
[ Ste22] - E. Steinitz, Polyeder und raumeinteilungen, 1922, pp. 1–139.,
Show rawAMSref
\bib{Steinitz}{incollection}{ author={Steinitz, E.}, title={Polyeder und raumeinteilungen}, date={1922}, pages={1--139}, }
[ Xue21] - Lei Xue, A proof of Grünbaum’s lower bound conjecture for general polytopes, Israel J. Math. 245 (2021), no. 2, 991–1000, DOI 10.1007/s11856-021-2234-x. MR4358269,
Show rawAMSref
\bib{XueLowerBound}{article}{ author={Xue, Lei}, title={A proof of Gr\"{u}nbaum's lower bound conjecture for general polytopes}, journal={Israel J. Math.}, volume={245}, date={2021}, number={2}, pages={991--1000}, issn={0021-2172}, review={\MR {4358269}}, doi={10.1007/s11856-021-2234-x}, }
[ Zie95] - Günter M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995, https://doi.org/10.1007/978-1-4613-8431-1. MR1311028,
Show rawAMSref
\bib{ZieglerLectures}{book}{ author={Ziegler, G\"unter~M.}, title={Lectures on polytopes}, series={Graduate Texts in Mathematics}, publisher={Springer-Verlag, New York}, date={1995}, volume={152}, isbn={0-387-94365-X}, url={https://doi.org/10.1007/978-1-4613-8431-1}, review={\MR {1311028}}, }
Credits
Book cover reproduced with the permission of the Cambridge University Press through PLSclear.
Figure 1 is courtesy of ArtBuilds (https://artbuilds.org/unfolding-humanity/).
Figures 2 and 3 are courtesy of Robert Davis.
Photo of Robert Davis is courtesy of Adam Brockway Photography.