Non-existence of annular separators in geometric graphs
share
Benjamini and Papasoglou (2011) showed that planar graphs with uniform polynomial volume growth admit 1-dimensional annular separators: The vertices at graph distance R from any vertex can be separated from those at distance 2R by removing at most O(R) vertices. They asked whether geometric d-dimensional graphs with uniform polynomial volume growth similarly admit (d-1)-dimensional annular separators when d > 2. We show that this fails in a strong sense: For any d ≥ 3 and every s ≥ 1, there is a collection of interior-disjoint spheres in ℝ^d whose tangency graph G has uniform polynomial growth, but such that all annular separators in G have cardinality at least R^s.
READ FULL TEXT