Sharp-threshold conjecture for reconstructible subsets near the random-graph critical point
Let with , and let the known distances be distributed as in for a parameter . Call a subset reconstructible if every injection of into preserving the distances on the known edges preserves all pairwise distances within that subset. Sharp-threshold conjecture. There exists such that, for every , if , then with high probability there exists a reconstructible subset of size , while if , then with high probability every reconstructible subset has size at most . 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
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.