Threshold (1+ε)/n for Ω(n) distance reconstruction

Status solved high confidence

The conjecture that $p=(1+\varepsilon)/n$ is the sharp threshold for the existence of a reconstructible set of size $\Omega(n)$ has been resolved by Zakharov (2026, arXiv:2604.09176), which proves that for every $\varepsilon>0$, with high probability there exists a reconstructible subset $U$ of the giant component $C$ of the 2-core satisfying $|U|=|V(C)|(1-o(1))$ when $p=(1+\varepsilon)/n$, establishing the conjectured threshold and in fact giving a stronger quantitative bound.

Cited literature (1)

• proof Sharp threshold for reconstructing points on the line (2026)
  Georgii Zakharov · arXiv preprint · arXiv:2604.09176

  Proves that for every $\varepsilon>0$ with $\varepsilon=\omega(1/\ln n)$, when $p=(1+\varepsilon)/n$, whp there exists a reconstructible subset of the giant 2-core component of size $(1-o(1))|V(C)|$, confirming the conjectured sharp threshold $p=(1+\varepsilon)/n$ for linear-proportion reconstruction.

Reviewer notes. The paper arXiv:2401.01882 (Barnes, Petr, Portier, Randall Shaw, Sergeev, 2024) addresses higher-dimensional reconstruction at a different threshold and is not directly related to this conjecture. The resolving paper arXiv:2604.09176 also requires $\varepsilon=\omega(1/\ln n)$, so there may remain a thin regime near $\varepsilon\to 0$ not fully covered.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).