2014/06/18 by Michael L. Oelze, Michael Oelze, Arnaud Vandaele +4
Computer Science · Engineering · Mathematics · #52Bxx #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #graph theory and CDMA systems #math.CO #msc:52Bxx
paper · pdf · doi:10.48550/arxiv.1406.4895
20 pages
arxiv created 2014/06/18 · openalex publication_date 2014/06/18 · arxiv updated 2014/06/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present slight refinements of known general lower and upper bounds on sizes of extended formulations for polytopes. With these observations we are able to compute the extension complexities of all 0/1-polytopes up to dimension 4. We provide a complete list of our results including geometric constructions of minimum size extensions for all considered polytopes. Furthermore, we show that all of these extensions have strong properties. In particular, one of our computational results is that every 0/1-polytope up to dimension 4 has a minimum size extension that is also a 0/1-polytope.