Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2602.23122 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914353941315584 |
|---|---|
| author | Portier, Julien |
| author_facet | Portier, Julien |
| contents | Let $V \subset \mathbb{R}$ be a finite set with $|V| = n $ and suppose we are given each pairwise distance independently with probability $p$. We show that if $p = (1+ε)/n$, for some fixed $ε>0$, then we can reconstruct a subset of size $Ω_ε(n)$, up to translation and reflection, with high probability. This confirms a conjecture posed by Girão, Illingworth, Michel, Powierski, and Scott.
We also study a deterministic variant proposed by Benjamini and Tzalik. We show that if we are given $m$ distinct pairwise distances of a point set $V \subset \mathbb{R}$ with $|V|=n$, then we can reconstruct a subset of size $Ω(m/ (n \log n)) $, up to translation and reflection. Moreover, we show that this is optimal, which also disproves a conjecture posed by Benjamini and Tzalik. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_23122 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Reconstructing a giant component of a point set in $\mathbb{R}$ Portier, Julien Combinatorics Let $V \subset \mathbb{R}$ be a finite set with $|V| = n $ and suppose we are given each pairwise distance independently with probability $p$. We show that if $p = (1+ε)/n$, for some fixed $ε>0$, then we can reconstruct a subset of size $Ω_ε(n)$, up to translation and reflection, with high probability. This confirms a conjecture posed by Girão, Illingworth, Michel, Powierski, and Scott. We also study a deterministic variant proposed by Benjamini and Tzalik. We show that if we are given $m$ distinct pairwise distances of a point set $V \subset \mathbb{R}$ with $|V|=n$, then we can reconstruct a subset of size $Ω(m/ (n \log n)) $, up to translation and reflection. Moreover, we show that this is optimal, which also disproves a conjecture posed by Benjamini and Tzalik. |
| title | Reconstructing a giant component of a point set in $\mathbb{R}$ |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2602.23122 |