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 fd-1(P) and the number of vertices f0(P), where d is the dimension of a 2-level polytope P. This question was first posed in [3], where experimental results showed f0(P)fd-1(P) ≤ d2d+1 up to d = 6. 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.
On vertices and facets of combinatorial 2-level polytopes
Aprile M.;Faenza Y.
2016
Abstract
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 fd-1(P) and the number of vertices f0(P), where d is the dimension of a 2-level polytope P. This question was first posed in [3], where experimental results showed f0(P)fd-1(P) ≤ d2d+1 up to d = 6. 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.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.