On vertices and facets of combinatorial 2-level polytopes

Manuel Aprile, Alfonso Cevallos, Yuri Faenza

Published 2017-02-10Version 1

2-level polytopes naturally appear in several areas of pure and applied mathematics, including combinatorial optimization, polyhedral combinatorics, communication complexity, and statistics. In this paper, we present a polyhedral study of 2-level polytopes arising in combinatorial settings. For all the known (to the best of our knowledge) such polytopes P, we show that v(P).f(P) is upper bounded by d2^(d+1). Here v(P) (resp. f(P)) is the number of vertices (resp. facets) of P, and d is its dimension. Whether this holds for all 2-level polytopes was asked in [Bohn et al., ESA 2015], where experimental results showed it true up to dimension 6. The key to most of our proofs is an understanding of the combinatorial structures underlying those polytopes. This leads to a number of results that we believe to be of independent interest: a trade-off formula for the number of cliques and stable sets in a graph; a description of the facets of the base polytope of the 2-sum of matroids; a linear-size description of the base polytope of matroids that are 2-level in terms of cuts of an associated tree. We also give a self-contained proof of the characterization of the last class, a result first obtained by Grande and Sanyal.