Small 𝑓-vectors of 3-spheres and of 4-polytopes

Brinkmann, Philip; Ziegler, Günter

doi:10.1090/mcom/3300

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 $f_0+f_3\le 22$ .

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 $f_0+f_3\le 22$ , there are exactly three such -vectors with $f_0\le f_3$ , 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.