Optimal Cheeger cuts and bisections of random geometric graphs

Tobias Müller, Mathew D. Penrose

OnderzoeksoutputAcademicpeer review

5 Citaten (Scopus)
71 Downloads (Pure)

Samenvatting

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, García Trillos et al. had shown this for
d

3
but had required an extra condition on the distance parameter when
d
=
2
.
Originele taal-2English
Pagina's (van-tot)1458–1483
TijdschriftThe Annals of Applied Probability
Volume30
Nummer van het tijdschrift3
DOI's
StatusPublished - 1-jun.-2020

Vingerafdruk

Duik in de onderzoeksthema's van 'Optimal Cheeger cuts and bisections of random geometric graphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit