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

polytope graphsseparators

Mathematics Subject Classification ID

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

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.

Review text

The authors introduce simple polytopes with n vertices such that all separators of their graphs have size at least \(\Omega\bigl(\frac{n}{\log^{3/2}(n)}\bigr)\) disproving a conjecture by Kalai from 1991/2004. The construction relies on the existence of neighborly cubical 4-polytopes first established in [\textit{M. Joswig} and the second author, Discrete Comput. Geom. 24, No. 2--3, 325--344 (2000; Zbl 1066.52012)]. By cutting the vertices and edges of such a polytope, one obtains a simple polytope whose graph is structurally similar to the graph of a hypercube but locally more entangled. The claim on the size of the separators follows by relating it with the asymptotics of separators of the hypercube graphs derived from [\textit{L. H. Harper}, J. Comb. Theory 1, 385--393 (1966; Zbl 0158.20802)]. Extending the construction to dimensions \(d>4\) by taking the product with a suitable hypercube yields a class of simple \(d\)-polytopes on \(n\) vertices without separators of size \(O\bigl(n^{1-\frac{1}{d-1}}\bigr)\) disproving Conjecture 20.2.12 by \textit{G. Kalai} [``Polytope skeletons and paths, in: Handbook of discrete and computational geometry. Boca Raton, FL: CRC Press. 331--344 (1997; Zbl 0910.52005)].

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

• 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
• 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?)
• 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)

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

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)