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

Let VRV\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+ε)/lnn\lambda=1+(C+\varepsilon)/\ln n, then with high probability there exists a reconstructible subset of size Ωε(n/ln2n)\Omega_{\varepsilon}(n/\ln^2 n), while if λ=1+(Cε)/lnn\lambda=1+(C-\varepsilon)/\ln n, then with high probability every reconstructible subset has size at most o(n/ln2n)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.

Sources & referencesView supporting material

Primary source

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

Additional 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.

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.