{"id":"arxiv/2604.09176","url":"https://arxiv.org/abs/2604.09176","tags":["math.CO"],"score":0,"title":"Sharp threshold for reconstructing points on the line","domain":"math.CO","source":"arxiv","authors":["Georgii Zakharov"],"reviews":0,"subject":"math.CO","summary":"For a set of $n$ points $V \\subseteq \\mathbb{R}$ let $G(V, p)$ be the random graph on $V$ where each possible edge is present independently with probability $p$. We call a subset $U \\subseteq V$ {\\emph {reconstructible}} if every injection $\\varphi:V\\to \\mathbb{R}$ that preserves the distances along the edges of $G(V, p)$ also preserves all pairwise distances in $U$. How large is the size $\\mathsf{R}$ of a largest reconstructible subset? Girão, Illingworth, Michel, Powierski and Scott conjectured that the answer is linear whp when $p = (1+\\varepsilon)/n$ for every $\\varepsilon > 0$. In this…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-10","reactions":{}}