Global rigidity of random graphs in $\mathbb{R}$

Abstract

We investigate the problem of reconstructing a set $P\subseteq \mathbb{R}$ of distinct points, where the only information available about $P$ consists of the distances between some of the pairs of points. More precisely, we examine which properties of the graph $G$ of known distances, defined on the vertex set $P$, ensure that $P$ can be uniquely reconstructed up to isometry. We prove that as soon as the random graph process has minimum degree 2, with high probability it can reconstruct all distances within any point set in $\mathbb{R}$. This resolves a conjecture of Benjamini and Tzalik. We also study the feasibility and limitations of reconstructing the distances within almost all points using much sparser random graphs. In doing so, we resolve a question posed by Girão, Illingworth, Michel, Powierski, and Scott.

9 pages. This version includes a new coauthor and an additional result, Theorem 1.5