Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2401.10803 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912239397634048 |
|---|---|
| author | Montgomery, Richard Nenadov, Rajko Portier, Julien Szabó, Tibor |
| author_facet | Montgomery, Richard Nenadov, Rajko Portier, Julien Szabó, Tibor |
| contents | We investigate the problem of reconstructing a set $P\subseteq \mathbb{R}$ of distinct points, where the only information available about $P$ consists of the distances between some of the pairs of points. More precisely, we examine which properties of the graph $G$ of known distances, defined on the vertex set $P$, ensure that $P$ can be uniquely reconstructed up to isometry. We prove that as soon as the random graph process has minimum degree 2, with high probability it can reconstruct all distances within any point set in $\mathbb{R}$. This resolves a conjecture of Benjamini and Tzalik. We also study the feasibility and limitations of reconstructing the distances within almost all points using much sparser random graphs. In doing so, we resolve a question posed by Girão, Illingworth, Michel, Powierski, and Scott. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_10803 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Global rigidity of random graphs in $\mathbb{R}$ Montgomery, Richard Nenadov, Rajko Portier, Julien Szabó, Tibor Combinatorics We investigate the problem of reconstructing a set $P\subseteq \mathbb{R}$ of distinct points, where the only information available about $P$ consists of the distances between some of the pairs of points. More precisely, we examine which properties of the graph $G$ of known distances, defined on the vertex set $P$, ensure that $P$ can be uniquely reconstructed up to isometry. We prove that as soon as the random graph process has minimum degree 2, with high probability it can reconstruct all distances within any point set in $\mathbb{R}$. This resolves a conjecture of Benjamini and Tzalik. We also study the feasibility and limitations of reconstructing the distances within almost all points using much sparser random graphs. In doing so, we resolve a question posed by Girão, Illingworth, Michel, Powierski, and Scott. |
| title | Global rigidity of random graphs in $\mathbb{R}$ |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2401.10803 |