[{"isi":1,"main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.2006.08836"}],"title":"Extension complexity of low-dimensional polytopes","external_id":{"isi":["000798461500001"],"arxiv":["2006.08836"]},"doi":"10.1090/tran/8614","year":"2022","publication_identifier":{"issn":["0002-9947"],"eissn":["1088-6850"]},"_id":"11443","quality_controlled":"1","oa_version":"Preprint","acknowledgement":"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.\r\nThe 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. ","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","arxiv":1,"article_processing_charge":"No","date_updated":"2023-08-03T07:17:37Z","oa":1,"volume":375,"abstract":[{"lang":"eng","text":"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."}],"author":[{"id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","first_name":"Matthew Alan","orcid":"0000-0002-4003-7567","full_name":"Kwan, Matthew Alan","last_name":"Kwan"},{"full_name":"Sauermann, Lisa","last_name":"Sauermann","first_name":"Lisa"},{"first_name":"Yufei","last_name":"Zhao","full_name":"Zhao, Yufei"}],"citation":{"ama":"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>","mla":"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>.","ista":"Kwan MA, Sauermann L, Zhao Y. 2022. Extension complexity of low-dimensional polytopes. Transactions of the American Mathematical Society. 375(6), 4209–4250.","short":"M.A. Kwan, L. Sauermann, Y. Zhao, Transactions of the American Mathematical Society 375 (2022) 4209–4250.","apa":"Kwan, M. A., Sauermann, L., &#38; 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>","ieee":"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.","chicago":"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>."},"publication_status":"published","date_created":"2022-06-12T22:01:45Z","department":[{"_id":"MaKw"}],"scopus_import":"1","publisher":"American Mathematical Society","language":[{"iso":"eng"}],"month":"06","article_type":"original","date_published":"2022-06-01T00:00:00Z","publication":"Transactions of the American Mathematical Society","issue":"6","page":"4209-4250","intvolume":"       375","status":"public","day":"01","type":"journal_article"},{"date_created":"2021-06-22T09:31:45Z","language":[{"iso":"eng"}],"scopus_import":"1","publisher":"American Mathematical Society","date_published":"2019-10-15T00:00:00Z","article_type":"original","month":"10","page":"5571-5594","publication":"Transactions of the American Mathematical Society","issue":"8","status":"public","intvolume":"       372","type":"journal_article","day":"15","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1090/tran/7729"}],"external_id":{"arxiv":["1712.05656"]},"title":"Proof of a conjecture on induced subgraphs of Ramsey graphs","doi":"10.1090/tran/7729","year":"2019","oa_version":"Submitted Version","quality_controlled":"1","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","extern":"1","publication_identifier":{"issn":["0002-9947"],"eissn":["1088-6850"]},"_id":"9585","article_processing_charge":"No","volume":372,"date_updated":"2023-02-23T14:01:50Z","oa":1,"arxiv":1,"author":[{"orcid":"0000-0002-4003-7567","last_name":"Kwan","full_name":"Kwan, Matthew Alan","first_name":"Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3"},{"full_name":"Sudakov, Benny","last_name":"Sudakov","first_name":"Benny"}],"abstract":[{"text":"An n-vertex graph is called C-Ramsey if it has no clique or independent set of size C log n. All known constructions of Ramsey graphs involve randomness in an essential way, and there is an ongoing line of research towards showing that in fact all Ramsey graphs must obey certain “richness” properties characteristic of random graphs. More than 25 years ago, Erdős, Faudree and Sós conjectured that in any C-Ramsey graph there are Ω(n^5/2) induced subgraphs, no pair of which have the same numbers of vertices and edges. Improving on earlier results of Alon, Balogh, Kostochka and Samotij, in this paper we prove this conjecture.","lang":"eng"}],"citation":{"chicago":"Kwan, Matthew Alan, and Benny Sudakov. “Proof of a Conjecture on Induced Subgraphs of Ramsey Graphs.” <i>Transactions of the American Mathematical Society</i>. American Mathematical Society, 2019. <a href=\"https://doi.org/10.1090/tran/7729\">https://doi.org/10.1090/tran/7729</a>.","apa":"Kwan, M. A., &#38; Sudakov, B. (2019). Proof of a conjecture on induced subgraphs of Ramsey graphs. <i>Transactions of the American Mathematical Society</i>. American Mathematical Society. <a href=\"https://doi.org/10.1090/tran/7729\">https://doi.org/10.1090/tran/7729</a>","ieee":"M. A. Kwan and B. Sudakov, “Proof of a conjecture on induced subgraphs of Ramsey graphs,” <i>Transactions of the American Mathematical Society</i>, vol. 372, no. 8. American Mathematical Society, pp. 5571–5594, 2019.","ista":"Kwan MA, Sudakov B. 2019. Proof of a conjecture on induced subgraphs of Ramsey graphs. Transactions of the American Mathematical Society. 372(8), 5571–5594.","short":"M.A. Kwan, B. Sudakov, Transactions of the American Mathematical Society 372 (2019) 5571–5594.","ama":"Kwan MA, Sudakov B. Proof of a conjecture on induced subgraphs of Ramsey graphs. <i>Transactions of the American Mathematical Society</i>. 2019;372(8):5571-5594. doi:<a href=\"https://doi.org/10.1090/tran/7729\">10.1090/tran/7729</a>","mla":"Kwan, Matthew Alan, and Benny Sudakov. “Proof of a Conjecture on Induced Subgraphs of Ramsey Graphs.” <i>Transactions of the American Mathematical Society</i>, vol. 372, no. 8, American Mathematical Society, 2019, pp. 5571–94, doi:<a href=\"https://doi.org/10.1090/tran/7729\">10.1090/tran/7729</a>."},"publication_status":"published"}]