Simple polytopes without small separators |
| |
Authors: | Lauri Loiskekoski Günter M Ziegler |
| |
Institution: | 1.Institut für Mathematik,FU Berlin,Berlin,Germany |
| |
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/log3/2 n). This disproves a conjecture by Kalai from 1991/2004. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |