# Determining a Points Configuration on the Line from a Subset of the Pairwise
Distances

Itai Benjamini, Elad Tzalik

###### Abstract

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}|=\Omega(n^{3/2})$, then the
positions of a large subset $V^{\prime}\subseteq V$, where large means
$|V^{\prime}|=\Omega(\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$.

##  1 Introduction

Let $V$ be a set of $n$ distinct points in a metric space. Given a subset of
pairwise distances $\mathcal{P}$ of $V$, we inquire whether all other
distances in $V$ can be uniquely determined. In $\mathbb{R}^{d}$ with $d>1$,
it is easy to construct examples where all distances are known except one
distance, yet this distance cannot be deduced from the others. In order to say
something meaningful on rigidity a popular line of work is to assume general
position, e.g. that the points are in generic position, meaning that all the
coordinates of elements of $V$ are algebraically independent over
$\mathbb{Q}$. In that case, it is known to be a property of the graph
$(V,\mathcal{P})$ that does not depend on the distances of elements in
$\mathcal{P}$.

In $\mathbb{R}$, it is well known that if the points are in generic position,
then all distances are determined by $\mathcal{P}$ if and only if
$(V,\mathcal{P})$ is $2$-connected, as shown in [7]. However, when the points
are not in generic position, it is easy to build an example with $4$ points
and $4$ given distances in which $2$-connectivity is no longer sufficient.

We study rigidity _without_ assuming general position but only assuming the
weaker assumption that $V$ are different points, and show that when the points
are in $\mathbb{R}$ the set $\mathcal{P}$ of pairwise distances known does
carry meaningful information.

A graph $G=(V,\mathcal{P})$ is said to be _globally rigid_ in $\mathbb{R}$ if,
for any _injective_ map $f\colon V\rightarrow\mathbb{R}$, the distance between
$(f(i),f(j))$ for ${i,j}\in\mathcal{P}$ determines uniquely the distances of
all ${V\choose 2}$ pairs. A characterization of globally rigid graphs in
$\mathbb{R}$ in the injective setting was obtained by [4] (Theorem 2.4). They
established that certain edge colorings of the graph serve as witnesses for
the graph being _not_ globally rigid in $\mathbb{R}$. Furthermore, they showed
that recognizing whether a graph is globally rigid in $\mathbb{R}$ is an NP-
complete problem.

To conclude the preceding discussion, we emphasize that although there exists
a significant amount of research on globally rigid graphs, it focuses to the
generic setting, where the embedding function $f$ satisfies a strong condition
of being generic. In contrast, the results presented in this paper apply under
a much weaker assumption, namely that $f$ is injective.

We consider $n$ points in either $\mathbb{R}$ or $S^{1}$, which may not
necessarily be in generic position. We first examine an arbitrary distance
sets $\mathcal{P}$. We prove that every dense enough graph $(V,\mathcal{P})$
contains a dense globally rigid subgraph.

###### Theorem 1

Let $V$ be a subset of either $\mathbb{R}$ or $S^{1}$ of size $n$ and let
$\mathcal{P}$ be the set of given distances. If $|\mathcal{P}|>40n\sqrt{n}$,
then there exists $V^{\prime}\subseteq V$ s.t. all distances between elements
of $V^{\prime}$ can be deduced from $\mathcal{P}$ and
$|V^{\prime}|=\Omega(\frac{|\mathcal{P}|}{n})$.

We prove the following stronger claim. Consider $V=\\{v_{1},...,v_{n}\\}$ a
set of objects whose explicit representation is unknown. Assume we have
knowledge of the result of a certain function $f(v_{i},v_{j})$ for some pairs
of elements in $V$ and the objective is to reconstruct some subset of the
elements of $V$ from these measurements. That is, we would like to determine
the $f$ valuations of all the pairs in some subset $V^{\prime}$ of $V$, with
$V^{\prime}$ large.

We say that a function $f$ is $k$-locally determined if $f(v_{i},v_{j})$ can
be determined from the values of $f(v_{i},x),f(v_{j},x)$ for $k$ different
elements $x$ in $V$. Let $\mathcal{P}$ be the set of pairs for which the $f$
valuations are known, then:

###### Theorem 2

Let $V$ be a set of $n$ elements, and let $f$ be a $k$-locally determined
function with a measurement set $\mathcal{P}\subseteq{V\choose 2}$. If
$|\mathcal{P}|\geq 8n\sqrt{kn}$, there exists a subset $V^{\prime}\subseteq V$
of size $\Omega(\frac{|\mathcal{P}|}{n})$ for which all the measurments on
${V^{\prime}\choose 2}$ are determined from $\mathcal{P}$.

To prove the bound given in Theorem 1, we demonstrate that distances in
$\mathbb{R}$ and $S^{1}$ are $3$ and $5$ locally-determined, respectively, and
then apply Theorem 2.

We also study what can be deduced from a random $\mathcal{P}$, and show that
the situation differs significantly. In this case, we show that if the
distance between each pair of elements in ${V\choose 2}$ is known with
probability $p=\frac{C\ln(n)}{n}$, independently, and for a large enough
constant $C$, then there is a linear expected running time algorithm that
returns a correct embedding to the line with high probability.

###### Theorem 3

Let $V=\\{v_{1},\dots,v_{n}\\}$ be $n$ distinct points in $\mathbb{R}$. There
exists a constant $C$ such that when each pairwise distance is known with
probability $p=\frac{C\ln(n)}{n}$, independently, then all other distances can
be deduced from $\mathcal{P}$ with high probability.

The main ingredient in the proof of the claim above is proving a sharp
threshold for having a monotone path from $1$ to $n$ in an Erdős–Rényi random
graph with vertex set $[n]$. Specifically, we prove that there is a sharp
threshold for the existence of such a path at $p=\frac{\ln(n)}{n}$.

#### Remarks on advancements after first arxiv version

Since the first publication Girão, Illingworth, Michel, Powierski, and Scott
[5] 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. They proved that one can reconstruct $V$ at the moment
where the minimum degree of the graph is $2$, In particular they proved
Theorem 3 holds with any constant $C>1$. Their proofs relies heavily on
Theorem 1.

The work of Barnes, Petr, Portier, Randall Shaw and Sergeev [2] made progress
on a question of Girão, Illingworth, Michel, Powierski, and Scott [5] and gave
the first non trivial bounds on the required density of a random set
$\mathcal{P}$ of distances, such that given $n$ points in $\mathbb{R}^{d}$,
one can reconstruct all distances between $(1-o(1))n$ of the points from the
distances in $\mathcal{P}$.

In the work of Montgomery, Nenadov and Szabó [9] they resolved a conjecture
from previous version, 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$. Their result also improve upon Theorem 3 and does not use
Theorem 1.

##  2 Reconstructing a subset of $\mathbb{R}$ or $S^{1}$

We start by showing that the distance functions in $\mathbb{R}$ and $S^{1}$
are $3,5$ locally determined respectively.

###### Claim 4

Given $v_{i},v_{j}\in\mathbb{R}$, and $3$ common neighbours in
$G=(V,\mathcal{P})$ one can determine the distance $d(v_{i},v_{j})$ from their
distances to the common neighbours.

###### Proof.

Consider the functions $f(z)=|d(v_{i},z)-d(z,v_{j})|$. As $f$ attains maximum
outside the segment $\overline{v_{i}v_{j}}$, and attains any other value at
most twice inside $\overline{v_{i}v_{j}}$. Let $z_{1},z_{2},z_{3}$ be three
common neighbours of $v_{i},v_{j}$. If all $f(z_{i})$ are equal then
$f(z_{i})=d(v_{i},v_{j})$. Otherwise, pick the element with minimal $f$ value
among $z_{1},z_{2},z_{3}$, w.l.o.g it is $z_{1}$, this implies $z_{1}$ lies
inside $\overline{v_{i}v_{j}}$ and hence
$d(v_{i},v_{j})=(v_{i},z_{1})+d(z_{1},v_{j})$ can be determined. ∎

In $S^{1}$ five common neighbors are enough.

###### Claim 5

Given $v_{i},v_{j}\in S^{1}$, and $5$ common neighbours in $G=(V,\mathcal{P})$
one can determine the distance $d(v_{i},v_{j})$ from their distances to the
common neighbours.

###### Proof.

Let $\\{z_{k}\\}_{k=1}^{5}$ be common neighbors of $v_{i},v_{j}$. Consider the
3 regions in Figure 1, and again consider the function
$f(z)=|d(v_{i},z)-d(z,v_{j})|$. If $f(z_{k})$ has the same value for all
$k=1,...,5$ then necessarily this is the distance from $x_{i}$ to $x_{j}$ and
all points $z_{1},...,z_{5}$ are in region $B$.

Otherwise w.l.o.g we may assume that $z_{1}$ attains the minimum over all
$|d(v_{i},z_{k})-d(z_{k},v_{j})|$. This means that $z_{1}$ is _not_ in the
region $B$. Hence if $d(x_{i},z_{1})+d(z_{1},x_{j})\geq\frac{1}{2}$ then
$z_{1}$ is at region $C$ and
$d(v_{i},v_{j})=1-(d(v_{i},z_{1})+d(z_{1},v_{j}))$, and if
$d(v_{i},z_{1})+d(v_{1},x_{j})\leq\frac{1}{2}$ then $z_{1}$ is at region $A$
and $d(v_{i},v_{j})=d(v_{i},z_{1})+d(v_{1},x_{j})$. ∎

By the previous claims, it suffices to prove Theorem 6 to get Theorem 1.

Figure 1: Three regions on the circle

###  2.1  Proof of Theorem 2

Let $(V,\mathcal{P})$ be the graph of given measurements. Define $G=(V,E)$ the
graph of determined $f$ valuations, which contains as edges all possible pairs
that can be determined from $\mathcal{P}$ by the locality of $f$. Let
$\Gamma(v)$ denote the set of neighbors of $v$ in $G$. Since $E$ contains all
possible pairs that can be determined it means that
$|\Gamma(v_{i})\cap\Gamma(v_{j})|\geq k\implies\\{v_{i},v_{j}\\}\in E$. Denote
by $\alpha(G)$ the size of a maximum independent set of $G$ and by $\omega(G)$
the size of the maximum clique in $G$.

Therefore the following implies Theorem 2:

###### Theorem 6

Let $G=(V,E)$ be a graph on $n$ vertices, such that $\\{i,j\\}\not\in
E\implies|\Gamma(i)\cap\Gamma(j)|\leq k$.
If $|E|\geq 8n\sqrt{kn}$ then $\omega(G)\geq\frac{1}{4}\frac{|E|}{n}$.

We remind the following standard lemma:

###### Lemma 7

Let $G$ be a graph of average degree $d=\frac{2|E|}{n}$. There exists an
induced subgraph $G^{\prime}$ with _minimal_ degree $\delta(G^{\prime})$
satisfying $\delta(G^{\prime})\geq\frac{d}{2}$

###### Proof.

Iteratively delete from $G$ vertices of degree smaller than $\frac{d}{2}$.
Each deletion only increases the average degree, so this process must
terminate and the final set of vertices $V^{\prime}$ induce the desired
subgraph. ∎

Consequently, from now we assume that $G$ has minimal degree
$\delta(G)\geq\frac{|\mathcal{P}|}{n}$ with $V=V^{\prime}$. To ease the
notation we refer to $\delta(G)$ as $\delta$.

To bound the size of the maximal independent set of $G$. We need the following
result due to Corrádi, whose proof appears in [8] (Lemma 2.1):

###### Lemma 8

Let $S_{1},..,S_{N}$ be subsets of a set $X$, each of size $\geq r$ with
$|S_{i}\cap S_{j}|\leq k$ then:

$|X|\geq\frac{r^{2}N}{r+(N-1)k}$

We now bound the size of the maximal independent set in $G$ by applying
Corrádi’s Lemma:

###### Claim 9

Let $G$ be a graph on $n$ vertices such that all non-neighbours $i,j$ satisfy
$|\Gamma(s_{i})\cap\Gamma(s_{j})|\leq k$. If the minimal degree of $G$
satisfies $\delta\geq\sqrt{2nk}$ then the size of a maximum independent set in
$G$ satisfies $\alpha(G)\leq 2\frac{n}{\delta}$

###### Proof.

Denote the elements of the maximum independent set by $s_{1},...,s_{\alpha}$.
By Lemma 8 applied to $S_{i}=\Gamma(s_{i})$:

$\displaystyle n\geq\frac{\delta^{2}\alpha(G)}{\delta+k(\alpha(G)-1)}$

Rearranging this inequality yields:

$\displaystyle\alpha(G)\leq\frac{n(\delta-k)}{\delta^{2}-kn}\leq\frac{n\delta}{1/2\cdot\delta^{2}}\leq
2\frac{n}{\delta}$

∎

###### Proof of Theorem 6.

We assume that the graph $G$ has minimal degree $\delta\geq\frac{|E|}{2n}$.
Let $I=\\{s_{1},\ldots,s_{\alpha}\\}$ be any independent set of maximum size.
Since by assumption $|E|\geq 8n\sqrt{kn}$ one can apply 9 to obtain that
$\alpha\leq 2\frac{n}{\delta}$. Define $B_{i}$ to be the set of elements that
has only $s_{i}$ as a neighbour in $s_{1},\ldots,s_{\alpha}$. Formally
$B_{i}=\\{u\in G\mid\Gamma(u)\cap\\{s_{1},...,s_{\alpha}\\}=s_{i}\\}$, i.e. it
is the set of elements in $\Gamma(s_{i})$ for which $s_{i}$ is their _unique_
neighbor from the set $s_{1},...,s_{\alpha}$. The following observation is the
heart of the argument:

###### Observation 10

Each $B_{i}$ form a clique in $G$.

The observation follows by noticing that if $x,y\in B_{i}$ are not adjacent
then $I\cup{x,y}\setminus s_{i}$ is an independent set. (see Figure 2).

Figure 2: Left: non-adjacent vertices have at most $k$ common neighbors.
Right: $B_{i}$ is a clique since replacing $i$ with $x,y$ non-adjacent
increases the size of a _maximum_ independent set.

Thus it follows that:

$\displaystyle\omega(G)\geq\frac{|\bigcup_{i=1}^{\alpha(G)}B_{i}|}{\alpha(G)}$
(1)

To estimate $|\bigcup_{i=1}^{\alpha(G)}B_{i}|$, first estimate
$|\bigcup_{i=1}^{\alpha(G)}\Gamma(s_{i})|$ by using Bonferroni’s inequality
and get:

$\displaystyle\bigg{|}\bigcup_{i=1}^{\alpha(G)}\Gamma(s_{i})\bigg{|}\geq\sum_{i=1}^{\alpha(G)}|\Gamma(s_{i})|-\sum_{i<j}|\Gamma(s_{i})\cap\Gamma(s_{j})|\geq\delta\alpha(G)-k{\alpha(G)\choose
2}$

Observe that the set $\bigcup_{i}B_{i}$ consists of exactly the elements in
$\bigcup_{i}\Gamma(s_{i})$ that do not appear in any
$\Gamma(s_{i})\cap\Gamma(s_{j})$ for all $i<j$, therefore:

$\displaystyle\bigg{|}\bigcup_{i=1}^{\alpha(G)}B_{i}\bigg{|}\geq\bigg{|}\bigcup_{i=1}^{\alpha(G)}\Gamma(s_{i})\bigg{|}-\sum_{i<j}|\Gamma(s_{i})\cap\Gamma(s_{j})|\geq\delta\alpha(G)-k{\alpha(G)\choose
2}-k{\alpha(G)\choose 2}$

Plugging this into Equation 1 and using 9 we get since $\delta\geq
4\sqrt{kn}$:

$\displaystyle\omega(G)\geq\delta-2k\alpha(G)\geq\delta-4k\frac{n}{\delta}\geq\frac{\delta}{2}\geq\frac{|E|}{4n}$

∎

Notice that the clique size achieved by Theorem 6 is asymptotically tight by
considering disjoint union of cliques of size roughly
$\Theta\left(\frac{|\mathcal{P}|}{n}\right)$. We note that the requirement
$|E|=\Omega\left(\sqrt{k}\cdot n\sqrt{n}\right)$ cannot be improved as well.

###### Claim 11

For every $k$, there are graphs $G$ satisfying the assumptions of Theorem 6,
with $|E|=\Theta\left(\sqrt{k}\cdot n\sqrt{n}\right)$ _and_ $\omega(G)=O(k)$.

###### Proof.

Let $G$ be a $C_{4}$-free graph with $|E(G)|=\Theta\left(n\sqrt{n}\right)$
edges, e.g. one may take the well-known ”lines vs planes” graph of the
incidences of lines and planes of $\mathbb{F}_{p}^{3}$ for a prime
$p\approx\sqrt{n}$. Denote by $V$ it’s vertex set, and let $n$ denote the size
of $V$. Observe that by being $C_{4}$-free $|\Gamma(v)\cap\Gamma(u)|\leq 1$
for any $v,u\in V$.

If we consider the graph $G^{\prime}$, obtained by replacing each vertex of
$V$ by a $k$-clique and each edge of $G$ by all possible edges between the new
cliques, then we obtain $G^{\prime}=(V^{\prime},E^{\prime})$ with
$|E(G^{\prime})|=\Omega\left(k^{2}|E(G)|\right)$ and $|V(G^{\prime})|=nk$,
moreover every two vertices in this graph has $\leq 2k$ common neighbors,
hence this graph satisfies the conditions of this claim as:

$|E(G^{\prime})|=\Omega(k^{2}n\sqrt{n})=\Omega(\sqrt{k}nk\sqrt{nk})=\Omega(\sqrt{k}|V(G^{\prime})|^{3/2})$

And $G^{\prime}$ has maximum clique of size $O(k)$ as needed. ∎

#### Reconstructing $3$ points on the 3-Regular tree requires $\Omega(n^{2})$
distances

It is natural to ask whether we can find analogs of Theorem 1 for subsets $S$
of metric spaces that are not $\mathbb{R}$ or $S^{1}$. We now consider the
3-regular tree $\mathbb{T}_{3}$ with the graph metric. We give an example of a
set $\mathcal{P}$ of size $\Omega(n^{2})$ for which we cannot fully
reconstruct a subset $S^{\prime}$ of size 3.

Consider the infinite binary tree, and associate each vertex of distance $k$
from some root $r$ by a length $k$ string over $\\{0,1\\}$. Consider the two
subsets of vertices of level $3n$, $S_{1}=\\{x\in\\{0,1\\}^{3n}\mid\text{ $x$
starts in $2n$ zeros}\\}$ and $S_{2}=\\{y\in\\{0,1\\}^{3n}\mid\text{ $y$ ends
in $2n$ zeros}\\}$. Notice that every two vertices of $S_{1}$ are at distance
at most $2n$, and every two vertices of $S_{2}$ are at distance at least $4n$.

For the $3$-regular tree, notice that for an edge $e$ the graph
$\mathbb{T}_{3}\setminus{e}$ is isomorphic to two copies of the infinite
binary tree. Define the set $R_{i}$ to be taking two copies of $S_{i}$ in each
infinite binary tree in $\mathbb{T}_{3}\setminus{e}$. If the set of distances
known, $\mathcal{P}$, is the set of all distances between vertices in the
different binary trees, then all distances in $\mathcal{P}$ is $6n$ and we
cannot distinguish $R_{1},R_{2}$ which have all other distances different, see
Figure 3. We also note this construction is tight since we constructed $2t$
points and $t^{2}$ known distances for which no $3$ points can be
reconstructed and by Mantel’s theorem adding one more pair to $\mathcal{P}$
yield a triangle in the distance graph.

Figure 3: Distances of vertices on different sides of $e$ give no information

#### Sparse globally rigid graphs in $\mathbb{R}$

4 has also the following application to injective global rigidity. A graph
$G=(V,E)$ is globally rigid in $\mathbb{R}$ if given an injective map
$\varphi:V\rightarrow\mathbb{R}$ all the distances of $e\in E(G)$ determine
all other distances uniquely (or equivalently, determine $\varphi$ up to
isometry). The proof of Theorem 6 gives that dense enough graphs contain large
globally rigid subgraphs. We note that 4 implies that there are infinitely
many globally rigid graphs with average degree at most $\frac{10}{3}$.

To see this, first notice that if $G$ is globally rigid in $\mathbb{R}$ then
adding a new vertex $v$ along with two edges to vertices of $G$ yields a new
graph that is also rigid. Given a graph $G=(V,E)$, define $T(G)$ to be a graph
with $V(T(G))=V\cup\left(E\times\\{i\\}\right)_{i=1}^{3}$ and
$E(T(G))=\\{\\{v,(e,i)\\}|v\in e\\}$, i.e. each edge is replace by 3 paths of
length two. Note that for every $\\{u,v\\}\in E(G)$,
$|\Gamma_{T(G)}(u)\cap\Gamma_{T(G)}(v)|=3$ thus by 4 all the distances of
vertices that correspond to the original edges of $G$ can be deduced from
$T(G)$. This means that $T(G)$ is rigid since all distances of $G$ can be
recovered from it, and the vertices of $V(T(G))\setminus{V(G)}$ all contain
two edges that connect to $G$. Note that if $\frac{|E|}{|V|}=\alpha$ then
$\frac{|E(T(G))|}{|V(T(G))|}=\frac{6\alpha}{1+3\alpha}$. Hence one can
construct an infinite family of graphs by $G_{1}=K_{3}$ a clique of size 3 and
take $G_{i}=T(G_{i-1})$. This infinite family has average degree
$<\frac{10}{3}$ since the sequence $a_{n}=\frac{|E(G_{n})|}{|V(G_{n})|}$ is
the sequence $a_{1}=1$, $a_{n+1}=\frac{6a_{n}}{1+3a_{n}}$ which converges to
$\frac{5}{3}$.

We note that the average degree of a globally rigid graph must be
substantially larger than what’s possible in the generic setting:

###### Proposition 12

Any globally rigid graph with at least $4$ vertices has average degree of at
least $\frac{12}{5}$.

###### Proof.

Let $G=(V,E)$ be a connected graph and let $V_{2}$ be the set of vertices of
degree $2$. Observe that if $G$ is globally rigid in $\mathbb{R}$ then $V_{2}$
must be an independent set. Indeed, for $x,y\in V_{2}$ assuming $x\sim y$ they
must lie on a path $(w,x,y,z)$ for $w\neq z$ since $G$ is connected and
$|V|\geq 4$. Let $\varphi:V\setminus\\{x,y\\}\rightarrow\mathbb{R}$ be an
injective map and consider:

$\varphi^{(c)}(a)=\left\\{\begin{array}[]{lr}\varphi(a),&\text{if }a\in
V\setminus\\{x,y\\}\\\ \varphi(w)+c,&\text{if }a=x\\\ \varphi(z)+c,&\text{ if
}a=z\end{array}\right\\}$

Notice that $\varphi^{(c)}$ and $\varphi^{(-c)}$ induce the same distances on
$e\in E$. As $c\in\mathbb{R}$ is arbitrary, then for some $c$ both
$\varphi^{(c)}$ and $\varphi^{(-c)}$ are injective and therefore $G$ is not
globally rigid.

Therefore $V_{2}$ is an independent set. Furthermore, it is clear that a
globally rigid graph must have minimum degree $>1$. Now consider the size of
$V_{2}$. If $|V_{2}|\geq\frac{3}{5}n$ then $|E|\geq 2|V_{2}|\geq\frac{6}{5}n$
and therefore $\frac{2|E|}{n}\geq\frac{12}{5}$.

If $|V_{2}|\leq\frac{3}{5}n$ then $\sum_{v\in V}deg(v)=\sum_{v\in
V_{2}}deg(v)+\sum_{v\in V\setminus V_{2}}deg(v)\geq
2|V_{2}|+3\left(n-|V_{2}|\right)\geq\frac{12}{5}n$ as needed. ∎

##  3 Reconstruction from Random $\mathcal{P}$

We now consider the case of a fixed set of points $V$ and a set of pairs
$\mathcal{P}$ sampled randomly, i.e. for each pair $\\{i,j\\}$ we know the
distance between point $i$ and point $j$ with probability $p$. We show that
for $p=\frac{C\ln(n)}{n}$ with $C$ being some universal constant it is
possible to reconstruct $V\subset\mathbb{R}$ w.h.p. We also show that at this
$p$, there is a randomized algorithm with expected running time linear in
$|\mathcal{P}|$ that returns the correct location of the points of $V$ up to
isometry w.h.p.

Before giving the full proof we sketch the strategy of the proof. Let
$\mathcal{P}$ be the random pairs samples, and $(V,\mathcal{P})$ is a $G(n,p)$
Erdős–Rényi random graph.

At the probability $p$ specified above we do not expect to vertices to have
common neighbors as this event occurs at $p\approx\frac{1}{\sqrt{n}}$. Since
the $G(n,p)$ graph at our range of $p$ looks locally like a tree and the local
structure is not rigid. Denote by $W(x,y)$ the set of all walks between $x,y$
in the graph $(V,\mathcal{P})$. We can define an estimate of the distance
between two nodes $x,y$ to be $Est(x,y):=min_{\gamma\in
W(x,y)}\sum_{i}d(v_{i},v_{i+1})$ where $\gamma=(v_{0},...,v_{k})$ is a walk
from $v_{0}=x$ to $v_{k}=y$, i.e. it is the distance in the graph metric
between $x,y$ in the graph $(V,\mathcal{P})$. It is clear that $Est(x,y)\geq
d(x,y)$. We will show that for $p=\frac{C\ln(n)}{n}$ far enough points $x,y$
(with $\Omega(n)$ points between them in the order induced by $\mathbb{R}$)
have $Est(x,y)=d(x,y)$ w.h.p.

The estimate $Est(x,y)$, even though correctly estimates far enough points, is
usually incorrect for close points, see Figure 4. To bypass this, we observe
that if $Est(x,y)$ is incorrect, then with many $z$, the three numbers
$Est(x,y),Est(x,z),Est(y,z)$ do not satisfy the triangle equality (w.h.p). We
also show the other direction, that is: if $Est(x,y)$ is correct, then with
many $z$, the terms $Est(x,y),Est(x,z),Est(y,z)$ satisfy the triangle
inequality. Combining these we get that we can find (w.h.p) the correct
$Est(x,y)$ efficiently, by checking triangle equalities.

Figure 4: Close points with $Est\approx 2Diam(S)$

Therefore, let $V=\\{v_{1},...,v_{n}\\}$ be $n$ points in $\mathbb{R}$ and
assume $v_{1}<v_{2}<...<v_{n}$ and let $G\sim G(n,p)$ be an Erdős–Rényi random
graph on vertex set $[n]$ where we associate the vertex $i$ with $v_{i}$, then
by the preceding discussion we’d like to understand when is
$Est(v_{i},v_{j})=d(v_{i},v_{j})$ which is exactly when there is a monotone
path from $i$ to $j$ in $G$111where by monotone we mean the sequence of vertex
indices along the path is monotone. We show that there is a sharp threshold at
$\frac{\ln(n)}{n}$ for the existence of a monotone path from $1$ to $n$ in a
random graph, that is:

###### Theorem 13

Let $G\sim G(n,p)$ be a random graph with vertex set $\\{1,...,n\\}$, then for
any $\varepsilon>0$:

  * •

(Subcritical) If $p=(1-\varepsilon)\frac{\ln(n)}{n}$ then w.h.p there is no
monotone path from $1$ to $n$.

  * •

(Supercritical) If $p=(1+\varepsilon)\frac{\ln(n)}{n}$ then w.h.p there is a
monotone path from $1$ to $n$.

###### Remark 14

In fact, we show in the supercritical regime that for each $\varepsilon$ the
corresponding events happen with probability $1-n^{f(\varepsilon)}$ where
$f(\varepsilon)$ is some constant depending on $\varepsilon$ and
$\lim_{\varepsilon\to\infty}f(\varepsilon)=\infty$.

By the remark above we have:

###### Corollary 15

There exist a universal constant $C$ such that a $G\sim G(n,p)$ random graph,
with vertex set $[n]$ and $p=\frac{C\ln(n)}{n}$ there is a monotone path
between all vertices $i,j\in[n]$ with $|i-j|\geq\frac{n}{8}$.

###### Proof.

Pick $\varepsilon>0$ such that $f(x)\geq 3$ for $x\geq\varepsilon$ and $f$ as
in Remark 14. Take $C=\frac{8}{\varepsilon}$, by a union bound one gets that
the probability some $i,j$, $|i-j|\geq\frac{n}{8}$ do not have a monotone path
is at most $n^{2}\cdot\frac{1}{n^{3}}=O(\frac{1}{n})$. ∎

Before we prove Theorem 13 we show it implies that we can reconstruct all
distances w.h.p.

The following lemma states that if one can reconstruct the $d(u,v)$ from
$d(\mathcal{P})$ for many pairs $(u,v)$ then one can reconstruct $d(u,v)$ for
_all_ pairs $(u,v)$. Let $d:{[n]\choose 2}\to\mathbb{R}_{>0}$ be the distances
of $V$, and let $d^{\prime}:{[n]\choose 2}\to\mathbb{R}_{>0}$ be a corrupted
distance function, whereby corrupted we mean that $d,d^{\prime}$ agree for
many pairs (to be defined precisely in the following lemma) then we claim that
if they are sufficiently close then $d^{\prime}$ uniquely defines $d$.

###### Lemma 16

Let $d:{[n]\choose 2}\to\mathbb{R}_{>0}$ be the distances between elements of
$V$ and $d^{\prime}$ another function with the same domain, range. Assume for
$u\in V:$ we have $\mid\\{v\in V\mid d(u,v)\neq d^{\prime}(u,v)\\}\mid\leq cn$
then:

  1. 1.

If $c<\frac{1}{4}$ then it is possible to uniquely reconstruct $d$ from
$d^{\prime}$.

  2. 2.

If $c>\frac{1}{4}$ then it may not be possible to uniquely reconstruct $d$
from $d^{\prime}$.

###### Proof.

For the first part, we can find all distances that are not corrupted by
observing that: $d^{\prime}(i,j)$ satisfies triangle equality with more than
$\frac{n}{2}$ other points if and only if $d^{\prime}(i,j)=d(i,j)$.

It is clear that for any $i,j$ the number of $k$ such that
$d^{\prime}(i,k)=d(i,k)$, $d^{\prime}(j,k)=d(j,k)$ is at least
$n-2cn-2=(1-2c)n-2$ since this is the total number of vertices minus corrupted
neighbors of $i$ or $j$. Therefore if $d^{\prime}(i,j)=d(i,j)$ it will satisfy
triangle equality with at least $(1-2c)n-2>\frac{n}{2}$ vertices.

Assume that $d^{\prime}(i,j)\neq d(i,j)$, we know by the argument above that
there is a set $S$ consisting of $(1-2c)n-2$ points for which their distance
to $i$ and $j$ is correct. For any point $k\in S$ that is contained in
$\overline{ij}$ for which $i,j,k$ satisfy triangle inequality we must have
that $d^{\prime}(i,j)$ is _not_ the largest edge in the triangle $\\{i,j,k\\}$
as this implies $d^{\prime}(i,j)=d(i,j)$ since $k\in S$. Therefore
$d^{\prime}(i,j)$ satisfies with $k\in S\cap\overline{ij}$:

$d^{\prime}(i,j)=max(d^{\prime}(i,k),d^{\prime}(j,k))-min(d^{\prime}(i,k),d^{\prime}(j,k))=max(d(i,k),d(j,k))-min(d(i,k),d(j,k))$

Where the right inequality follows by assuming $k\in S$. The RHS above doesn’t
take any value except the correct one more than twice by 4 therefore there are
at most two points in $S\cap\overline{ij}$ that satisfy triangle inequality
with $i,j$. A similar argument for points outside the segment between $i,j$
implies that at most two points of $S$ that lie outside the segment
$\overline{ij}$ satisfy triangle equality with $i,j$ therefore if
$d^{\prime}(i,j)\neq d(i,j)$then we have that $d^{\prime}(i,j)$ satisfies
triangle equality with at most $(2cn+2)+2+2=2cn+6<\frac{n}{2}$ points for
large enough $n$ while in the case $d^{\prime}(i,j)=d(i,j)$ we have that
$d^{\prime}(i,j)$ satisfies triangle equality with at least $\frac{n}{2}$
points by the assumption on $c$, hence one may observe $d^{\prime}$ and
distinguish the $d^{\prime}$ values corresponding to $d$, and those which does
not. This proves that the graph $(V,E^{\prime})$ with $E^{\prime}=\\{e\mid
d^{\prime}(e)=d(e)$ satisfies that all pairs of vertices share at least
$\frac{n}{2}>2$ neighbors we get by 4 that $d^{\prime}$ uniquely determines
$d$.

For the second part, take any $n=4k$ points labeled by $[n]$ and let $s$ be
their pairwise distances. Notice that if we partition the $n$ vertices to two
sets of size $2k$ we can find a $k$-regular subgraph of $K_{2k,2k}$ (since
$K_{2k,2k}$ is a union of $2k$ perfect matchings), denote the edges of this
subgraph by $E^{\prime}$. For the $n$ points in the line, if we shift the
points associated with $1,...,2k$ (while the other vertices stay in place)
then the distances that change are only those that correspond to edges in the
cut $\\{1,...,2k\\}\cup\\{2k+1,...,4k\\}$. If the edges of $E^{\prime}$ are
corrupted according to the shifted configuration to produce a corrupted set of
distances $d^{\prime}(i,j)$ then we cannot distinguish between the original
set and the shifted set after the corruption. ∎

###### Proof of Theorem 3.

By Corollary 15 w.h.p each pair of nodes that have at least $\frac{1}{8}n$
points between them there is a monotone path with edges in $\mathcal{P}$.

Therefore for all $i$: $\Big{\lvert}\left\\{j\mid Est(i,j)\neq
d(i,j)\right\\}\Big{\rvert}\leq 2\delta n<\frac{1}{4}n$ and thus by Lemma 16
one can correct $Est(x,y)$ to $d(x,y)$ and reconstruct the distances of all
the pairs of vertices w.h.p. ∎

We note that from an algorithmic standpoint Lemma 16 is inefficient since one
needs to run over all pairs to find which $Est$ are corrupted and which are
not. We now explain how to obtain a simple linear time algorithm, i.e.
$O(n^{2}p)$ expected running time that finds an embedding of $V$ to the line
w.h.p for $p$ in the range above.

###  3.1 Linear Time Algorithm to Find an Embedding

We note that it is possible to obtain a linear time algorithm that returns the
correct embedding w.h.p for a random $\mathcal{P}$ when $p=\frac{Cln(n)}{n}$
for large enough $C$. Specifically, sample two vertices $u,v$ and compute
shortest paths (value of $Est$) from them to all other vertices. Define:

$\displaystyle Int(u,v)=\\{x\mid$ $\displaystyle
Est(u,v),Est(u,x),Est(x,v)\text{ satisfy triangle equality},$ $\displaystyle
Est(u,v)=\max(Est(u,v),Est(u,x),Est(x,v)\\}$

Conditioning on the event that every two points $u,v$ with $\frac{1}{8}n$
between them are connected by a monotone path we have that
$|Int(u,v)|\geq\frac{n}{2}$ happens only for points for which
$Est(u,v)=d(u,v)$ and in this case all the points of $Int(u,v)$ are indeed
interior points of the segment $u,v$ (this follows since $Est$ is always at
least $d$). Even though $Int(u,v)$ consists of point in the segment between
$u,v$ it would be easier to work with points that are contagious. This can be
done by removing from $Int(u,v)$ the $\frac{1}{8}n$ points closest to $u$ and
removing the $\frac{1}{8}n$ points closest to $v$, denote this smaller set by
$Int^{\prime}(u,v)$, which is a set of contiguous points by assuming the event
of Corollary 15 holds. To construct the embedding, we first embed $u$ at $0$
and all vertices of $Int^{\prime}(u,v)$ are embedded by $x\rightarrow
Est(u,x)$. Using $Int^{\prime}(u,v)$ we can embedd all other points as
follows. Let $x,y$ be the middle two elements of $Int^{\prime}(u,v)$ and
denote the one of them which is closer to $u$ by $x_{u}$ and the other by
$x_{v}$. All points in $V\setminus Int^{\prime}(u,v)$ have between them and
each of $x_{u}$, $x_{v}$ at least $\frac{1}{8}n$ points (since
$Int^{\prime}(u,v)$ is a contagious set, of at least $\frac{n}{4}$ elements
with $x_{u},x_{v}$ being the middle elements). Therefore it is possible to
embed correctly $V\setminus(Int^{\prime}(u,v)\cup u)$ by computing shortest
path from $x_{u},x_{v}$ to all other points since the $Est$ is correct for
pairs in $\\{x_{u},x_{v}\\}\times V\setminus(Int^{\prime}(u,v)\cup u)$. We
describe below the algorithm more formally which returns an embedding
$Emb:V\rightarrow\mathbb{R}$.

Algorithm 1 Reconstruction($\mathcal{P}$)

1:for $i=1...\ln(n)$ do

2: Sample $u,v$ from $V$ uniformly.

3: Compute $Est$ on $\\{u,v\\}\times V$.

4: Compute $Int(u,v)$.

5: if $|Int(u,v)|\geq\frac{n}{2}$ then

6: Compute $Int^{\prime}(u,v)$.

7: for $w\in Int^{\prime}(u,v)$ do

8: $Emb(w)=Est(u,w)$

9: $x_{u},x_{v}\leftarrow$ middle vertices of $Int^{\prime}(u,v)$.

10: for $w\not\in Int^{\prime}(u,v)$ do

11: if $Est(x_{u},w)>Est(x_{v},w)$ then

12: $Emb(w)=Emb(x_{u})+Est(x_{u},w)$

13: if $Est(x_{u},w)<Est(x_{v},w)$ then

14: $Emb(w)=Emb(x_{u})-Est(x_{u},w)$ return

15: Return $Emb$

16:Return FALSE

#### Correctness (w.h.p) of Algorithm 1

The algorithm may be incorrect if the event of Corollary 15 does not hold,
though this is $o(1)$ in our range of $p$. Assuming the event of Corollary 15
we get that $Est$ is correct for all $u,v$ with $\frac{1}{8}n$ points between
them. We note that if the sample used by the algorithm is of two vertices with
$\frac{6}{8}n$ points between them then necessarily Line 5 of Algorithm 1 will
be executed and will produce an isometric embedding. Hence, the only event
remaining for which the algorithm is incorrect is the case where all the
samples didn’t satisfy Line 5 which is $o(1)$ since each sample has constant
probability to satisfy Line 5 and $\ln(n)$ samples are used.

#### Running time of Algorithm 1

Computing $Est$ between the samples and $V$ can be done in time
$O(|V|\ln(|V|)+|E|)=O(n^{2}p)$ by applying Dijkstra’s algorithm from $u,v$.
Since each sample has constant probability to invoke Line 5 of Algorithm 1 the
expected number of executions of the loop is constant. Therefore, the expected
running time is $O(n^{2}p)$ (which is linear in the size of the random graph).

###  3.2 Proof of Theorem 13

Before we analyze the threshold for monotone path at $p=\frac{\ln(n)}{n}$ we
sketch the main ideas of the proof. The case of $p$ below the threshold follow
from a standard first moment method. For $p$ above the threshold the analysis
is more involved. Set $p=\frac{c\ln(n)}{n}$, and let $V_{1}$ be the set of
vertices in $1,..,\frac{n}{2}$ that connects to $1$ by a monotone path and
define $V_{2}$ similarly for vertices in $\frac{n}{2}+1,...,n$ that connect to
$n$. We note that each monotone path from $1$ to $n$ passes once from $V_{1}$
to $V_{2}$. Therefore if any element of the set $V_{1}\times V_{2}$ is in our
random graph we will find a monotone $1$ to $n$ path. We show that with high
probability $|V_{1}|\cdot|V_{2}|=\Omega(n)$ in the super critical regime and
therefore we will be done as w.h.p an edge in $V_{1}\times V_{2}$ will be in
the random graph in our range of $p$.

To estimate the growth of $V_{1}$ divide the $n$ vertices to contiguous
intervals of size $\frac{n}{\ln(n)}$. Consider the first interval $I_{1}$
_before_ giving the vertices labels (meaning do not reveal yet the order of
$I_{1}$ on $\mathbb{R}$). The random graph induced on $I_{1}$ is distributed
as $G(\frac{n}{\ln(n)},\frac{c\ln(n)}{n})$, and it is well known that the
neighbourhood of a vertex in $G(\frac{n}{\ln(n)},\frac{c\ln(n)}{n})$ converges
Benjamini-Schramm (see [3]) to a Galton-Watson process with off-spring
distribution $Poisson(c)$, this in particular means that we expect the vertex
$1$ to have $c^{i}$ neighbours of distance $i$ in the interval $I_{1}$. Recall
that we do not care just about connectivity to vertices but we want to be
connected _by a monotone path_.

To understand the number of vertices in $I_{1}$ that $v$ connects to via a
monotone path it will be useful to think first of the neighbourhood structure
being picked and only then revealing for each vertex a random “label” from
$[n]$ not yet used (again, by label we mean it’s index in $\mathbb{R}$ with
respect to the order induced from $\mathbb{R}$). When giving those vertices a
random label we get that vertices with distance $i$ from $1$ are connected to
$1$ by a monotone path w.p. $\frac{1}{i!}$. Therefore, we expect that $1$
connects by a monotone path to $1+c+\frac{c^{2}}{2}+...=e^{c}$ vertices _from
the first interval_.

In general we expect the number of vertices that connect to $1$ by a monotone
path to grow by $e^{c}$ with each new interval since each vertex that connects
to $1$ by a monotone path connects by a monotone path to $e^{c}$ vertices in
the next interval therefore
$|V_{1}|\approx\left(e^{c}\right)^{\frac{\ln(n)}{2}}=n^{\frac{c}{2}}$ and
$|V_{1}|\cdot|V_{2}|\approx n^{c}$. Therefore if $c>1$ then w.h.p an edge
between $V_{1}$ to $V_{2}$ will be found.

###### Lemma 17

Let $T$ be a tree with $n$ vertices rooted at $v$, and denote by $r_{i}$ the
number of vertices of distance $i$ from $v$. Let $\pi$ be a uniformly random
bijection $\pi:V(T)\rightarrow\left[n\right]$ that satisfies $\pi(v)=1$.
Denote by $M_{\pi}$ the set of all vertices $u$ for which the $\pi$ values on
the path from $v$ to $u$ form an increasing sequence. Then
$\mathbb{E}[|M_{\pi}|]=\sum\frac{r_{i}}{i!}$

###### Proof.

Let $u$ be a vertex of distance $k$ and let $I_{u}$ be an indicator to the
event that the path from $v$ to $u$ is increasing. Fixing the $k+1$ labels of
the path there are $k!$ ways to label the path (since $\pi(v)$ is fixed to be
$1$) and exactly one of them is increasing, thus
$\mathbb{E}[I_{k}]=\mathbb{P}[I_{k}=1]=\frac{1}{k!}$ and the proof follows by
linearity of expectation. ∎

###### Corollary 18

Let $T$ be a Branching Process with a root $v$, offspring distribution
$\mathcal{D}$ with mean $\mu$, and let the process be stopped at time $M$. If
the vertices of each tree in the distribution are randomly labeled with $\pi$
such that $\pi(v)=1$ then
$\mathbb{E}[|M_{\pi}|]=\sum_{i=0}^{M}\frac{\mu^{i}}{i!}$

###### Proof.

Let $r_{i}$ be the size of the $i^{th}$ generation, then
$\mathbb{E}[r_{i}]=\mu^{i}$. The proof follows from Lemma 17 and the law of
total expectation. ∎

Finally, we remind the following inequality by Bernstein which may be found in
[10]:

###### Theorem 19

Let $X_{1},...X_{n}$ be i.i.d R.Vs with $0\leq X_{i}\leq K$ a.s. ,
$\mathbb{E}[X_{i}]=\mu$ then:

$\displaystyle\mathbb{P}[|\sum_{i=1}^{n}X_{i}-\mu n|\geq t]\leq
2exp\left(-\frac{t^{2}/2}{nK^{2}+K\frac{t}{3}}\right)$

###### Proof of Theorem 13.

In the subcritical regime a simple computation yields that the expected number
of monotone paths from $1$ to $n$ is $\sum_{i}{n-2\choose
i}p^{i+1}=p\cdot\left(1+p\right)^{n-2}\leq pe^{pn}$ and this is $o(1)$ in the
subcritical regime.

For the range above the threshold, let $G$ be a random graph on vertices
$1,..,n$ at $p=\frac{c\ln(n)}{n}$ for $c>1$, denote
$I_{j}=\\{(j-1)\frac{n}{ln(n)}+1,...,j\frac{n}{ln(n)}\\}$ and let $S_{i}$ be
the number of vertices in $\cup_{j=1}^{i}I_{j}$ that are connected to $1$ by a
monotone path and define a R.V. $X_{i}=|S_{i}|$. By the discussion above, it
is enough to show that the probability $X_{\frac{\ln(n)}{2}}<n^{1/2+\delta}$
is polynomially small in $n$222We need polynomially small probability for
Corollary 15. Since $X_{i}$ is increasing it’s equivalent to show that with
high enough probability we have for some $1\leq i\leq\frac{\ln(n)}{2}$ for
which $X_{i}\geq n^{1/2+\delta}$.

The proof proceeds in two stages. In the first stage we show that $X$ gets to
a polynomial size after logarithmically many steps, meaning
$X_{\beta\cdot\ln(n)}\geq n^{\alpha}$ for some $\alpha,\beta$ small enough.
For the second stage we show that conditioning on the event
$X_{\beta\cdot\ln(n)}\geq n^{\alpha}$ the increase from $X_{i}$ to $X_{i+1}$
is roughly by a factor $e^{c}$, thus by picking small enough $\beta$ we’ll get
that $X_{\ln(n)/2}$ is of size $n^{1/2+\delta}$.

For the first stage we note that the distribution of the neighbours of a
vertex $v$ from $X_{i}$ in $I_{i+1}$ follow a distribution that converges a
$Poisson(c)$ distribution, see e.g. Chapter 10 of [1]. Since $Poisson(c)$ has
expectation $c$ we can find $c>c^{\prime}>1$ such that for large enough $n$
the expected number of neighbours of $v$ in $I_{i+1}$ is at least
$c^{\prime}$. We can also truncate the distribution, meaning that there is $T$
such that if $v$ has more then $T$ neighbours we take only $T$ of them (and do
not use the other for constructing monotone paths). Also, for any
$c^{\prime}>c^{*}>1$ there is an $M$ such that
$\sum_{i=0}^{M}\frac{(c^{*})^{i}}{i!}>e$. To ease the notation we denote by
$c$ this $c^{*}$ and $T,M$ as above and we use this truncated distribution on
the neighbours. Hence from now on we assume each element from $S_{i}$ has at
most $T$ neighbours, and consider only monotone paths from it for $I_{j}$ for
$j>i$, analyzed as follows.

We first claim that if $X_{i}\leq n^{\frac{2}{3}}$ then for large enough $n$
with probability $\geq\frac{1}{2}$ we have
$X_{i+1}\geq(\frac{3}{4}+\frac{c}{4})X_{i}$. Fix $v\in I_{i+1}$ and $u\in
S_{i}$. By considering the event that $v$ adjacent to $u$, by linearity of
expectation we have:

$\displaystyle\mathbb{E}[X_{i+1}|X_{i}]=X_{i}+\frac{n}{\ln(n)}\mathbb{P}[v\in
I_{i+1}\text{ connects to some }u\in S_{i}]$ (2)

By the probabilistic Bonferroni’s inequality:

$\displaystyle\mathbb{P}[v\in I_{i+1}\text{ connects to some }u\in S_{i}]$
$\displaystyle\geq\frac{c\ln(n)}{n}X_{i}-{X_{i}\choose
2}\left(\frac{c\ln(n)}{n}\right)^{2}$ (3)
$\displaystyle\geq\frac{c\ln(n)}{n}X_{i}\left(1-\frac{c\ln(n)\cdot
X_{i}}{n}\right)$ (4)

If $X_{i}\leq n^{\frac{2}{3}}$ and $n$ is large enough, plugging Equation 3
into Equation 2 we get:

$\displaystyle\mathbb{E}[X_{i+1}|X_{i}]\geq(1+c-o(1))X_{i}$

Therefore by Markov’s inequality this means that since $c>1$:

$\displaystyle\mathbb{P}[X_{i+1}\geq\frac{1}{2}(1+c-o(1))X_{i}]\geq\frac{1}{2}$
(5)

And since $c>1$ this implies for large enough $n$:

$\displaystyle\mathbb{P}[X_{i+1}>\left(\frac{3}{4}+\frac{c}{4}\right)X_{i}]\geq\frac{1}{2}$
(6)

To show this implies that for suitable $\alpha,\beta$ one has:
$X_{\beta\cdot\ln(n)}\geq n^{\alpha}$, define:

$Y_{i}=\left\\{\begin{array}[]{lr}n^{\alpha},&\text{if }i=1\\\
\left(\frac{3}{4}+\frac{c}{4}\right)^{-1}Y_{i-1},&\text{if
}X_{i}>\left(\frac{3}{4}+\frac{c}{4}\right)X_{i-1}\\\ Y_{i-1},&\text{
otherwise}\end{array}\right\\}$

Notice that $\mathbb{P}[X_{i}\leq n^{\alpha}]\leq\mathbb{P}[Y_{i}\geq 1]$
since each multiplicative decrease of $Y$ is complemented by a multiplicative
increase in $X$ by at least the same constant. Also, note that
$\mathbb{E}[Y_{1}]=n^{\alpha}$. By combining Equation 6 with the law of total
expectation this implies that:

$\displaystyle\mathbb{E}[Y_{k}]\leq\left(\frac{1}{2}+\frac{1}{2}\left(\frac{3}{4}+\frac{c}{4}\right)\right)^{-1}\mathbb{E}[Y_{k-1}]$

Therefore by setting $k=\beta\cdot ln(n)$ and
$\gamma=\alpha-\beta\ln\left(\frac{7}{8}+\frac{c}{8}\right)$ we get that:

$\displaystyle\mathbb{E}[Y_{\beta\cdot
ln(n)}]\leq\left(\frac{7}{8}+\frac{c}{8}\right)^{-\beta\cdot
ln(n)}n^{\alpha}\leq exp\left(\gamma\ln(n)\right)=n^{\gamma}$ (7)

Notice that for any fixed $c,\beta$ for small enough $\alpha$ we have
$\gamma<0$ thus the expectation is polynomially small and by Markov’s
inequality:

$\displaystyle\mathbb{P}[Y_{\beta\cdot ln(n)}\geq
1]\leq\frac{\mathbb{E}[Y_{\beta\cdot ln(n)}]}{1}\leq n^{\gamma}$ (8)

Since $\mathbb{P}[X_{i}\leq n^{\alpha}]\leq\mathbb{P}[Y_{i}\geq 1]$ we get
$\mathbb{P}[X_{i}\leq n^{\alpha}]\leq n^{\gamma}$ which is what we aimed to
achieve in the first phase.

For the second phase, consider the neighbourhood of some $v\in X_{i}$
restricted to $I_{i+1}$, this neighbourhood is distributed according to
$\mathcal{D}$. The ball around $v$ of size $M$ is a random rooted tree with
offspring distribution $\mathcal{D}$ of height $M$. Let $Z_{v}$ denote the
random variable of the number of monotonically connected vertices to $v$ among
this neighbours. By Corollary 18 we know that
$\mathbb{E}[Z_{v}]=\sum_{i=1}^{M}\frac{c^{i}}{i!}>e$ for our choice of $M$.
Denote $\mathbb{E}[Z_{v}]$ by $\mu>e$, and pick $\mu>\mu^{\prime}>e$ such that
$\mu-\mu^{\prime}<1$. Denote $X_{i}=t$ and the elements of $S_{i}$ by
$x_{1},...,x_{t}$, notice that $X_{i+1}\geq\sum_{j=1}^{X_{i}}Z_{x_{j}}$, each
$Z_{x_{i}}$ is bounded by $\sum_{i=0}^{M}T^{i}\leq T^{M+1}$ since we use the
truncated distribution, and the $Z_{x_{i}}$ are independent therefore by
Bernstein inequality we get that

$\displaystyle\mathbb{P}[|\sum_{j=1}^{t}Z_{x_{j}}-\mu
t|\geq\left(\mu-\mu^{\prime}\right)t]\leq
2exp\left(-\frac{\left(\mu-\mu^{\prime}\right)^{2}t^{2}/2}{t\left(T^{M+1}\right)^{2}+T^{M+1}\cdot\frac{\left(\mu-\mu^{\prime}\right)t}{3}}\right)$
(9)

Since $\mu-\mu^{\prime}<1$ we know that
$T^{M+1}\cdot\frac{\left(\mu-\mu^{\prime}\right)t}{3}\leq
t\left(T^{M+1}\right)^{2}$ and thus:

$\displaystyle
2exp\left(-\frac{\left(\mu-\mu^{\prime}\right)^{2}t^{2}/2}{t\left(T^{M+1}\right)^{2}+T^{M+1}\cdot\frac{\left(\mu-\mu^{\prime}\right)t}{3}}\right)\leq
2exp\left(-\left(\frac{(\mu-\mu^{\prime})^{2}}{4T^{2M+2}}\right)t\right)=e^{-\Omega(t)}$
(10)

If we condition on the event that $X_{\beta\ln(n)}>n^{\alpha}$ then this
probability is $e^{-\Omega(n^{\alpha})}$ which implies that
$X_{\frac{\ln(n)}{2}}\geq(\mu^{\prime})^{(\frac{1}{2}-\beta)\ln(n)}X_{\beta\ln(n)}=n^{\ln(\mu^{\prime})(\frac{1}{2}-\beta)}$
w.h.p. We now note that we may first choose $T,M,\mu^{\prime}$, then find
$\beta$ such that $ln(\mu^{\prime})(\frac{1}{2}-\beta)>\frac{1}{2}$, denote
this quantity by $\tau>\frac{1}{2}$. Then pick $\alpha$ such that
$\gamma:=\alpha-\beta\ln\left(\frac{7}{8}+\frac{c}{8}\right)<0$. This implies
that $\mathbb{P}[X_{\frac{\ln(n)}{2}}\geq
n^{\tau}]>1-n^{-\gamma}-\ln(n)e^{-\Omega(n^{\alpha})}\geq(1-\frac{2}{n^{\gamma}})$.

Therefore the probability that $1,n$ are not connected by a monotone path is
at most
$\frac{2}{n^{\gamma}}+\frac{2}{n^{\gamma}+(1-p)^{n^{2\tau}}}=O(\frac{1}{n^{\gamma}}+(1-p)^{n^{2\tau}})$
where the left term corresponds to the event that $1$ connects to less than
$n^{\tau}$ vertices in $\\{1,\ldots,\frac{n}{2}\\}$, the middle term
corresponds to the event that $n$ connects to less than $n^{\tau}$ vertices in
$\\{\frac{n}{2}+1,\ldots,n\\}$ , and the last term corresponds to the
probability that both $1$ and $n$ connects by a monotone path to $n^{\tau}$
vertices in their half, and each edge between those sets is not present in the
random graph. Since $\tau>\frac{1}{2}$ we have
$(1-p)^{n^{2\tau}}=O(\frac{1}{n^{\gamma}})$ hence the probability of finding a
monotone $1$ to $n$ path is at least $1-O(\frac{1}{n^{\gamma}})$ as needed.

∎

##  4 Concluding Remarks and Open Problems

We remark that the proof of our extremal result is related to a result of [6]
about large cliques in induced $C_{4}$ free graphs..

Another direction is to improve the sufficient condition
$|\mathcal{P}|=\Omega(n\sqrt{n})$ in Theorem 1 to a weaker one. We conjecture
that Theorem 1 holds for any graph without density assumptions. Explicitly we
conjecture that any graph $G=(V,P)$ has a globally rigid subgraph in
$\mathbb{R}$ and $\Omega(\frac{|\mathcal{P}|}{|V|})$ vertices.

In a previous version we conjectured that for large enough constant $k$, every
$k$ connected graph is globally rigid. This was proved to be false in the work
of Girão, Illingworth, Michel, Powierski, and Scott [5] and seperates rigidity
in $\mathbb{R}$ and _generic_ rigidity in higher dimensions by the recent
breakthrough of Villányi [11] which proved that $d(d+1)$ connected graphs are
globally rigid in $\mathbb{R}^{d}$ assuming the embedding is generic.

In regard to the threshold of monotone path we believe it is interesting to
understand what happens at $c=1$? Another problem is to understand the
distribution of the number of monotonically connected vertices to a given
vertex. In particular consider a Galton-Watson process with off spring
distribution $\mathcal{D}$ and for which each node $v$ gets an auxiliary R.V
$X_{v}\sim U[0,1]$, and the root $r$ has $X_{r}=0$. What is the distribution
of the number of monotonically connected vertices to the root?

We conjectured that random graph $G$ sampled via the Erdős-Rényi evolution
becomes globally rigid in $\mathbb{R}$ exactly at the time its minimum degree
is $2$. This was proved by a clever argument of Montgomery, Nenadov and Szabó
[9] and extends to other models of random graphs, e.g. $d$-regular graphs with
$d\geq 6$.

We also believe it is interesting to construct sparse globally rigid graphs
with average degree as small as possible.

#### Acknowledgments

We thank Dan Bar, Nicolas Curien, Dániel Garamvölgyi, Bo’az Klartag, Eran
Nevo, Asaf Petruschka and Ran Tessler for useful discussions. The first author
would like to thank the ISF for their support under Grant 14.13.20.

## References

  * [1] Noga Alon and Joel H. Spencer.  The Probabilistic Method.  Wiley Publishing, 4th edition, 2016.
  * [2] Douglas Barnes, Jan Petr, Julien Portier, Benedict Randall Shaw, and Alan Sergeev.  Reconstructing almost all of a point set in $\mathbb{R}^{d}$ from randomly revealed pairwise distances, 2024.  arXiv:2401.01882.
  * [3] Itai Benjamini and Oded Schramm.  Recurrence of distributional limits of finite planar graphs.  Electronic Journal of Probability [electronic only], 6:Paper No. 23, 13 p., electronic only–Paper No. 23, 13 p., electronic only, 2001.  URL: http://eudml.org/doc/122590.
  * [4] Dániel Garamvölgyi.  Global rigidity of (quasi-)injective frameworks on the line.  Discrete Mathematics, 345(2):112687, 2022.  URL: https://www.sciencedirect.com/science/article/pii/S0012365X21004003, doi:https://doi.org/10.1016/j.disc.2021.112687.
  * [5] António Girão, Freddie Illingworth, Lukas Michel, Emil Powierski, and Alex Scott.  Reconstructing a point set from a random subset of its pairwise distances, 2023.  arXiv:2301.11019.
  * [6] András Gyárfás, Alice Hubenko, and József Solymosi.  Large cliques in _C_ ${}_{\mbox{4}}$-free graphs.  Comb., 22(2):269–274, 2002.  doi:10.1007/s004930200012.
  * [7] Tibor Jordan and Walter Whitely.  Handbook of Discrete and Computational Geometry, 3rd Edition, Chapter 63.  CRC Press LLC, 2017.
  * [8] Stasys Jukna.  Extremal Combinatorics - With Applications in Computer Science.  Texts in Theoretical Computer Science. An EATCS Series. Springer, 2011\.  doi:10.1007/978-3-642-17364-6.
  * [9] Richard Montgomery, Rajko Nenadov, and Tibor Szabó.  Global rigidity of random graphs in $\mathbb{R}$, 2024.  arXiv:2401.10803.
  * [10] Roman Vershynin.  High-Dimensional Probability: An Introduction with Applications in Data Science.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.  doi:10.1017/9781108231596.
  * [11] Soma Villányi.  Every $d(d+1)$-connected graph is globally rigid in $\mathbb{R}^{d}$, 2023\.  arXiv:2312.02028.