The sharp threshold conjecture for a linear-sized reconstructible set
The sharp threshold conjecture for a linear-sized reconstructible set
Let be a set of points on the real line. A graph of known pairwise distances 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 , write whp for “with high probability.”
Sharp threshold conjecture. The threshold for the existence of a reconstructible set of size linear in is sharp and occurs at
The preceding result establishes that is a weak threshold for a linear-sized reconstructible set, while the conjectured location agrees with the appearance of the giant component in . 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.