{
  "id": "1702.03187",
  "version": "v1",
  "published": "2017-02-10T14:37:00.000Z",
  "updated": "2017-02-10T14:37:00.000Z",
  "title": "On vertices and facets of combinatorial 2-level polytopes",
  "authors": [
    "Manuel Aprile",
    "Alfonso Cevallos",
    "Yuri Faenza"
  ],
  "categories": [
    "math.CO",
    "cs.CG"
  ],
  "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 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-02-10T14:37:00.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "base polytope",
      "independent interest",
      "polyhedral combinatorics",
      "experimental results",
      "combinatorial structures"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}