article
Extension complexity of low-dimensional polytopes
published
yes
Matthew Alan
Kwan
author 5fca0887-a1db-11eb-95d1-ca9d5e0453b30000-0002-4003-7567
Lisa
Sauermann
author
Yufei
Zhao
author
MaKw
department
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.
American Mathematical Society2022
eng
Transactions of the American Mathematical Society
0002-9947
1088-6850
2006.08836
00079846150000110.1090/tran/8614
37564209-4250
Kwan, Matthew Alan, et al. “Extension Complexity of Low-Dimensional Polytopes.” <i>Transactions of the American Mathematical Society</i>, vol. 375, no. 6, American Mathematical Society, 2022, pp. 4209–50, doi:<a href="https://doi.org/10.1090/tran/8614">10.1090/tran/8614</a>.
Kwan MA, Sauermann L, Zhao Y. Extension complexity of low-dimensional polytopes. <i>Transactions of the American Mathematical Society</i>. 2022;375(6):4209-4250. doi:<a href="https://doi.org/10.1090/tran/8614">10.1090/tran/8614</a>
Kwan MA, Sauermann L, Zhao Y. 2022. Extension complexity of low-dimensional polytopes. Transactions of the American Mathematical Society. 375(6), 4209–4250.
M.A. Kwan, L. Sauermann, Y. Zhao, Transactions of the American Mathematical Society 375 (2022) 4209–4250.
Kwan, Matthew Alan, Lisa Sauermann, and Yufei Zhao. “Extension Complexity of Low-Dimensional Polytopes.” <i>Transactions of the American Mathematical Society</i>. American Mathematical Society, 2022. <a href="https://doi.org/10.1090/tran/8614">https://doi.org/10.1090/tran/8614</a>.
M. A. Kwan, L. Sauermann, and Y. Zhao, “Extension complexity of low-dimensional polytopes,” <i>Transactions of the American Mathematical Society</i>, vol. 375, no. 6. American Mathematical Society, pp. 4209–4250, 2022.
Kwan, M. A., Sauermann, L., & Zhao, Y. (2022). Extension complexity of low-dimensional polytopes. <i>Transactions of the American Mathematical Society</i>. American Mathematical Society. <a href="https://doi.org/10.1090/tran/8614">https://doi.org/10.1090/tran/8614</a>
114432022-06-12T22:01:45Z2024-10-09T21:02:31Z