Optimal Cheeger cuts and bisections of random geometric graphs

Mathew Penrose, Tobias Müller

Research output: Contribution to journalArticle

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 languageEnglish
Number of pages33
JournalAnnals of Applied Probability
Publication statusAccepted/In press - 14 Sep 2019

Cite this

Optimal Cheeger cuts and bisections of random geometric graphs. / Penrose, Mathew; Müller, Tobias.

In: Annals of Applied Probability, 14.09.2019.

Research output: Contribution to journalArticle

@article{b2ea93bae8be48dfa239cb8c0f1a4551,
title = "Optimal Cheeger cuts and bisections of random geometric graphs",
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.",
author = "Mathew Penrose and Tobias M{\"u}ller",
year = "2019",
month = "9",
day = "14",
language = "English",
journal = "Annals of Applied Probability",
issn = "1050-5164",
publisher = "Institute of Mathematical Statistics",

}

TY - JOUR

T1 - Optimal Cheeger cuts and bisections of random geometric graphs

AU - Penrose, Mathew

AU - Müller, Tobias

PY - 2019/9/14

Y1 - 2019/9/14

N2 - 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.

AB - 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.

UR - https://arxiv.org/abs/1805.08669

M3 - Article

JO - Annals of Applied Probability

JF - Annals of Applied Probability

SN - 1050-5164

ER -