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

Brinkmann, Philip; Ziegler, Günter

doi:10.1090/mcom/3300

Small $f$-vectors of 3-spheres and of 4-polytopes
HTML articles powered by AMS MathViewer

by Philip Brinkmann and Günter M. Ziegler PDF

Math. Comp. 87 (2018), 2955-2975 Request permission

Abstract:

We present a new algorithmic approach that can be used to determine whether a given quadruple $(f_0,f_1,f_2,f_3)$ is the $f$-vector of any convex $4$-dimensional polytope, or more generally of a strongly regular cellular $3$-sphere, that is, a regular cell complex homeomorphic to the $3$-dimensional sphere such that any intersection of two faces (cells) is a face.

By implementing this approach, we classify the $f$-vectors of $4$-polytopes in the range $f_0+f_3\le 22$.

In particular, we prove that there are $f$-vectors of strongly regular cellular $3$-spheres that are not $f$-vectors of any convex $4$-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 $f$-vectors with $f_0\le f_3$, namely $(10,32,33,11)$, $(10,33,35,12)$, and $(11,35,35,11)$.

References

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
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
David W. Barnette, The minimum number of vertices of a simple polytope, Israel J. Math. 10 (1971), 121–125. MR 298553, DOI 10.1007/BF02771522
David Barnette, Inequalities for $f$-vectors of $4$-polytopes, Israel J. Math. 11 (1972), 284–291. MR 295207, DOI 10.1007/BF02789320
David Barnette, A proof of the lower bound conjecture for convex polytopes, Pacific J. Math. 46 (1973), 349–354. MR 328773
David Barnette, The projection of the $f$-vectors of $4$-polytopes onto the $(E,\,S)$-plane, Discrete Math. 10 (1974), 201–216. MR 353148, DOI 10.1016/0012-365X(74)90117-4
David Barnette and John R. Reay, Projections of $f$-vectors of four-polytopes, J. Combinatorial Theory Ser. A 15 (1973), 200–209. MR 320890, DOI 10.1016/s0097-3165(73)80007-x
Margaret Bayer, The extended $f$-vectors of $4$-polytopes, J. Combin. Theory Ser. A 44 (1987), no. 1, 141–151. MR 871395, DOI 10.1016/0097-3165(87)90066-5
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
P. Brinkmann, f-Vector Spaces of Polytopes, Spheres, and Eulerian Lattices, PhD thesis, Freie Universität Berlin, Germany, 2016.
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, DOI 10.1112/S0025579316000267
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.
George E. Cooke and Ross L. Finney, Homology of cell complexes, Princeton University Press, Princeton, N.J.; University of Tokyo Press, Tokyo, 1967. Based on lectures by Norman E. Steenrod. MR 0219059
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, DOI 10.1201/9780203911211.ch18
Günter Ewald, Combinatorial convexity and algebraic geometry, Graduate Texts in Mathematics, vol. 168, Springer-Verlag, New York, 1996. MR 1418400, DOI 10.1007/978-1-4612-4044-0
M. Firsching, The complete enumeration of 4-polytopes and 3-spheres with nine vertices, in preparation, 2018.
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, DOI 10.1007/978-1-4613-0019-9
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
A. Höppner, $f$-Vectoren und Fahnenvektoren von $4$-dimensionalen Polytopen, Diplomarbeit, TU Berlin, 1998. (in German), 78 pages.
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
Gil Kalai, Rigidity and the lower bound theorem. I, Invent. Math. 88 (1987), no. 1, 125–151. MR 877009, DOI 10.1007/BF01405094
Victor Klee, A combinatorial analogue of Poincaré’s duality theorem, Canadian J. Math. 16 (1964), 517–531. MR 189039, DOI 10.4153/CJM-1964-053-0
Joseph M. Ling, New non-linear inequalities for flag-vectors of 4-poytopes, Discrete Comput. Geom. 37 (2007), no. 3, 455–469. MR 2301529, DOI 10.1007/s00454-006-1302-7
F. H. Lutz, GAP-program BISTELLAR. Second version (first version 1997 with A. Björner). page.math.tu-berlin.de/~lutz/, 1999. Software.
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
Brendan D. McKay and Adolfo Piperno, Practical graph isomorphism, II, J. Symbolic Comput. 60 (2014), 94–112. MR 3131381, DOI 10.1016/j.jsc.2013.09.003
P. McMullen, The numbers of faces of simplicial polytopes, Israel J. Math. 9 (1971), 559–570. MR 278183, DOI 10.1007/BF02771471
H. Miyata, Studies on Classifications and Constructions of Combinatorial Structures Related to Oriented Matroids, PhD thesis, University of Tokyo, 2011. xii+123 pages.
James R. Munkres, Elements of algebraic topology, Addison-Wesley Publishing Company, Menlo Park, CA, 1984. MR 755006
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, DOI 10.1090/conm/423/08083
Sage community, Sage 6.2, Sage Mathematical Software System. http://www. sagemath.org/. Software.
Richard P. Stanley, Enumerative combinatorics. Volume 1, 2nd ed., Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 2012. MR 2868112
E. Steinitz, Über die Eulerschen Polyederrelationen, Archiv für Mathematik und Physik, 11 (1906), pp. 86–88.
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.
Ernst Steinitz and Hans Rademacher, Vorlesungen über die Theorie der Polyeder unter Einschluss der Elemente der Topologie, Grundlehren der Mathematischen Wissenschaften, No. 41, Springer-Verlag, Berlin-New York, 1976. Reprint der 1934 Auflage. MR 0430958
A. Werner, Linear constraints on Face numbers of Polytopes, PhD thesis, Technische Universität Berlin, Germany, 2009. Published at https://opus4.kobv.de/.
Günter M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995. MR 1311028, DOI 10.1007/978-1-4613-8431-1
G. M. Ziegler, Face numbers of $4$-polytopes and $3$-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.