Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.09176 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914463376998400 |
|---|---|
| author | Zakharov, Georgii |
| author_facet | Zakharov, Georgii |
| contents | 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 $φ: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 paper, we show that for every $\varepsilon>0$ whp there exists a reconstructible subset $U$ of the largest component $\mathcal{C}$ of the 2-core satisfying $|U| = |V(\mathcal{C})|(1-o(1))$, proving a stronger form of the conjecture. The bound is asymptotically best possible, since for $V \subseteq \mathbb{R}$ linearly independent over $\mathbb{Q}$ it is straightforward to verify that $\mathsf{R} \leq \max(2, |V(\mathcal{C})|)$. Furthermore, we extend these results to every $\varepsilon:= \varepsilon(n)$ satisfying $\varepsilon = ω(1/\ln n)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_09176 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Sharp threshold for reconstructing points on the line Zakharov, Georgii Combinatorics 05C80, 52C25 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 $φ: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 paper, we show that for every $\varepsilon>0$ whp there exists a reconstructible subset $U$ of the largest component $\mathcal{C}$ of the 2-core satisfying $|U| = |V(\mathcal{C})|(1-o(1))$, proving a stronger form of the conjecture. The bound is asymptotically best possible, since for $V \subseteq \mathbb{R}$ linearly independent over $\mathbb{Q}$ it is straightforward to verify that $\mathsf{R} \leq \max(2, |V(\mathcal{C})|)$. Furthermore, we extend these results to every $\varepsilon:= \varepsilon(n)$ satisfying $\varepsilon = ω(1/\ln n)$. |
| title | Sharp threshold for reconstructing points on the line |
| topic | Combinatorics 05C80, 52C25 |
| url | https://arxiv.org/abs/2604.09176 |