## Abstract

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 language | English |
---|---|

Pages (from-to) | 1458-1483 |

Number of pages | 26 |

Journal | Annals of Applied Probability |

Volume | 30 |

Issue number | 3 |

Early online date | 14 Sept 2019 |

DOIs | |

Publication status | Published - 30 Jun 2020 |

### Bibliographical note

Funding Information:Acknowledgements. We thank Nicolás García Trillos and Ery Arias Castro for answering some questions regarding their work on this subject. We also thank the anonymous referees for some helpful suggestions. The research leading to this paper was partially carried out during an extended visit of the second author to Utrecht University. He thanks the Department of Mathematics at Utrecht University for its hospitality. The first author was partially supported by NWO Grants 639.032.529 and 612.001.409. The second author was partially supported by a STAR visitor grant, by NWO visitor grant 040.11.532 and by the Department of Mathematics at Utrecht University.

Publisher Copyright:

© Institute of Mathematical Statistics, 2020.

## Keywords

- Cheeger constant
- Conductance
- Random geometric graph

## ASJC Scopus subject areas

- Statistics and Probability
- Statistics, Probability and Uncertainty