Small -vectors of 3-spheres and of 4-polytopes
Authors:
Philip Brinkmann and Günter M. Ziegler
Journal:
Math. Comp. 87 (2018), 2955-2975
MSC (2010):
Primary 52B11, 52B55; Secondary 52C40
DOI:
https://doi.org/10.1090/mcom/3300
Published electronically:
February 14, 2018
MathSciNet review:
3834694
Full-text PDF
Abstract | References | Similar Articles | Additional Information
Abstract: We present a new algorithmic approach that can be used to determine whether a given quadruple is the
-vector of any convex
-dimensional polytope, or more generally of a strongly regular cellular
-sphere, that is, a regular cell complex homeomorphic to the
-dimensional sphere such that any intersection of two faces (cells) is a face.
By implementing this approach, we classify the -vectors of
-polytopes in the range
.
In particular, we prove that there are -vectors of strongly regular cellular
-spheres that are not
-vectors of any convex
-polytopes. This answers a question that may be traced back to the works of Steinitz (1906/1922). In the range
, there are exactly three such
-vectors with
, namely
,
, and
.
- [1] Amos Altshuler and Leon Steinberg, Enumeration of the quasisimplicial 3-spheres and 4-polytopes with eight vertices, Pacific J. Math. 113 (1984), no. 2, 269–288. MR 749536
- [2] Amos Altshuler and Leon Steinberg, The complete enumeration of the 4-polytopes and 3-spheres with eight vertices, Pacific J. Math. 117 (1985), no. 1, 1–16. MR 777434
- [3] David W. Barnette, The minimum number of vertices of a simple polytope, Israel J. Math. 10 (1971), 121–125. MR 298553, https://doi.org/10.1007/BF02771522
- [4] David Barnette, Inequalities for 𝑓-vectors of 4-polytopes, Israel J. Math. 11 (1972), 284–291. MR 295207, https://doi.org/10.1007/BF02789320
- [5] David Barnette, A proof of the lower bound conjecture for convex polytopes, Pacific J. Math. 46 (1973), 349–354. MR 328773
- [6] David Barnette, The projection of the 𝑓-vectors of 4-polytopes onto the (𝐸,𝑆)-plane, Discrete Math. 10 (1974), 201–216. MR 353148, https://doi.org/10.1016/0012-365X(74)90117-4
- [7] David Barnette and John R. Reay, Projections of 𝑓-vectors of four-polytopes, J. Combinatorial Theory Ser. A 15 (1973), 200–209. MR 320890, https://doi.org/10.1016/s0097-3165(73)80007-x
- [8] Margaret Bayer, The extended 𝑓-vectors of 4-polytopes, J. Combin. Theory Ser. A 44 (1987), no. 1, 141–151. MR 871395, https://doi.org/10.1016/0097-3165(87)90066-5
- [9] Margaret M. Bayer and Carl W. Lee, Combinatorial aspects of convex polytopes, Handbook of convex geometry, Vol. A, B, North-Holland, Amsterdam, 1993, pp. 485–534. MR 1242988
- [10] P. Brinkmann, f-Vector Spaces of Polytopes, Spheres, and Eulerian Lattices, PhD thesis, Freie Universität Berlin, Germany, 2016.
- [11] Philip Brinkmann and Günter M. Ziegler, A flag vector of a 3-sphere that is not the flag vector of a 4-polytope, Mathematika 63 (2017), no. 1, 260–271. MR 3610014, https://doi.org/10.1112/S0025579316000267
- [12] J. M. Brückner, Über die Ableitung der allgemeinen Polytope und die nach Isomorphismus verschiedenen Typen der allgemeinen Achtzelle, Verhand. Konink. Akad. Wetenschap, Erste Sectie, 10 (1909), no. 1.
- [13] George E. Cooke and Ross L. Finney, Homology of cell complexes, Based on lectures by Norman E. Steenrod, Princeton University Press, Princeton, N.J.; University of Tokyo Press, Tokyo, 1967. MR 0219059
- [14] David Eppstein, Greg Kuperberg, and Günter M. Ziegler, Fat 4-polytopes and fatter 3-spheres, Discrete geometry, Monogr. Textbooks Pure Appl. Math., vol. 253, Dekker, New York, 2003, pp. 239–265. MR 2034720, https://doi.org/10.1201/9780203911211.ch18
- [15] Günter Ewald, Combinatorial convexity and algebraic geometry, Graduate Texts in Mathematics, vol. 168, Springer-Verlag, New York, 1996. MR 1418400
- [16] M. Firsching, The complete enumeration of 4-polytopes and 3-spheres with nine vertices, in preparation, 2018.
- [17] 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. MR 1976856
- [18] Branko Grünbaum and V. P. Sreedharan, An enumeration of simplicial 4-polytopes with 8 vertices, J. Combinatorial Theory 2 (1967), 437–465. MR 215182
- [19]
A. Höppner,
-Vectoren und Fahnenvektoren von
-dimensionalen Polytopen, Diplomarbeit, TU Berlin, 1998.
(in German), 78 pages. - [20] Andrea Höppner and Günter M. Ziegler, A census of flag-vectors of 4-polytopes, Polytopes—combinatorics and computation (Oberwolfach, 1997) DMV Sem., vol. 29, Birkhäuser, Basel, 2000, pp. 105–110. MR 1785294
- [21] Gil Kalai, Rigidity and the lower bound theorem. I, Invent. Math. 88 (1987), no. 1, 125–151. MR 877009, https://doi.org/10.1007/BF01405094
- [22] Victor Klee, A combinatorial analogue of Poincaré’s duality theorem, Canadian J. Math. 16 (1964), 517–531. MR 189039, https://doi.org/10.4153/CJM-1964-053-0
- [23] Joseph M. Ling, New non-linear inequalities for flag-vectors of 4-poytopes, Discrete Comput. Geom. 37 (2007), no. 3, 455–469. MR 2301529, https://doi.org/10.1007/s00454-006-1302-7
- [24]
F. H. Lutz, GAP-program BISTELLAR. Second version (first version 1997 with A. Björner).
page.math.tu-berlin.de/~lutz/, 1999.
Software. - [25] Frank Hagen Lutz, Triangulated manifolds with few vertices and vertex-transitive group actions, Berichte aus der Mathematik. [Reports from Mathematics], Verlag Shaker, Aachen, 1999 (English, with German summary). Dissertation, Technischen Universität Berlin, Berlin, 1999. MR 1866007
- [26] Brendan D. McKay and Adolfo Piperno, Practical graph isomorphism, II, J. Symbolic Comput. 60 (2014), 94–112. MR 3131381, https://doi.org/10.1016/j.jsc.2013.09.003
- [27] P. McMullen, The numbers of faces of simplicial polytopes, Israel J. Math. 9 (1971), 559–570. MR 278183, https://doi.org/10.1007/BF02771471
- [28]
H. Miyata, Studies on Classifications and Constructions of Combinatorial Structures Related to Oriented Matroids, PhD thesis, University of Tokyo, 2011.
xii+123 pages. - [29] James R. Munkres, Elements of algebraic topology, Addison-Wesley Publishing Company, Menlo Park, CA, 1984. MR 755006
- [30] Andreas Paffenholz and Axel Werner, Constructions for 4-polytopes and the cone of flag vectors, Algebraic and geometric combinatorics, Contemp. Math., vol. 423, Amer. Math. Soc., Providence, RI, 2006, pp. 283–303. MR 2298763, https://doi.org/10.1090/conm/423/08083
- [31]
Sage community, Sage 6.2, Sage Mathematical Software System.
http://www. sagemath.org/.
Software. - [32] Richard P. Stanley, Enumerative combinatorics. Volume 1, 2nd ed., Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 2012. MR 2868112
- [33] E. Steinitz, Über die Eulerschen Polyederrelationen, Archiv für Mathematik und Physik, 11 (1906), pp. 86-88.
- [34] E. Steinitz, Polyeder und Raumeinteilungen, in Encyklopädie der mathematischen Wissenschaften mit Einschluss ihrer Anwendungen, Band III.1.2, W. F. Meyer and H. Mohrmann, eds., vol. 9, Teubner, Leipzig, 1922, ch. AB12, pp. 1-139.
- [35] Ernst Steinitz and Hans Rademacher, Vorlesungen über die Theorie der Polyeder unter Einschluss der Elemente der Topologie, Springer-Verlag, Berlin-New York, 1976. Reprint der 1934 Auflage; Grundlehren der Mathematischen Wissenschaften, No. 41. MR 0430958
- [36]
A. Werner, Linear constraints on Face numbers of Polytopes, PhD thesis, Technische Universität Berlin, Germany, 2009.
Published at https://opus4.kobv.de/. - [37] Günter M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995. MR 1311028
- [38]
G. M. Ziegler, Face numbers of
-polytopes and
-spheres, in Proceedings of the International Congress of Mathematicians (ICM 2002, Beijing), L. Tatsien, ed., vol. III, Beijing, China, 2002, Higher Education Press, pp. 625-634.
Retrieve articles in Mathematics of Computation with MSC (2010): 52B11, 52B55, 52C40
Retrieve articles in all journals with MSC (2010): 52B11, 52B55, 52C40
Additional Information
Philip Brinkmann
Affiliation:
Institut für Mathematik, FU Berlin Arnimallee 2 14195 Berlin, Germany
Email:
webmaster@phi-fotos.de
Günter M. Ziegler
Affiliation:
Institut für Mathematik, FU Berlin Arnimallee 2 14195 Berlin, Germany
Email:
ziegler@math.fu-berlin.de
DOI:
https://doi.org/10.1090/mcom/3300
Received by editor(s):
October 19, 2016
Received by editor(s) in revised form:
March 26, 2017, and May 27, 2017
Published electronically:
February 14, 2018
Additional Notes:
The first author was funded by DFG through the RTG Methods for Discrete Structures.
The second author was supported by DFG via the Collaborative Research Center TRR 109 “Discretization in Geometry and Dynamics”.
Article copyright:
© Copyright 2018
American Mathematical Society