### Abstract

Let d ≥ 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, Garca Trillos*et al*had shown this for*d*≥ 3 but had required an extra condition on the distance parameter when*d*= 2.Original language | English |
---|---|

Pages (from-to) | 1458-1483 |

Number of pages | 33 |

Journal | Annals of Applied Probability |

Volume | 30 |

Issue number | 3 |

Early online date | 14 Sep 2019 |

DOIs | |

Publication status | Published - 30 Jun 2020 |

## Cite this

Penrose, M., & Müller, T. (2020). Optimal Cheeger cuts and bisections of random geometric graphs.

*Annals of Applied Probability*,*30*(3), 1458-1483. https://doi.org/10.1214/19-AAP1534