Simple polytopes without small separators

2015/10/02 by Lauri Loiskekoski, Günter M. Ziegler, Loiskekoski, Lauri +1
Mathematics · #05C12 #05C40 #52B05 #52B11 #Combinatorics (math.CO) #FOS: Mathematics #Metric Geometry (math.MG) #math.CO #math.MG #msc:05C12 #msc:05C40 #msc:52B05 #msc:52B11

paper · pdf · doi:10.48550/arxiv.1510.00511

7 pages

arxiv created 2015/10/02 · arxiv updated 2015/10/05

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

Related

• Simple polytopes without small separators, II: Thurston's bound
• Reconstructing a non-simple polytope from its graph
• Neighborly cubical polytopes
• The special cuts of 600-cell
• Separation in Simply Linked Neighbourly 4-Polytopes