Title: On 2-level polytopes arising in combinatorial settings,
Abstract: 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 study of
some 2-level polytopes arising in combinatorial settings. Our first
contribution is proving that v(P)*f(P) is upper bounded by d*2^(d+1), for a
large collection of families of such polytopes P. 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], and
experimental results from [Fiorini et al., ISCO 2016] showed it true up to
dimension 7. The key to most of our proofs is a deeper understanding of the
relations among those polytopes and their underlying combinatorial structures.
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 stable matching polytopes as affine projections of
certain order polytopes; and a linear-size description of the base polytope of
matroids that are 2-level in terms of cuts of an associated tree.