Optimal Cheeger cuts and bisections of random geometric graphs

Mathew Penrose, Tobias Müller

Research output: Contribution to journalArticlepeer-review

5 Citations (SciVal)
68 Downloads (Pure)

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 languageEnglish
Pages (from-to)1458-1483
Number of pages26
JournalAnnals of Applied Probability
Volume30
Issue number3
Early online date14 Sept 2019
DOIs
Publication statusPublished - 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

Fingerprint

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

Cite this