On The Number of Robust Geometric Graphs in a Euclidean Space

Abstract

We say that a graph \(\Gamma = (V , E)\) with vertices in a \(k\)–dimensional Euclidean space is an \(\varepsilon\)–robust distance graph with threshold \(\tau\) if any two vertices \(v, w\) in \(V\) are adjacent if and only if \(\Vert v − w \Vert_2 \leq (1 + \varepsilon)^{−1}\tau\) and are not adjacent if and only if \(\Vert v − w \Vert_2 > (1 + \varepsilon)\tau\). We show that there are universal constants \(C′, c′, c > 0\) with the following property. For \(k \geq C′d \log{n}\), asymptotically almost every \(d\)–regular graph on \(n\) vertices is isomorphic to a \(\frac{c}{\sqrt{d}}\)–robust distance graph in \(\mathbb{R}^k\) , whereas for \(k \leq \frac{c′ d \log{n}}{\log{d}}\) , a.a.e \(d\)–regular graph on \(n\) vertices cannot be represented as an \(\frac{c}{\sqrt{d}}\)–robust distance graph.