Optimal Cheeger cuts and bisections of random geometric graphs

Mathew Penrose, Tobias Müller

Research output: Contribution to journalArticlepeer-review

3 Citations (SciVal)
33 Downloads (Pure)


Let d ≥ 2. The Cheeger constant of a graph is the minimum surfaceto- 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ía Trillos et al. had shown this for d ≥ 3 but had required an extra condition on the distance parameter when d = 2.

Original languageEnglish
Pages (from-to)1458-1483
Number of pages26
JournalAnnals of Applied Probability
Issue number3
Early online date14 Sept 2019
Publication statusPublished - 30 Jun 2020


  • Cheeger constant
  • Conductance
  • Random geometric graph

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty


Dive into the research topics of 'Optimal Cheeger cuts and bisections of random geometric graphs'. Together they form a unique fingerprint.

Cite this