Simple polytopes without small separators

DOI10.1007/S11856-017-1572-1MaRDI QIDQ1678493zbMATH OpenOpenAlexFDO

Authors Lauri Loiskekoski, Günter M. Ziegler

Publication date 17 November 2017

Published in Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.00511

zbMATH Keywords

separatorspolytope graphs

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Three-dimensional polytopes (52B10) Combinatorial inequalities (05A20)

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 $Omega(n/lo{g}^{3/2}n)$. This disproves a conjecture by Kalai from 1991/2004.

Recommendations

• Simple polytopes without small separators. II: Thurston's bound
• Connectivity of cubical polytopes
• Separation in neighbourly 4-polytopes
• Separation in totally-sewn 4-polytopes with the decreasing universal edge property
• A counterexample to the Perles conjecture

Cites work

• scientific article; zbMATH DE number 3957109 (Why is no real title available?)
• scientific article; zbMATH DE number 17653 (Why is no real title available?)
• scientific article; zbMATH DE number 2060183 (Why is no real title available?)
• scientific article; zbMATH DE number 6319745 (Why is no real title available?)
• A Separator Theorem for Planar Graphs
• Construction and analysis of projected deformed products
• Generalized Dehn-Sommerville relations for polytopes, spheres and Eulerian partially ordered sets
• Neighborly cubical polytopes
• Optimal numberings and isoperimetric problems on graphs
• Separators for sphere-packings and nearest neighbor graphs
• Stellar subdivisions of boundary complexes of convex polytopes

Cited in

(6)

• Non-existence of annular separators in geometric graphs
• Simple polytopes without small separators. II: Thurston's bound
• scientific article; zbMATH DE number 1760744 (Why is no real title available?)
• Spatial polyhedra without diagonals
• Connectivity of cubical polytopes
• Simple Euclidean arrangements with no \((\geq 5)\)-gons

This page was built for publication: Simple polytopes without small separators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1678493)