Universal geometric non-embedding of random regular graphs

2025/01/15 by Dylan J. Altschuler, Konstantin Tikhomirov, Altschuler, Dylan J. +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Limits and Structures in Graph Theory #Metric Geometry (math.MG) #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.2501.09142

openalex publication_date 2025/01/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let Δ≥ 3 be fixed, n ≥ n_Δ be a large integer. It is a classical result that Δ--regular expanders on n vertices are not embeddable as geometric (distance) graphs into Euclidean space of dimension less than c log n, for some universal constant c. We show that for typical Δ-regular graphs, this obstruction is universal with respect to the choice of norm. More precisely, for a uniform random Δ-regular graph G on n vertices, it holds with high probability: there is no normed space of dimension less than clog n which admits a geometric graph isomorphic to G. The proof is based on a seeded multiscale ε--net argument.

Cited by

• Metric dimension reduction modulus for superlogarithmic distortion

Related

• A universal threshold for geometric embeddings of trees
• On expansion of G_{n, d} with respect to G_{m, d}
• Local Improvement Gives Better Expanders
• Random Geometric Graphs and Isometries of Normed Spaces
• The model theory of geometric random graphs