Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)



Realization spaces of 4-polytopes are universal

Authors: Jürgen Richter-Gebert and Günter M. Ziegler
Journal: Bull. Amer. Math. Soc. 32 (1995), 403-412
MSC: Primary 52B11; Secondary 52B55
MathSciNet review: 1316500
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ {P \subset \mathbb{R}^{d}}$ be a d-dimensional polytope. The realization space of P is the space of all polytopes $ P \subset \mathbb{R}^{d}$ that are combinatorially equivalent to P, modulo affine transformations. We report on work by the first author, which shows that realization spaces of 4-dimensional polytopes can be "arbitrarily bad": namely, for every primary semialgebraic set V defined over $ {\mathbb{Z}}$, there is a 4-polytope $ {P(V)}$ whose realization space is "stably equivalent" to V. This implies that the realization space of a 4-polytope can have the homotopy type of an arbitrary finite simplicial complex, and that all algebraic numbers are needed to realize all 4-polytopes. The proof is constructive.

These results sharply contrast the 3-dimensional case, where realization spaces are contractible and all polytopes are realizable with integral coordinates (Steinitz's Theorem). No similar universality result was previously known in any fixed dimension.

References [Enhancements On Off] (What's this?)

  • [1] D.W. Barnette, Two "simple" 3-spheres, Discrete Math. 67 (1987), 97-99. MR 908189 (88j:52013)
  • [2] D. Barnette and B. Grünbaum, Preassigning the shape of a face, Pacific J. Math. 32 (1970), 299-302. MR 0259744 (41:4377)
  • [3] M. Bayer and B. Sturmfels, Lawrence polytopes, Canad. J. Math. 42 (1990), 62-79. MR 1043511 (91e:52023)
  • [4] L.J. Billera and B.S. Munson, Polarity and inner products in oriented matroids, European J. Combin. 5 (1984), 293-308. MR 782051 (86e:05026)
  • [5] A. Björner, M. Las Vergnas, B. Sturmfels, N. White, and G.M. Ziegler, Oriented matroids, Encyclopedia of Mathematics, vol. 46, Cambridge Univ. Press, London and New York, 1993. MR 1226888 (95e:52023)
  • [6] J. Bokowski, G. Ewald, and P. Kleinschmidt, On combinatorial and affine automorphisms of polytopes, Israel J. Math. 47 (1984), 123-130. MR 738163 (85i:52001)
  • [7] J. Bokowski and A. Guedes de Oliveira, Simplicial convex 4-polytopes do not have the isotopy property, Portugal. Math. 47 (1990), 309-318. MR 1090270 (91k:52017)
  • [8] S.S. Cairns, Homeomorphisms between topological manifolds and analytic manifolds, Ann. of Math. 41 (1940), 796-808. MR 0002538 (2:71e)
  • [9] B. Grünbaum, Convex polytopes, Interscience, London, 1967; revised edition (V. Klee and P. Kleinschmidt, eds.), Springer-Verlag (in preparation). MR 1976856 (2004b:52001)
  • [10] H. Günzel, The universal partition theorem for oriented matroids, Discrete Comput. Geom. (to appear). MR 1368271 (97e:52016)
  • [11] H. Günzel, R. Hirabayashi, and H. Th. Jongen, Multiparametric optimization: On stable singularities occurring in combinatorial partition codes, Control Cybernet. 22 (1994), 153-167. MR 1284512 (95d:90080)
  • [12] P. Kleinschmidt, On facets with non-arbitrary shapes, Pacific J. Math. 65 (1976), 511-515. MR 0425771 (54:13724)
  • [13] -, Sphären mit wenigen Ecken, Geom. Dedicata 5 (1976), 97-101. MR 0493759 (58:12728)
  • [14] P. Mani, Spheres with few vertices, J. Combin. Theory Ser. A 13 (1972), 346-352. MR 0317175 (47:5723)
  • [15] N.E. Mnëv, The universality theorems on the classification problem of configuration varieties and convex polytopes varieties, Topology and Geometry - Rohlin Seminar (O. Ya. Viro, ed.), Lecture Notes in Math., vol. 1346, Springer-Verlag, Heidelberg, 1988, pp. 527-544. MR 970093 (90a:52013)
  • [16] -, The universality theorems on the oriented matroid stratification of the space of real matrices, Applied Geometry and Discrete Mathematics - The Victor Klee Festschrift (P. Gritzmann and B. Sturmfels, eds.), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 6, Amer. Math. Soc., Providence, RI, 1991, pp. 237-243. MR 1143301 (93d:14086)
  • [17] J. Richter-Gebert, Realization spaces of 4-polytopes are universal, Preprint 448/1995, Technical University, Berlin, 1995. MR 1316500 (96b:52020)
  • [18] P. Shor, Stretchability of pseudolines is NP-hard, Applied Geometry and Discrete Mathematics - The Victor Klee Festschrift (P. Gritzmann, B. Sturmfels, eds.), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 4, Amer. Math. Soc., Providence, RI, 1991, pp. 531-554. MR 1116375 (92g:05065)
  • [19] E. Steinitz, Polyeder und Raumeinteilungen, Encyclopädie der Mathematischen Wissenschaften, Band 3 (Geometrie) Teil 3AB12, Teubner, Leipzig, 1922, pp. 1-139.
  • [20] E. Steinitz and H. Rademacher, Vorlesungen über die Theorie der Polyeder, Springer-Verlag, Berlin, 1934; reprint, Springer-Verlag, 1976. MR 0430958 (55:3962)
  • [21] B. Sturmfels, Boundary complexes of convex polytopes cannot be characterized locally, Bull. London Math. Soc. 35 (1987), 314-326. MR 881520 (88e:52010)
  • [22] G.M. Ziegler, Three problems about 4-polytopes, Polytopes: Abstract, Convex and Computational (T. Bisztriczky, P. McMullen, and A. Weiss, eds.), Kluwer, Dordrecht, 1994, pp. 499-502. MR 1322074 (95m:52025)
  • [23] -, Lectures on polytopes, Graduate Texts in Math., vol. 152, Springer-Verlag, New York, 1995. MR 1311028 (96a:52011)

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC: 52B11, 52B55

Retrieve articles in all journals with MSC: 52B11, 52B55

Additional Information

Keywords: Polytopes, realization spaces, Steinitz's Theorem, universality, oriented matroids, semialgebraic sets, stable equivalence, NP-completeness
Article copyright: © Copyright 1995 American Mathematical Society

American Mathematical Society