Optimal Cheeger cuts and bisections of random geometric graphs

Tobias Müller, Mathew D. Penrose

Let $d\ge 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…