# Transactions of the American Mathematical Society

Published by the American Mathematical Society since 1900, Transactions of the American Mathematical Society is devoted to longer research articles in all areas of pure and applied mathematics.

ISSN 1088-6850 (online) ISSN 0002-9947 (print)

The 2020 MCQ for Transactions of the American Mathematical Society is 1.48.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

## Extension complexity of low-dimensional polytopesHTML articles powered by AMS MathViewer

by Matthew Kwan, Lisa Sauermann and Yufei Zhao
Trans. Amer. Math. Soc. 375 (2022), 4209-4250

## 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\sqrt n$. This bound is tight up to the constant factor $24$. Finally, we show that there exists an $n^{o(1)}$-dimensional polytope with at most $n$ vertices and extension complexity $n^{1-o(1)}$. Our theorems are proved with a range of different techniques, which we hope will be of further interest.

References
Similar Articles
• Retrieve articles in Transactions of the American Mathematical Society with MSC (2020): 52B05
• Retrieve articles in all journals with MSC (2020): 52B05
• Matthew Kwan
• Affiliation: IST Austria, Klosterneuburg, Austria
• MR Author ID: 1056015
• ORCID: 0000-0002-4003-7567
• Email: matthew.kwan@ist.ac.at
• Lisa Sauermann
• Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachussetts
• MR Author ID: 1051738
• Email: lsauerma@mit.edu
• Yufei Zhao
• Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts
• MR Author ID: 864404
• Email: yufeiz@mit.edu
• Received by editor(s): June 25, 2020
• Received by editor(s) in revised form: October 7, 2021
• Published electronically: March 31, 2022
• Additional Notes: The research of the first author was supported by SNSF Project 178493 and NSF Award DMS-1953990.
The research of the second author supported by NSF Award DMS-1953772.
The research of the third author was supported by NSF Award DMS-1764176, NSF CAREER Award DMS-2044606, a Sloan Research Fellowship, and the MIT Solomon Buchsbaum Fund.
• © Copyright 2022 Copyright by Matthew Kwan; Lisa Sauermann; Yufei Zhao
• Journal: Trans. Amer. Math. Soc. 375 (2022), 4209-4250
• MSC (2020): Primary 52B05
• DOI: https://doi.org/10.1090/tran/8614
• MathSciNet review: 4419057