2016/02/22 by Padrol, Arnau
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG)
paper · doi:10.48550/arxiv.1602.06894
We study the extension complexity of polytopes with few vertices or facets. On the one hand, we provide a complete classification of d-polytopes with at most d+4 vertices according to their extension complexity: Out of the super-exponentially many d-polytopes with d+4 vertices, all have extension complexity d+4 except for some families of size θ(d2). On the other hand, we show that generic realizations of simplicial/simple d-polytopes with d+1+α vertices/facets have extension complexity at least 2 √(d(d+α)) -d + 1, which shows that for all d>((α-1)/(2))2 there are d-polytopes with d+1+α vertices or facets and extension complexity d+1+α.