The sharp threshold conjecture for a linear-sized reconstructible set

Let VV be a set of nn points on the real line. A graph of known pairwise distances (V,P)(V,\mathcal{P}) records which pairs of points have known distances; a set of vertices is reconstructible if its points can be determined from the known pairwise distances, up to the relevant ambiguities. For a random graph distributed as G(n,p)\mathcal{G}(n,p), write whp for “with high probability.”

Sharp threshold conjecture. The threshold for the existence of a reconstructible set of size linear in nn is sharp and occurs at

p=1n.p=\frac{1}{n}.

The preceding result establishes that 1/n1/n is a weak threshold for a linear-sized reconstructible set, while the conjectured location agrees with the appearance of the giant component in G(n,p)\mathcal{G}(n,p). The source presents this as a natural conjecture and gives no resolution.

Sources & referencesView supporting material

Primary source

António Girão, Freddie Illingworth, Lukas Michel, Emil Powierski and Alex Scott, “Reconstructing a point set from a random subset of its pairwise distances”, arXiv:2301.11019 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.