{
  "id": "math/0112146",
  "version": "v1",
  "published": "2001-12-14T08:20:45.000Z",
  "updated": "2001-12-14T08:20:45.000Z",
  "title": "On the Expansion of Graphs of 0/1-Polytopes",
  "authors": [
    "Volker Kaibel"
  ],
  "comment": "19 pages",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "The edge expansion of a graph is the minimum quotient of the number of edges in a cut and the size of the smaller one among the two node sets separated by the cut. Bounding the edge expansion from below is important for bounding the ``mixing time'' of a random walk on the graph from above. It has been conjectured by Mihail and Vazirani that the graph of every 0/1-polytope has edge expansion at least one. A proof of this (or even a weaker) conjecture would imply solutions of several long-standing open problems in the theory of randomized approximate counting. We present different techniques for bounding the edge expansion of a 0/1-polytope from below. By means of these tools we show that several classes of 0/1-polytopes indeed have graphs with edge expansion at least one. These classes include all 0/1-polytopes of dimension at most five, all simple 0/1-polytopes, all hypersimplices, all stable set polytopes, and all (perfect) matching polytopes.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2001-12-14T08:20:45.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "52B12",
      "52B11",
      "52B05",
      "68W20",
      "60G50"
    ],
    "keywords": [
      "edge expansion",
      "minimum quotient",
      "stable set polytopes",
      "node sets",
      "long-standing open problems"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 19,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2001math.....12146K"
    }
  }
}