Simple polytopes without small separators

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

arXiv comment7 pages