2017/08/22 by Loiskekoski, Lauri, Ziegler, Günter M. · 1 citation
#05C12 #05C40 #52B05 #52B11 #Combinatorics (math.CO) #FOS: Mathematics #Metric Geometry (math.MG)
paper · doi:10.48550/arxiv.1708.06718
We show that there are simple 4-dimensional polytopes with n vertices such that all separators of the graph have size at least Ω(n/log n). This establishes a strong form of a claim by Thurston, for which the construction and proof had been lost. We construct the polytopes by cutting off the vertices and then the edges of a particular type of neighborly cubical polytopes. The graphs of simple polytopes thus obtained are 4-regular; they contain 3-regular "cube-connected cycle graphs" as minors of spanning subgraphs.