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

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 $(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 https://doi.org/10.1007/BF02771522
David Barnette, Inequalities for $f$-vectors of $4$-polytopes, Israel J. Math. 11 (1972), 284–291. MR 295207, DOI https://doi.org/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 https://doi.org/10.1016/0012-365X%2874%2990117-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 https://doi.org/10.1016/s0097-3165%2873%2980007-x
Margaret Bayer, The extended $f$-vectors of $4$-polytopes, J. Combin. Theory Ser. A 44 (1987), no. 1, 141–151. MR 871395, DOI https://doi.org/10.1016/0097-3165%2887%2990066-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 https://doi.org/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 https://doi.org/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

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

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 https://doi.org/10.1007/BF01405094

Victor Klee, A combinatorial analogue of Poincaré’s duality theorem, Canadian J. Math. 16 (1964), 517–531. MR 189039, DOI https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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, Springer-Verlag, Berlin-New York, 1976. Reprint der 1934 Auflage; Grundlehren der Mathematischen Wissenschaften, No. 41. 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

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.