On vertices and facets of combinatorial 2-level polytopes

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.


Editor(s):
Cerulli, Raffaele
Mahjoub, A. Ridha
Fujishige, Satoru
Published in:
Combinatorial Optimization: 4th International Symposium, ISCO 2016 Vietri sul Mare, Italy, May 16–18, 2016 Revised Selected Papers, LNCS 9849, 177-188
Presented at:
ISCO 2016, Vietri sul mare, Italy, May 16-18, 2016
Year:
2016
Publisher:
Springer
ISBN:
978-3-319-45586-0
Keywords:
Laboratories:




 Record created 2016-11-03, last modified 2018-03-17

Publisher's version:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)