---
_id: '11443'
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.
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. "
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Matthew Alan
  full_name: Kwan, Matthew Alan
  id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3
  last_name: Kwan
  orcid: 0000-0002-4003-7567
- first_name: Lisa
  full_name: Sauermann, Lisa
  last_name: Sauermann
- first_name: Yufei
  full_name: Zhao, Yufei
  last_name: Zhao
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>
  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>
  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>.
  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.
  ista: Kwan MA, Sauermann L, Zhao Y. 2022. Extension complexity of low-dimensional
    polytopes. Transactions of the American Mathematical Society. 375(6), 4209–4250.
  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>.
  short: M.A. Kwan, L. Sauermann, Y. Zhao, Transactions of the American Mathematical
    Society 375 (2022) 4209–4250.
date_created: 2022-06-12T22:01:45Z
date_published: 2022-06-01T00:00:00Z
date_updated: 2023-08-03T07:17:37Z
day: '01'
department:
- _id: MaKw
doi: 10.1090/tran/8614
external_id:
  arxiv:
  - '2006.08836'
  isi:
  - '000798461500001'
intvolume: '       375'
isi: 1
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: ' https://doi.org/10.48550/arXiv.2006.08836'
month: '06'
oa: 1
oa_version: Preprint
page: 4209-4250
publication: Transactions of the American Mathematical Society
publication_identifier:
  eissn:
  - 1088-6850
  issn:
  - 0002-9947
publication_status: published
publisher: American Mathematical Society
quality_controlled: '1'
scopus_import: '1'
status: public
title: Extension complexity of low-dimensional polytopes
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 375
year: '2022'
...
---
_id: '9585'
abstract:
- lang: eng
  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.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Matthew Alan
  full_name: Kwan, Matthew Alan
  id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3
  last_name: Kwan
  orcid: 0000-0002-4003-7567
- first_name: Benny
  full_name: Sudakov, Benny
  last_name: Sudakov
citation:
  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>
  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>
  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>.
  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.
  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>.
  short: M.A. Kwan, B. Sudakov, Transactions of the American Mathematical Society
    372 (2019) 5571–5594.
date_created: 2021-06-22T09:31:45Z
date_published: 2019-10-15T00:00:00Z
date_updated: 2023-02-23T14:01:50Z
day: '15'
doi: 10.1090/tran/7729
extern: '1'
external_id:
  arxiv:
  - '1712.05656'
intvolume: '       372'
issue: '8'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.1090/tran/7729
month: '10'
oa: 1
oa_version: Submitted Version
page: 5571-5594
publication: Transactions of the American Mathematical Society
publication_identifier:
  eissn:
  - 1088-6850
  issn:
  - 0002-9947
publication_status: published
publisher: American Mathematical Society
quality_controlled: '1'
scopus_import: '1'
status: public
title: Proof of a conjecture on induced subgraphs of Ramsey graphs
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 372
year: '2019'
...