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.