# Optimal Cheeger cuts and bisections of random geometric graphs

Mathew Penrose, Tobias Müller

Research output: Working paper

### Abstract

Let $d \geq 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\'ia Trillos {\em et al.} had shown this for $d \geq 3$ but had required an extra condition on the distance parameter when $d=2$.
Original language English arXiv 33 1805.08669 Published - 22 May 2018

### Cite this

arXiv, 2018.

Research output: Working paper

@techreport{b2ea93bae8be48dfa239cb8c0f1a4551,
title = "Optimal Cheeger cuts and bisections of random geometric graphs",
abstract = "Let $d \geq 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\'ia Trillos {\em et al.} had shown this for $d \geq 3$ but had required an extra condition on the distance parameter when $d=2$.",
author = "Mathew Penrose and Tobias M{\"u}ller",
year = "2018",
month = "5",
day = "22",
language = "English",
volume = "1805.08669",
publisher = "arXiv",
type = "WorkingPaper",
institution = "arXiv",

}

TY - UNPB

T1 - Optimal Cheeger cuts and bisections of random geometric graphs

AU - Penrose, Mathew

AU - Müller, Tobias

PY - 2018/5/22

Y1 - 2018/5/22

N2 - Let $d \geq 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\'ia Trillos {\em et al.} had shown this for $d \geq 3$ but had required an extra condition on the distance parameter when $d=2$.

AB - Let $d \geq 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\'ia Trillos {\em et al.} had shown this for $d \geq 3$ but had required an extra condition on the distance parameter when $d=2$.

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

M3 - Working paper

VL - 1805.08669

BT - Optimal Cheeger cuts and bisections of random geometric graphs

PB - arXiv

ER -