OPTIMAL CHEEGER CUTS AND BISECTIONS OF RANDOM GEOMETRIC GRAPHS
成果类型：
Article
署名作者：
Mueller, Tobias; Penrose, Mathew D.
署名单位：
University of Groningen; University of Bath
刊物名称：
ANNALS OF APPLIED PROBABILITY
ISSN/ISSBN：
1050-5164
DOI：
10.1214/19-AAP1534
发表日期：
2020
页码：
1458-1483
关键词：
摘要：
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, Garcia Trillos et al. had shown this for d >= 3 but had required an extra condition on the distance parameter when d = 2.