Convex Polytopes

Last updated

Convex Polytopes is a graduate-level mathematics textbook about convex polytopes, higher-dimensional generalizations of three-dimensional convex polyhedra. It was written by Branko Grünbaum, with contributions from Victor Klee, Micha Perles, and G. C. Shephard, and published in 1967 by John Wiley & Sons. [1] [2] [3] [4] It went out of print in 1970. [5] [6] A second edition, prepared with the assistance of Volker Kaibel, Victor Klee, and Günter M. Ziegler, was published by Springer-Verlag in 2003, as volume 221 of their book series Graduate Texts in Mathematics. [5] [6] [7] [8]

Contents

Convex Polytopes was the winner of the 2005 Leroy P. Steele Prize for mathematical exposition, given by the American Mathematical Society. [9] The Basic Library List Committee of the Mathematical Association of America has recommended its inclusion in undergraduate mathematics libraries. [10]

Topics

The book has 19 chapters. After two chapters introducing background material in linear algebra, topology, and convex geometry, two more chapters provide basic definitions of polyhedra, in their two dual versions (intersections of half-spaces and convex hulls of finite point sets), introduce Schlegel diagrams, and provide some basic examples including the cyclic polytopes. Chapter 5 introduces Gale diagrams, and the next two chapters use them to study polytopes with a number of vertices only slightly higher than their dimension, and neighborly polytopes. [8] [5]

Chapters 8 through 11 study the numbers of faces of different dimensions in polytopes through Euler's polyhedral formula, the Dehn–Sommerville equations, and the extremal combinatorics of numbers of faces in polytopes. Chapter 11 connects the low-dimensional faces together into the skeleton of a polytope, and proves the van Kampen–Flores theorem about non-embeddability of skeletons into lower-dimensional spaces. Chapter 12 studies the question of when a skeleton uniquely determines the higher-dimensional combinatorial structure of its polytope. Chapter 13 provides a complete answer to this theorem for three-dimensional convex polytopes via Steinitz's theorem, which characterizes the graphs of convex polyhedra combinatorially and can be used to show that they can only be realized as a convex polyhedron in one way. It also touches on the multisets of face sizes that can be realized as polyhedra (Eberhard's theorem) and on the combinatorial types of polyhedra that can have inscribed spheres or circumscribed spheres. [8] [5]

Chapter 14 concerns relations analogous to the Dehn–Sommerville equations for sums of angles of polytopes, and uses sums of angles to define a central point, the "Steiner point", for any polytope. Chapter 15 studies Minkowski addition and Blaschke addition, two operations by which polytopes can be combined to produce other polytopes. Chapters 16 and 17 study shortest paths and the Hirsch conjecture, longest paths and Hamiltonian cycles, and the shortness exponent of polytopes. Chapter 18 studies arrangements of hyperplanes and their dual relation to the combinatorial structure of zonotopes. A concluding chapter, chapter 19, also includes material on the symmetries of polytopes. [8] [5]

Exercises throughout the book make it usable as a textbook, and provide additional links to recent research, and the later chapters of the book also list many open research problems. [1] The second edition of the book keeps the content, organization, and pagination of the first edition intact, adding to it notes at the ends of each chapter on updates to the material in that chapter. [7] [8] These updates include material on Mnëv's universality theorem and its relation to the realizability of polytopes from their combinatorial structures, the proof of the -conjecture for simplicial spheres, and Kalai's 3d conjecture. [8] The second edition also provides an improved bibliography. [6]

Topics that are important to the theory of convex polytopes but not well-covered in the book Convex Polytopes include Hilbert's third problem and the theory of Dehn invariants. [8]

Audience and reception

Although written at a graduate level, the main prerequisites for reading the book are linear algebra and general topology, both at an undergraduate level. [1]

In a review of the first edition of the book, Werner Fenchel calls it "a remarkable achievement", "a wealth of material", "well organized and presented in a lucid style". [2] Over 35 years later, in giving the Steele Prize to Grünbaum for Convex Polytopes, the American Mathematical Society wrote that the book "has served both as a standard reference and as an inspiration", that it was in large part responsible for the vibrant ongoing research in polyhedral combinatorics, and that it remained relevant to this area. [9] Reviewing and welcoming the second edition, Peter McMullen wrote that despite being "immediately rendered obsolete" by the research that it sparked, the book was still essential reading for researchers in this area. [8]

See also

Related Research Articles

Polyhedron Three-dimensional shape with flat polygonal faces, straight edges and sharp corners

In geometry, a polyhedron is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices. The word polyhedron comes from the Classical Greek πολύεδρον, as poly- + -hedron.

In solid geometry, a face is a flat (planar) surface that forms part of the boundary of a solid object; a three-dimensional solid bounded exclusively by faces is a polyhedron.

Discrete geometry Branch of geometry that studies combinatorial properties and constructive methods

Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles, spheres, polygons, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect one another, or how they may be arranged to cover a larger object.

Net (polyhedron)

In geometry a net of a polyhedron is an arrangement of non-overlapping edge-joined polygons in the plane which can be folded to become the faces of the polyhedron. Polyhedral nets are a useful aid to the study of polyhedra and solid geometry in general, as they allow for physical models of polyhedra to be constructed from material such as thin cardboard.

Convex polytope

A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the -dimensional Euclidean space . Most texts use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue. Yet other texts identify a convex polytope with its boundary.

Cauchy's theorem is a theorem in geometry, named after Augustin Cauchy. It states that convex polytopes in three dimensions with congruent corresponding faces must be congruent to each other. That is, any polyhedral net formed by unfolding the faces of the polyhedron onto a flat surface, together with gluing instructions describing which faces should be connected to each other, uniquely determines the shape of the original polyhedron. For instance, if six squares are connected in the pattern of a cube, then they must form a cube: there is no convex polyhedron with six square faces connected in the same way that does not have the same shape.

Flexible polyhedron

In geometry, a flexible polyhedron is a polyhedral surface without any boundary edges, whose shape can be continuously changed while keeping the shapes of all of its faces unchanged. The Cauchy rigidity theorem shows that in dimension 3 such a polyhedron cannot be convex.

Combinatorial commutative algebra is a relatively new, rapidly developing mathematical discipline. As the name implies, it lies at the intersection of two more established fields, commutative algebra and combinatorics, and frequently uses methods of one to address problems arising in the other. Less obviously, polyhedral geometry plays a significant role.

In algebraic combinatorics, the h-vector of a simplicial polytope is a fundamental invariant of the polytope which encodes the number of faces of different dimensions and allows one to express the Dehn–Sommerville equations in a particularly simple form. A characterization of the set of h-vectors of simplicial polytopes was conjectured by Peter McMullen and proved by Lou Billera and Carl W. Lee and Richard Stanley (g-theorem). The definition of h-vector applies to arbitrary abstract simplicial complexes. The g-conjecture stated that for simplicial spheres, all possible h-vectors occur already among the h-vectors of the boundaries of convex simplicial polytopes. It was proven in December 2018 by Karim Adiprasito.

Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes.

In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the (simple) 3-vertex-connected planar graphs. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs. Branko Grünbaum has called this theorem “the most important and deepest known result on 3-polytopes.”

In geometry and combinatorics, a simpliciald-sphere is a simplicial complex homeomorphic to the d-dimensional sphere. Some simplicial spheres arise as the boundaries of convex polytopes, however, in higher dimensions most simplicial spheres cannot be obtained in this way.

In geometry and polyhedral combinatorics, a k-neighborly polytope is a convex polytope in which every set of k or fewer vertices forms a face. For instance, a 2-neighborly polytope is a polytope in which every pair of vertices is connected by an edge, forming a complete graph. 2-neighborly polytopes with more than four vertices may exist only in spaces of four or more dimensions, and in general a k-neighborly polytope requires a dimension of 2k or more. A d-simplex is d-neighborly. A polytope is said to be neighborly, without specifying k, if it is k-neighborly for . If we exclude simplices, this is the maximum possible k: in fact, every polytope that is k-neighborly for some is a simplex.

In mathematics, a cyclic polytope, denoted C(n,d), is a convex polytope formed as a convex hull of n distinct points on a rational normal curve in Rd, where n is greater than d. These polytopes were studied by Constantin Carathéodory, David Gale, Theodore Motzkin, Victor Klee, and others. They play an important role in polyhedral combinatorics: according to the upper bound theorem, proved by Peter McMullen and Richard Stanley, the boundary Δ(n,d) of the cyclic polytope C(n,d) maximizes the number fi of i-dimensional faces among all simplicial spheres of dimension d − 1 with n vertices.

In combinatorial mathematics, an Eulerian poset is a graded poset in which every nontrivial interval has the same number of elements of even rank as of odd rank. An Eulerian poset which is a lattice is an Eulerian lattice. These objects are named after Leonhard Euler. Eulerian lattices generalize face lattices of convex polytopes and much recent research has been devoted to extending known results from polyhedral combinatorics, such as various restrictions on f-vectors of convex simplicial polytopes, to this more general setting.

In mathematics, the upper bound theorem states that cyclic polytopes have the largest possible number of faces among all convex polytopes with a given dimension and number of vertices. It is one of the central results of polyhedral combinatorics.

Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra is an undergraduate-level textbook in geometry, on the interplay between the volume of convex polytopes and the number of lattice points they contain. It was written by Matthias Beck and Sinai Robins, and published in 2007 by Springer-Verlag in their Undergraduate Texts in Mathematics series. A second edition was published in 2015, and a German translation of the first edition by Kord Eickmeyer, Das Kontinuum diskret berechnen, was published by Springer in 2008.

Lectures in Geometric Combinatorics is a textbook on polyhedral combinatorics. It was written by Rekha R. Thomas, based on a course given by Thomas at the 2004 Park City Mathematics Institute, and published by the American Mathematical Society and Institute for Advanced Study in 2006, as volume 33 of their Student Mathematical Library book series.

Convex Polyhedra is a book on the mathematics of convex polyhedra, written by Soviet mathematician Aleksandr Danilovich Aleksandrov, and originally published in Russian in 1950, under the title Выпуклые многогранники. It was translated into German by Wilhelm Süss as Konvexe Polyeder in 1958. An updated edition, translated into English by Nurlan S. Dairbekov, Semën Samsonovich Kutateladze and Alexei B. Sossinsky, with added material by Victor Zalgaller, L. A. Shor, and Yu. A. Volkov, was published as Convex Polyhedra by Springer-Verlag in 2005.

In the geometry of convex polytopes, the Minkowski problem for polytopes concerns the specification of the shape of a polytope by the directions and measures of its facets. The theorem that every polytope is uniquely determined up to translation by this information was proven by Hermann Minkowski; it has been called "Minkowski's theorem", although the same name has also been given to several unrelated results of Minkowski. The Minkowski problem for polytopes should also be distinguished from the Minkowski problem, on specifying convex shapes by their curvature.

References

  1. 1 2 3 Baxandall, P. R. (October 1969), "Review of Convex Polytopes (1st ed.)", The Mathematical Gazette , 53 (385): 342–343, doi:10.2307/3615008
  2. 1 2 Fenchel, Werner (Winter 1968), "Review of Convex Polytopes (1st ed.)", American Scientist , 56 (4): 476A–477A, JSTOR   27828384
  3. Sallee, G. T., "Review of Convex Polytopes (1st ed.)", MathSciNet , MR   0226496
  4. Jucovič, E., "Review of Convex Polytopes (1st ed.)", zbMATH (in German), Zbl   0163.16603
  5. 1 2 3 4 5 Zvonkin, Alexander (2004), "Review of Convex Polytopes (2nd ed.)", MathSciNet , MR   1976856
  6. 1 2 3 Ehrig, G., "Review of Convex Polytopes (2nd ed.)", zbMATH (in German), Zbl   1024.52001
  7. 1 2 Lord, Nick (March 2005), "Review of Convex Polytopes (2nd ed.)", The Mathematical Gazette , 89 (514): 164–166, JSTOR   3620690
  8. 1 2 3 4 5 6 7 8 McMullen, Peter (July 2005), "Review of Convex Polytopes (2nd ed.)", Combinatorics, Probability and Computing , 14 (4): 623–626, doi:10.1017/s0963548305226998
  9. 1 2 "2005 Steele Prizes" (PDF), Notices of the American Mathematical Society, 52 (4): 439–442, April 2005
  10. "Convex Polytopes (Basic Library List selection, no review)", MAA Reviews, Mathematical Association of America , retrieved 2020-08-26