Sharp threshold for reconstructing points on the line

Abstract

For a set of $n$ points $V\subseteq \mathbb{R}$ let $G(V,p)$ be the random graph on $V$ where each possible edge is present independently with probability $p$. We call a subset $U\subseteq V$ {\emph {reconstructible}} if every injection $\phi :V\to \mathbb{R}$ that preserves the distances along the edges of $G(V,p)$ also preserves all pairwise distances in $U$. How large is the size $\mathsf{R}$ of a largest reconstructible subset? Girão, Illingworth, Michel, Powierski and Scott conjectured that the answer is linear whp when $p=(1+\epsilon )/n$ for every $\epsilon >0$. In this paper, we show that for every $\epsilon >0$ whp there exists a reconstructible subset $U$ of the largest component $\mathcal{C}$ of the 2-core satisfying $|U|=|V(\mathcal{C})|(1-o(1))$, proving a stronger form of the conjecture. The bound is asymptotically best possible, since for $V\subseteq \mathbb{R}$ linearly independent over $\mathbb{Q}$ it is straightforward to verify that $\mathsf{R}\le \max (2,|V(\mathcal{C})|)$. Furthermore, we extend these results to every $\epsilon :=\epsilon (n)$ satisfying $\epsilon =\omega (1/\ln n)$.

47 pages, 8 figures