← All problems

Sharp-threshold conjecture for reconstructible subsets near the random-graph critical point

17 years old · traced to

Let V⊆RV\subseteq\mathbb{R} with ∣V∣=n|V|=n, and let the known distances be distributed as in G(V,λ/n)G(V,\lambda/n) for a parameter λ>0\lambda>0. Call a subset reconstructible if every injection of VV into R\mathbb{R} preserving the distances on the known edges preserves all pairwise distances within that subset. Sharp-threshold conjecture. There exists C>0C>0 such that, for every ε>0\varepsilon>0, if λ=1+(C+ε)/ln⁡n\lambda=1+(C+\varepsilon)/\ln n, then with high probability there exists a reconstructible subset of size Ωε(n/ln⁡2n)\Omega_{\varepsilon}(n/\ln^2 n), while if λ=1+(C−ε)/ln⁡n\lambda=1+(C-\varepsilon)/\ln n, then with high probability every reconstructible subset has size at most o(n/ln⁡2n)o(n/\ln^2 n). This gives a quantitative formulation of the proposed phase transition in the critical window; neither side of the threshold is established in the source.

References

17 papers in this index state this conjecture (2009–2026). The statement above is taken from the most recent of them; the others are arXiv:2603.05467, arXiv:2602.09049, arXiv:2601.07771, arXiv:2510.07870, arXiv:2509.06403, arXiv:2502.14794, arXiv:2405.07253, arXiv:2206.14472, arXiv:2108.04299, arXiv:2011.08066, arXiv:1712.00992, arXiv:1703.10711, and 4 more.

Source: Georgii Zakharov, “Sharp threshold for reconstructing points on the line”, arXiv:2604.09176 (2026).

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.