Universal geometric non-embedding of random regular graphs

Let $\mathrm{\Delta }\ge 3$ be fixed, $n\ge n_{\mathrm{\Delta }}$ be a large integer. It is a classical result that $\mathrm{\Delta }$–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 $\mathrm{\Delta }$-regular graphs, this obstruction is universal with respect to the choice of norm. More precisely, for a uniform random $\mathrm{\Delta }$-regular graph $G$ on $n$ vertices, it holds with high probability: there is no normed space of dimension less than $c\log n$ which admits a geometric graph isomorphic to $G$. The proof is based on a seeded multiscale $\epsilon$–net argument.