On The Number of Robust Geometric Graphs in a Euclidean Space
DOI:
https://doi.org/10.5195/pimr.2024.41Abstract
We say that a graph Γ=(V,E) with vertices in a k–dimensional Euclidean space is an ε–robust distance graph with threshold τ if any two vertices v,w in V are adjacent if and only if ‖v−w‖2≤(1+ε)−1τ and are not adjacent if and only if ‖v−w‖2>(1+ε)τ. We show that there are universal constants C′,c′,c>0 with the following property. For k≥C′dlogn, asymptotically almost every d–regular graph on n vertices is isomorphic to a c√d–robust distance graph in Rk , whereas for k≤c′dlognlogd , a.a.e d–regular graph on n vertices cannot be represented as an c√d–robust distance graph.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Lufei Yang, Colin Yip, Madison Zhao, Konstantin Tikhomirov

This work is licensed under a Creative Commons Attribution 4.0 International License.