Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
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.
Mika Tapani Göös, Siddhartha Jain
Matthias Schymura, Georg Peter Loho
Yuri Faenza, Manuel Francesco Aprile