Abstract
We show that by cutting off the vertices and then the edges of neighborly cubical polytopes, one obtains simple 4-dimensional polytopes with n vertices such that all separators of the graph have size at least Ω(n/log3/2 n). This disproves a conjecture by Kalai from 1991/2004.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
M. M. Bayer and L. J. Billera, Generalized Dehn-Sommerville relations for polytopes, spheres and Eulerian partially ordered sets, Inventiones Math. 79 (1985), 143–157.
B. Bollobas, Combinatorics, Cambridge University Press, Cambridge, 1986.
G. Ewald and G. C. Shephard, Stellar subdivisions of boundary complexes of convex polytopes, Math. Annalen 210 (1974), 7–16.
L. H. Harper, Optimal numberings and isoperimetric problems on graphs, J. Combinatorial Theory 1 (1966), 385–393.
L. H. Harper, Global methods for combinatorial isoperimetric problems, Cambridge University Press, Cambridge, 2004.
M. Joswig and G. M. Ziegler, Neighborly cubical polytopes, Discrete Comput. Geometry (Grünbaum Festschrift: G. Kalai and V. Klee, eds.) 24 (2000), 325–344.
G. Kalai, The diameter of graphs of convex polytopes and f-vector theory, in Applied Geometry and Discrete Mathematics — The Victor Klee Festschrift (P. Gritzmann and B. Sturmfels, eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 4, Amer. Math. Soc., Providence, RI, 1991, pp. 387–411.
G. Kalai, Polytope skeletons and paths, in Handbook of Discrete and Computational Geometry (J. E. Goodman and J. O’Rourke, eds.), CRC Press, Boca Raton, second ed., 2004, First edition 1997, pp. 455–476.
R. J. Lipton and R. E. Tarjan, A separator theorem for planar graphs, SIAM J. Applied Math. 36 (1979), 177–189.
G. L. Miller, S.-H. Teng, W. Thurston and S. A. Vavasis, Separators for sphere-packings and nearest neighbor graphs, J. ACM 44 (1997), 1–29.
G. L. Miller and W. Thurston, Separators in two and three dimensions, in Proc. 22nd Ann. ACM Symp. Theory Computing (Baltimore MD, May 1990) (New York), ACM, pp. 300–309.
R. Sanyal and G. M. Ziegler, Construction and analysis of projected deformed products, Discrete Comput. Geometry 43 (2010), 412–435.
J. Spencer and L. Florescu, Asymptopia, Student Math. Library, Vol. 71, Amer. Math. Soc., Providence, RI, 2014.
Author information
Authors and Affiliations
Corresponding author
Additional information
For Gil Kalai on the occasion of his sixtieth birthday
The first author was funded by DFG through the Berlin Mathematical School. Research by the second author was supported by the DFG Collaborative Research Center TRR 109 “Discretization in Geometry and Dynamics”.
Rights and permissions
About this article
Cite this article
Loiskekoski, L., Ziegler, G.M. Simple polytopes without small separators. Isr. J. Math. 221, 731–739 (2017). https://doi.org/10.1007/s11856-017-1572-1
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11856-017-1572-1