{
  "id": "2207.03627",
  "version": "v1",
  "published": "2022-07-08T00:41:59.000Z",
  "updated": "2022-07-08T00:41:59.000Z",
  "title": "Expansion of random $0/1$ polytopes",
  "authors": [
    "Brett Leroux",
    "Luis Rademacher"
  ],
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "A conjecture of Mihail and Vazirani states that the edge expansion of the graph of every $0/1$ polytope is at least one. Any lower bound on the edge expansion gives an upper bound for the mixing time of a random walk on the graph of the polytope. Such random walks are important because they can be used to generate an element from a set of combinatorial objects uniformly at random. A weaker form of the conjecture of Mihail and Vazirani says that the edge expansion of the graph of a $0/1$ polytope in $\\mathbb{R}^d$ is greater than 1 over some polynomial function of $d$. This weaker version of the conjecture would suffice for all applications. Our main result is that the edge expansion of the graph of a $\\textit{random}$ $0/1$ polytope in $\\mathbb{R}^d$ is at least $\\frac{1}{12d}$ with high probability.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-07-08T00:41:59.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "52B12",
      "52B11",
      "52B05",
      "68W20",
      "60G50"
    ],
    "keywords": [
      "edge expansion",
      "random walk",
      "conjecture",
      "vazirani states",
      "lower bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}