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
| CREATOR | Dylan J. Altschuler and Konstantin Tikhomirov |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 42 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-09142