Determining a Points Configuration from a Subset of the Pairwise Distances

Abstract

We study rigidity without assuming general position. Given $n$ distinct labelled points and a set $\mathcal{P}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{2}\right)$ of revealed pairs, we ask when the corresponding distances determine the configuration up to isometry. On the line, we prove an extremal result: if $|\mathcal{P}|=\hat{I}\text{c◯}(n^{3/2})$, then there is an induced globally rigid subgraph on $\hat{I}\text{c◯}(|\mathcal{P}|/n)$ vertices. In other words, any dense enough graph will contain a subset of labels whose locations can be determined from their distances up to isometry. To prove this, we establish a graph-theoretic result, which may be of independent interest: a dense graph in which every non-edge has few common neighbours contains a clique of size $\hat{I}\text{c◯}(|E|/n)$. We also study random revealed pairs. For every labelled configuration $V$ of distinct points in $\mathbb{R}$, if each pair is revealed independently with probability $p=C\ln n/n$, where $C>1$, then the revealed distances determine $V$ w.h.p. We prove a similar result for $d\ge 1$ under the mild non-degeneracy assumption that every subcollection of more than $\ddot{I}„n$ points of $V\subseteq {\mathbb{R}}^d$ affinely spans ${\mathbb{R}}^d$, for some fixed $0<\ddot{I}„<1$. In this case, every $C>1/(1-\ddot{I}„)$ suffices. The same ideas also settle the weak-threshold form of a conjecture of Girão et al. for a giant reconstructable component, and substantially improve in this direction the work of Barnes et al. establishing such a component for $p>n^{-2/(d+4)}$.