{
  "id": "1805.08669",
  "version": "v1",
  "published": "2018-05-22T15:41:55.000Z",
  "updated": "2018-05-22T15:41:55.000Z",
  "title": "Optimal Cheeger cuts and bisections of random geometric graphs",
  "authors": [
    "Tobias Müller",
    "Mathew D. Penrose"
  ],
  "comment": "33 pages",
  "categories": [
    "math.PR"
  ],
  "abstract": "Let $d \\geq 2$. The Cheeger constant of a graph is the minimum surface-to-volume ratio of all subsets of the vertex set with relative volume at most 1/2. There are several ways to define surface and volume here: the simplest method is to count boundary edges (for the surface) and vertices (for the volume). We show that for a geometric (possibly weighted) graph on $n$ random points in a $d$-dimensional domain with Lipschitz boundary and with distance parameter decaying more slowly (as a function of $n$) than the connectivity threshold, the Cheeger constant (under several possible definitions of surface and volume), also known as conductance, suitably rescaled, converges for large $n$ to an analogous Cheeger-type constant of the domain. Previously, Garc\\'ia Trillos {\\em et al.} had shown this for $d \\geq 3$ but had required an extra condition on the distance parameter when $d=2$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-05-22T15:41:55.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "60D05",
      "62H30"
    ],
    "keywords": [
      "random geometric graphs",
      "optimal cheeger cuts",
      "cheeger constant",
      "bisections",
      "distance parameter"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 33,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}