Sharp-threshold conjecture for reconstructible subsets near the random-graph critical point
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.
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
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.