Maximum Semidefinite and Linear Extension Complexity of Families of\n Polytopes

2016/05/27 by Gennadiy Averkov, Averkov, Gennadiy, Volker Kaibel +3
Computer Science · Engineering · #52Bxx (Secondary) #90C22 (Primary) #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Packing Problems

paper · pdf · doi:10.48550/arxiv.1605.08538

openalex publication_date 2016/05/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We relate the maximum semidefinite and linear extension complexity of a\nfamily of polytopes to the cardinality of this family and the minimum pairwise\nHausdorff distance of its members. This result directly implies a known lower\nbound on the maximum semidefinite extension complexity of 0/1-polytopes. We\nfurther show how our result can be used to improve on the corresponding bounds\nknown for polygons with integer vertices.\n Our geometric proof builds upon nothing else than a simple well-known\nproperty of maximum volume inscribed ellipsoids of convex bodies. In\nparticular, it does not rely on factorizations over the semidefinite cone and\nthus avoids involved procedures of balancing them as required, e.g., in [Briet,\nDadush & Pokutta 2015]. We hope that revealing the geometry behind the\nphenomenon opens doors for further results.\n Moreover, we show that the linear extension complexity of every d-dimensional\n0/1-polytope is bounded from above by O(2^d / d).\n

Related

• On the existence of 0/1 polytopes with high semidefinite extension complexity
• Extension complexity of low-dimensional polytopes
• Extension complexity of polytopes with few vertices or facets
• On the extension complexity of polytopes separating subsets of the Boolean cube
• Computing The Extension Complexities of All 4-Dimensional 0/1-Polytopes