Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. On vertices and facets of combinatorial 2-level polytopes
 
conference paper

On vertices and facets of combinatorial 2-level polytopes

Aprile, Manuel Francesco  
•
Cevallos Manzano, Alfonso Bolívar  
•
Faenza, Yuri  
Cerulli, Raffaele
•
Mahjoub, A. Ridha
Show more
2016
Combinatorial Optimization: 4th International Symposium, ISCO 2016 Vietri sul Mare, Italy, May 16–18, 2016 Revised Selected Papers
ISCO 2016

2-level polytopes naturally appear in several areas of mathematics, including combinatorial optimization, polyhedral combinatorics, communication complexity, and statistics. We investigate upper bounds on the product of the number of facets and the number of vertices, where d is the dimension of a 2-level polytope P. This question was first posed in [3], where experimental results showed an upper bound of d2^{d+1} up to d = 6, where d is the dimension of the polytope. We show that this bound holds for all known (to the best of our knowledge) 2-level polytopes coming from combinatorial settings, including stable set polytopes of perfect graphs and all 2-level base polytopes of matroids. For the latter family, we also give a simple description of the facet-defining inequalities. These results are achieved by an investigation of related combinatorial objects, that could be of independent interest.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

On vertices and facets of combinatorial 2-level polytopes.pdf

Type

Publisher's Version

Version

http://purl.org/coar/version/c_970fb48d4fbd8a85

Access type

openaccess

Size

479.56 KB

Format

Adobe PDF

Checksum (MD5)

8d209ab9a734d12f0056d8e98d58e058

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés