Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2208.13855 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917549672759296 |
|---|---|
| author | Benjamini, Itai Tzalik, Elad |
| author_facet | Benjamini, Itai Tzalik, Elad |
| contents | We study rigidity without assuming general position. Given $n$ distinct labelled points and a set $\mathcal{P}\subseteq \binom{[n]}{2}$ of revealed pairs, we ask when the corresponding distances determine the configuration up to isometry. On the line, we prove an extremal result: if $|\mathcal{P}|=Ω(n^{3/2})$, then there is an induced globally rigid subgraph on $Ω(|\mathcal{P}|/n)$ vertices. In other words, any dense enough graph will contain a subset of labels whose locations can be determined from their distances up to isometry. To prove this, we establish a graph-theoretic result, which may be of independent interest: a dense graph in which every non-edge has few common neighbours contains a clique of size $Ω(|E|/n)$.
We also study random revealed pairs. For every labelled configuration $V$ of distinct points in $\mathbb{R}$, if each pair is revealed independently with probability $p=C\ln n/n$, where $C>1$, then the revealed distances determine $V$ w.h.p. We prove a similar result for $d\ge1$ under the mild non-degeneracy assumption that every subcollection of more than $τn$ points of $V\subseteq\mathbb R^d$ affinely spans $\mathbb R^d$, for some fixed $0<τ<1$. In this case, every $C>1/(1-τ)$ suffices. The same ideas also settle the weak-threshold form of a conjecture of Girão et al. for a giant reconstructable component, and substantially improve in this direction the work of Barnes et al. establishing such a component for $p>n^{-2/(d+4)}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_13855 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Determining a Points Configuration from a Subset of the Pairwise Distances Benjamini, Itai Tzalik, Elad Metric Geometry Combinatorics Probability We study rigidity without assuming general position. Given $n$ distinct labelled points and a set $\mathcal{P}\subseteq \binom{[n]}{2}$ of revealed pairs, we ask when the corresponding distances determine the configuration up to isometry. On the line, we prove an extremal result: if $|\mathcal{P}|=Ω(n^{3/2})$, then there is an induced globally rigid subgraph on $Ω(|\mathcal{P}|/n)$ vertices. In other words, any dense enough graph will contain a subset of labels whose locations can be determined from their distances up to isometry. To prove this, we establish a graph-theoretic result, which may be of independent interest: a dense graph in which every non-edge has few common neighbours contains a clique of size $Ω(|E|/n)$. We also study random revealed pairs. For every labelled configuration $V$ of distinct points in $\mathbb{R}$, if each pair is revealed independently with probability $p=C\ln n/n$, where $C>1$, then the revealed distances determine $V$ w.h.p. We prove a similar result for $d\ge1$ under the mild non-degeneracy assumption that every subcollection of more than $τn$ points of $V\subseteq\mathbb R^d$ affinely spans $\mathbb R^d$, for some fixed $0<τ<1$. In this case, every $C>1/(1-τ)$ suffices. The same ideas also settle the weak-threshold form of a conjecture of Girão et al. for a giant reconstructable component, and substantially improve in this direction the work of Barnes et al. establishing such a component for $p>n^{-2/(d+4)}$. |
| title | Determining a Points Configuration from a Subset of the Pairwise Distances |
| topic | Metric Geometry Combinatorics Probability |
| url | https://arxiv.org/abs/2208.13855 |