Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

On the extension complexity of low-dimensional polytopes

Algebra & Discrete Mathematics

Speaker: Lisa Sauermann, Institute for Advanced Study (IAS)
Related Webpage:
Location: Zoom
Start time: Thu, Feb 11 2021, 9:30AM

It is sometimes 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 in a (possibly higher-dimensional) polytope from which P can be obtained as a (linear) projection. In this talk, we discuss some results on the extension complexity of random d-dimensional polytopes (obtained as convex hulls of random points on either on the unit sphere or in the unit ball), and on the extension complexity of polygons with all vertices on a common circle. Joint work with Matthew Kwan and Yufei Zhao.

Lisa's slides can be found here