论文标题
从成对距离的子集确定线上的点配置
Determining a Points Configuration on the Line from a Subset of the Pairwise Distances
论文作者
论文摘要
我们研究了实际线路上的刚性类型问题，在非传播环境中的圆圈。具体而言，我们考虑唯一确定$ n $不同点的位置的问题$ v = {v_1，\ ldots，v_n} $给定一组相互距离$ \ MATHCAL {p} \ subSeteq {v \ subseteq {v \ select 2} $。我们建立了一个极端结果：如果$ | \ Mathcal {p} | =ω（n^{3/2}）$，然后是大子集$ v'\ subseteq v $的位置，其中大表示$ | v'| =ω（\ frac {| \ Mathcal {p} |} {n}）$，可以独特地确定为等级。作为证明的主要成分，这可能引起独立的兴趣，我们表明，密集的图$ g =（v，e）$，为此，每两个非附属顶点只有少数常见的邻居必须具有较大的集团。 此外，我们研究了从随机距离集$ \ mathcal {p} $重建$ v $的问题。我们确定，如果每对点之间的距离与概率$ p = \ frac {c \ ln（n）} {n} $独立知道，则对于某些通用常数$ c> 0 $，则可以从距离从距离重建$ v $，具有很高的可能性。我们提供了一种随机算法，并具有线性预期的运行时间，该算法将$ V $的正确嵌入到线上的正确概率。 由于我们在ARXIV上发布了本文的初步版本，因此随机环境中的结果有所改善。 Girão，Illingworth，Michel，Powierski和Scott证明了第一个时刻的打击时间，当时人们可以使用Erdös-RényiEvolution揭示$ \ Mathcal {p} $重建$ v $ V $，我们的最大结果是他们参数的核心。 Montgomery，Nenadov和Szabó解决了我们在先前版本中提出的猜想，并证明了从Erdös-rényiEvolution采样的w.h.p图表在$ \ Mathbb {r} $中在全球范围内变得僵化，目前的最小程度为$ 2 $ 2美元。
We investigate rigidity-type problems on the real line and the circle in the non-generic setting. Specifically, we consider the problem of uniquely determining the positions of $n$ distinct points $V = {v_1, \ldots, v_n}$ given a set of mutual distances $\mathcal{P} \subseteq {V \choose 2}$. We establish an extremal result: if $|\mathcal{P}| = Ω(n^{3/2})$, then the positions of a large subset $V' \subseteq V$, where large means $|V'| = Ω(\frac{|\mathcal{P}|}{n})$, can be uniquely determined up to isometry. As a main ingredient in the proof, which may be of independent interest, we show that dense graphs $G=(V,E)$ for which every two non-adjacent vertices have only a few common neighbours must have large cliques. Furthermore, we examine the problem of reconstructing $V$ from a random distance set $\mathcal{P}$. We establish that if the distance between each pair of points is known independently with probability $p = \frac{C \ln(n)}{n}$ for some universal constant $C > 0$, then $V$ can be reconstructed from the distances with high probability. We provide a randomized algorithm with linear expected running time that returns the correct embedding of $V$ to the line with high probability. Since we posted a preliminary version of the paper on arxiv, follow-up works have improved upon our results in the random setting. Girão, Illingworth, Michel, Powierski, and Scott proved a hitting time result for the first moment at which an time at which one can reconstruct $V$ when $\mathcal{P}$ is revealed using the Erdös--Rényi evolution, our extremal result lies in the heart of their argument. Montgomery, Nenadov and Szabó resolved a conjecture we posed in a previous version and proved that w.h.p a graph sampled from the Erdös--Rényi evolution becomes globally rigid in $\mathbb{R}$ at the moment it's minimum degree is $2$.
