---
res:
bibo_abstract:
- Sometimes, it is possible to represent a complicated polytope as a projection
of a much simpler polytope. To quantify this phenomenon, the extension complexity
of a polytope P is defined to be the minimum number of facets of a (possibly higher-dimensional)
polytope from which P can be obtained as a (linear) projection. This notion is
motivated by its relevance to combinatorial optimisation, and has been studied
intensively for various specific polytopes associated with important optimisation
problems. In this paper we study extension complexity as a parameter of general
polytopes, more specifically considering various families of low-dimensional polytopes.
First, we prove that for a fixed dimension d, the extension complexity of a random
d-dimensional polytope (obtained as the convex hull of random points in a ball
or on a sphere) is typically on the order of the square root of its number of
vertices. Second, we prove that any cyclic n-vertex polygon (whose vertices lie
on a circle) has extension complexity at most 24√n. This bound is tight up to
the constant factor 24. Finally, we show that there exists an no(1)-dimensional
polytope with at most n vertices and extension complexity n1−o(1). Our theorems
are proved with a range of different techniques, which we hope will be of further
interest.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Matthew Alan
foaf_name: Kwan, Matthew Alan
foaf_surname: Kwan
foaf_workInfoHomepage: http://www.librecat.org/personId=5fca0887-a1db-11eb-95d1-ca9d5e0453b3
orcid: 0000-0002-4003-7567
- foaf_Person:
foaf_givenName: Lisa
foaf_name: Sauermann, Lisa
foaf_surname: Sauermann
- foaf_Person:
foaf_givenName: Yufei
foaf_name: Zhao, Yufei
foaf_surname: Zhao
bibo_doi: 10.1090/tran/8614
bibo_issue: '6'
bibo_volume: 375
dct_date: 2022^xs_gYear
dct_identifier:
- UT:000798461500001
dct_isPartOf:
- http://id.crossref.org/issn/0002-9947
- http://id.crossref.org/issn/1088-6850
dct_language: eng
dct_publisher: American Mathematical Society@
dct_title: Extension complexity of low-dimensional polytopes@
...