Simple polytopes without small separators (Q1678493)

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)].