Universal geometric non-embedding of random regular graphs

Dylan J. Altschuler and Konstantin Tikhomirov · 2025

Read Universal geometric non-embedding of random regular graphs by Dylan J. Altschuler and Konstantin Tikhomirov (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-09142.txt.

Description

Dylan Altschuler and Konstantin Tikhomirov show that typical random regular graphs refuse to live as distance graphs in any low-dimensional normed space. A classic result blocks regular expanders from Euclidean spaces below a logarithmic dimension threshold. The obstruction there might have been a quirk of the Euclidean norm. This paper removes that hope.

For a uniform random regular graph with fixed degree at least three, no normed space below the threshold dimension admits it as a geometric graph, with high probability. The ban is universal across norms. The proof seeds a multiscale net argument and grows the obstruction scale by scale. Geometric realizability, the result says, is not a matter of choosing a friendlier geometry. Expander-like randomness itself forbids faithful distance representations in few dimensions.

Catalog record

CREATORDylan J. Altschuler and Konstantin Tikhomirov
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE42 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-09142

Browse the full library · About the Tower of Babel