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