222832
20180624125342.0
978-3-319-45586-0
10.1007/978-3-319-45587-7_16
doi
CONF
On vertices and facets of combinatorial 2-level polytopes
2016
Springer
2016
Conference Papers
Lecture Notes in Computer Science
9849
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.
2-level polytopes
matroid polytopes
polyhedral combinatorics.
Aprile, Manuel Francesco
249959
248589
Cevallos Manzano, Alfonso Bolívar
222377
246643
Faenza, Yuri
229283
246581
ISCO 2016
Vietri sul mare, Italy
May 16-18, 2016
Cerulli, Raffaele
ed.
Mahjoub, A. Ridha
ed.
Fujishige, Satoru
ed.
177-188
Combinatorial Optimization: 4th International Symposium, ISCO 2016 Vietri sul Mare, Italy, May 16–18, 2016 Revised Selected Papers
LNCS 9849
Publisher's version
491066
Publisher's version
http://infoscience.epfl.ch/record/222832/files/On%20vertices%20and%20facets%20of%20combinatorial%202-level%20polytopes.pdf
oai:infoscience.tind.io:222832
SB
conf
DISOPT
252111
U11879
249959
EPFL-CONF-222832
EPFL
PUBLISHED
REVIEWED
CONF