2021/07/20 by Farzam Ebrahimnejad, James R. Lee, Ebrahimnejad, Farzam +1
Computer Science · Mathematics · #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Metric Geometry (math.MG) #Point processes and geometric inequalities #Stochastic processes and statistical mechanics #cs.DS #math.CO #math.MG
paper · pdf · doi:10.48550/arxiv.2107.09790
17 pages, 7 figures
arxiv created 2021/07/20 · openalex publication_date 2021/07/20 · arxiv updated 2021/07/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
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 Rs.