Realization spaces of polytopes.

*(English)*Zbl 0866.52009
Lecture Notes in Mathematics. 1643. Berlin: Springer. xi, 187 p. (1996).

Let \(P\) be a (convex) \(d\)-polytope, and pick \(d+1\) of its vertices which are necessarily affinely independent. (For example, let \(\varnothing=: F_{-1} \subset F_0\subset F_1 \subset\cdots \subset F_d:=P\) be faces with \(\dim F_j=j\), and let \(v_j\in F_j \backslash F_{j-1}\) be a vertex of \(P\) for \(j=0, \dots, d\); then \(v_0, \dots, v_d\) will serve.) The realization space of \(P\) then consists of all polytopes (combinatorially) isomorphic to \(P\) (parametrized, say, by their vertex-sets), for which the vertices corresponding to \(v_0, \dots, v_d\) coincide with a given affinely independent set. It has long been known (a result due to Steinitz) that, if \(d\leq 3\), then the realization space is an open ball of some dimension. The theory of Gale diagrams [see, for example, B. Grünbaum’s “Convex polytopes” [Wiley-Interscience (1967; Zbl 0163.16603)] shows that the same thing is true of \(d\)-polytopes with at most \(d+3\) vertices (or facets). However, outside this narrow range, the situation is strikingly different. A (basic) semi-algebraic set is one defined by polynomial equations or inequalities with integer coefficients; it is primary if only strict inequalities are permitted. Stable equivalence between semi-algebraic sets is a strong form of homotopy equivalence (the definition is a little technical). N. E. Mnëv [see, for example, Lect. Notes Math. 1346, 527-544 (1988; Zbl 0667.52006)] showed that every primary semi-algebraic set is stably equivalent to the realization space of some \(d\)-polytope with \(d+4\) vertices. The book under review contains the first full exposition of the author’s proof of the corresponding property for 4-polytopes; this formed his Habilitationsschrift for the TU Berlin in 1995.

The idea which underlies both results is that the algebraic operations of addition and multiplication can be encoded by von Staudt constructions in the real projective plane. (An intermediate step represents these equivalently as a Shor normal form, in variables \(1<x_1< \cdots<x_n\) for some \(n\), with equations only of the form \(x_i+x_j=x_k\) or \(x_i \cdot x_j=x_k\).) Mnëv could use this fact directly; however, Richter-Gebert has to lift the constructions up by two dimensions, if they are to correspond to convex polytopes. Each operation yields a 4-dimensional building block (the cases \(i=j\) need special treatment), and these blocks are then pasted together to give the final polytope with the required realization space. (We leave to the reader the pleasure of exploring the actual details.)

There are many consequences of this “universality theorem”; among them are the fact that all algebraic numbers are needed to coordinatize (the vertices of) 4-polytopes, and that the realizability problem for 4-polytopes is NP-hard. There are also “local non-Steinitz” results, to the effect that even parts of the face-lattices of 4-polytopes cannot be specified arbitrarily, and various algorithmic complexity results.

The author has rounded out his original thesis by discussing the case of ordinary polyhedra, giving a nice proof of Steinitz’s theorem using stresses in planar graphs, as well as non-Steinitz theorems in dimension 5 and realizability in dimension 6 (where the proof of the universality theorem is quite a bit more straightforward). With a comprehensive bibliography as well, this book provides a valuable (and well written) source-text for a fascinating topic.

The idea which underlies both results is that the algebraic operations of addition and multiplication can be encoded by von Staudt constructions in the real projective plane. (An intermediate step represents these equivalently as a Shor normal form, in variables \(1<x_1< \cdots<x_n\) for some \(n\), with equations only of the form \(x_i+x_j=x_k\) or \(x_i \cdot x_j=x_k\).) Mnëv could use this fact directly; however, Richter-Gebert has to lift the constructions up by two dimensions, if they are to correspond to convex polytopes. Each operation yields a 4-dimensional building block (the cases \(i=j\) need special treatment), and these blocks are then pasted together to give the final polytope with the required realization space. (We leave to the reader the pleasure of exploring the actual details.)

There are many consequences of this “universality theorem”; among them are the fact that all algebraic numbers are needed to coordinatize (the vertices of) 4-polytopes, and that the realizability problem for 4-polytopes is NP-hard. There are also “local non-Steinitz” results, to the effect that even parts of the face-lattices of 4-polytopes cannot be specified arbitrarily, and various algorithmic complexity results.

The author has rounded out his original thesis by discussing the case of ordinary polyhedra, giving a nice proof of Steinitz’s theorem using stresses in planar graphs, as well as non-Steinitz theorems in dimension 5 and realizability in dimension 6 (where the proof of the universality theorem is quite a bit more straightforward). With a comprehensive bibliography as well, this book provides a valuable (and well written) source-text for a fascinating topic.

Reviewer: P.McMullen (London)

##### MSC:

52B11 | \(n\)-dimensional polytopes |

52-02 | Research exposition (monographs, survey articles) pertaining to convex and discrete geometry |

52B40 | Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) |

14P10 | Semialgebraic sets and related spaces |

51A25 | Algebraization in linear incidence geometry |

52B10 | Three-dimensional polytopes |

52C35 | Arrangements of points, flats, hyperplanes (aspects of discrete geometry) |

68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |