# Maximum likelihood thresholds via graph rigidity

Daniel Bernstein  Sean Dewar  Steven J. Gortler  Anthony Nixon  Meera Sitharam
Louis Theran

###### Abstract

The maximum likelihood threshold (MLT) of a graph $G$ is the minimum number of
samples to almost surely guarantee existence of the maximum likelihood
estimate in the corresponding Gaussian graphical model. We give a new
characterization of the MLT in terms of rigidity-theoretic properties of $G$
and use this characterization to give new combinatorial lower bounds on the
MLT of any graph.

We use the new lower bounds to give high-probability guarantees on the maximum
likelihood thresholds of sparse Erdös-Rényi random graphs in terms of their
average density. These examples show that the new lower bounds are within a
polylog factor of tight, where, on the same graph families, all known lower
bounds are trivial.

Based on computational experiments made possible by our methods, we conjecture
that the MLT of an Erdös-Rényi random graph is equal to its generic completion
rank with high probability. Using structural results on rigid graphs in low
dimension, we can prove the conjecture for graphs with MLT at most $4$ and
describe the threshold probability for the MLT to switch from $3$ to $4$.

We also give a geometric characterization of the MLT of a graph in terms of a
new “lifting” problem for frameworks that is interesting in its own right. The
lifting perspective yields a new connection between the weak MLT (where the
maximum likelihood estimate exists only with positive probability) and the
classical Hadwiger-Nelson problem.

##  1 Introduction

Modern statistical applications often require researchers to make inferences
about a large number of variables from few observations (see e.g. [31, Chapter
18]). For example, certain biological network modeling problems, including
those related to gene regulation [23, 53, 62] and metabolic pathways [40], can
be approached by fitting a Gaussian graphical model to a dataset that has
fewer datapoints than variables. This invites one to ask the motivating
question of this paper, which was previously explored by Uhler [58], who
attributes recent interest in it to Lauritzen: _given a fixed Gaussian
graphical model, what is the minimum number of datapoints required to fit it_?
We now define some terms and state the question more precisely.

Let $G$ be a graph with $n$ vertices. The Gaussian graphical model associated
with $G$ is the set of $n$-variate normal distributions
$\mathcal{N}(0,\Sigma)$ so that if $ij$ is _not_ an edge of $G$, then
$(\Sigma^{-1})_{ij}=0$, i.e. the corresponding random variables are
conditionally independent given all of the other random variables. Suppose now
that we have iid samples $X_{1},\ldots,X_{d}$ from a Gaussian graphical model.
The MLE of the covariance is, then, the inverse of the matrix $K$ that solves
the following optimization problem (see, e.g., [31, p. 632]) —l— KTrace(SK) -
logdetK K ∈S^n_++ and K_ij = 0 if ij ∉E(G) where $S$ is the sample
covariance111The sample covariance is $S=\frac{1}{d}XX^{T}$. and
$\mathcal{S}^{n}_{++}$ is the set of positive definite $n\times n$ matrices.
This is a convex problem that can be solved efficiently in practice [59].
Computing the MLE is a common way to fit a Gaussian graphical model to data.
If $d\geq n$ and $G$ is complete then the MLE of the covariance is $K=S^{-1}$.
Indeed, almost surely $S^{-1}$ exists and then

$\frac{d}{dK}\left(\operatorname{Trace}(SK)-\log\det K\right)=S-K^{-1}$

vanishes at $S^{-1}$. As a warmup for some of the ideas in Section 3, now
consider the case when $d<n$ and $G$ is complete. Since $S$ has rank at most
$d$, we can find a non-zero vector $v$ in the kernel of $S$. For all $t\geq
0$, $I+tvv^{T}$ is positive definite and

$\operatorname{Trace}(S(I+tvv^{T}))-\log\det(I+tvv^{T})=\operatorname{Trace}(S)-\log\det(I+tvv^{T})\to-\infty$

as $t\to\infty$. Hence the MLE of the covariance does not exist. What goes
wrong is that the sampled datapoints lie in a proper linear subspace of
$\mathbb{R}^{n}$, so we can “overfit” the sample by Gaussian densities that
have, as their level sets, increasingly flat ellipsoids.

If $G$ is not complete, however, the MLE might exist almost surely even when
$d<n$. This prompts the following definition.

######  Definition 1.1.

The _maximum likelihood threshold_ (MLT) of a graph $G$, denoted
$\operatorname{mlt}(G)$, is the smallest number of samples222Here, we are
assuming that the samples are i.i.d. from a distribution whose probability
measure is mutually absolutely continuous with respect to Lebesgue measure.
required for the MLE of the Gaussian graphical model associated with $G$ to
exist almost surely.

######  Remark 1.2.

The maximum likelihood threshold can be similarly defined for any class of
Gaussian models. See e.g. [3, 24, 45].

###  1.1 Existing bounds on the MLT

The discussion above implies that $\operatorname{mlt}(K_{n})=n$. For any $G$,
$1\leq\operatorname{mlt}(G)\leq n$, since if $H$ is a subgraph of $G$, then
$\operatorname{mlt}(H)\leq\operatorname{mlt}(G)$. Heuristically, if $G$ is
very sparse, we could hope that $\operatorname{mlt}(G)$ is much less than $n$.
However, counting edges is not enough to get good bounds, since, as we will
see, small or sparse subgraphs can push the MLT up.

Ideally, one would like an efficient algorithm to compute
$\operatorname{mlt}(G)$, but this seems difficult and the complexity of
computing $\operatorname{mlt}(G)$ remains open.333It follows from Dempster’s
work [22] that one can compute $\operatorname{mlt}(G)$ using, e.g.,
cylindrical decomposition of a semi-algebraic set, but the algorithms for this
task are not fast enough to be of practical interest. Instead, the literature,
which we now review, focuses on finding combinatorial properties that bound
the MLT, a problem first raised by Dempster [22] and, more recently,
popularized by Lauritzen (see [58, 5]). The first nontrivial bounds on the MLT
are due to Buhl [12].

######  Theorem 1.3 ([12]).

Let $G$ be a graph with clique number $\omega(G)$ and treewidth $\tau(G)$.
Then

$\omega(G)\leq\operatorname{mlt}(G)\leq\tau(G)+1.$

We will see presently that both of these estimates are unsatisfactory:
computing clique number and treewidth are NP-hard problems and both
inequalities are extremely weak. As a running example to compare inequalties,
we will use the complete bipartite graph $K_{m,m}$. Theorem 1.3 implies that

$2=\omega(K_{m,m})\leq\operatorname{mlt}(K_{m,m})\leq\tau(K_{m,m})+1=m+1.$

In a landmark paper that introduced maximum-likelihood geometry, Uhler [58]
used tools from algebraic geometry to bound the MLT.

######  Definition 1.4.

Let $G$ be a graph with $n$ vertices and $m$ edges. Let $\mathcal{S}^{d+1}$ be
the set of symmetric matrices of rank $d+1$. The _generic completion rank of
$G$_, denoted $\operatorname{gcr}(G)$, is the smallest $d+1$ so that the
orthogonal projection of $\mathcal{S}^{d+1}$ onto the diagonal entries and the
entries corresponding to the edges of $G$ is $(m+n)$-dimensional.

######  Theorem 1.5 ([58]).

Let $G$ be a graph. Then $\operatorname{mlt}(G)\leq\operatorname{gcr}(G)$.

Uhler formulated the generic completion rank in terms of a certain elimination
ideal being empty, but one can compute $\operatorname{gcr}(G)$ with a
randomized algorithm and linear algebra (see [30]). The upper bound from
Theorem 1.5 is very much tighter than the one from Theorem 1.3. It can also be
used to extract other combinatorial bounds on the MLT, for example the
presence of a $k$-core (the maximum induced subgraph of minimum degree $k$).
Via [7, Corollary 4.5], Uhler’s bound implies that if $k$ is the minimum
integer such that the $k$-core of $G$ is empty, then
$\operatorname{mlt}(G)\leq k-1$.

In our running example, we have

$\operatorname{mlt}(K_{m,m})\leq\operatorname{gcr}(K_{m,m})=m-2$

(see Theorem 1.6 below for the GCR of $K_{m,m}$). Thus, on our running
example, Uhler’s bound is better than Buhl’s _and_ it is much easier to
compute.

For some time, it was open whether, in fact,
$\operatorname{mlt}(G)=\operatorname{gcr}(G)$ for every graph $G$. Blekherman
and Sinn [8] provided a negative answer as part of a detailed study of
bipartite graphs. We will give a more detailed account of [8], but here is one
summary result.

######  Theorem 1.6 ([8]).

Let $m,D\in\mathbb{N}$ so that $m>2$ and $D$ is largest number satisfying
$2m>\binom{D+1}{2}$. Then

$\operatorname{gcr}(K_{m,m})=m\qquad\text{and}\qquad\operatorname{mlt}(K_{m,m})=D.$

Comparing with Theorem 1.3, we see that $K_{m,m}$ has clique number $2$ and
MLT $\Theta(\sqrt{m})$. Comparing with Theorem 1.5, we see that the upper
bound from generic completion rank is also off by an $O(\sqrt{m})$ factor,
making $\operatorname{gcr}(G)$ far from tight as an upper bound.

###  1.2 MLT and rigidity

In this paper, we give new lower bounds on the MLT, which are more general and
sharper than those mentioned above. Our methods are based on a connection to
graph rigidity theory, which we briefly introduce. Figure 1 illustrates the
following definitions for $d=2$.

######  Definition 1.7.

Let $d\in\mathbb{N}$ be a dimension. A _framework in $\mathbb{R}^{d}$_ is a
pair $(G,p)$ where $G$ is a graph with $n$ vertices $\\{1,\ldots,n\\}$ and
$p=(p(1),\ldots,p(n))$ is a configuration of $n$ points in $\mathbb{R}^{d}$.
Two frameworks $(G,p)$ and $(G,q)$ are _equivalent_ if

$\|p(j)-p(i)\|=\|q(j)-q(i)\|\qquad\text{ for all edges $ij$ of $G$}$

and _congruent_ if $p$ and $q$ are related by a Euclidean isometry, i.e. if
there exists a Euclidean isometry $T:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$
such that $q(i)=T(p(i))$ for $i=1,\dots,n$. If two frameworks are congruent,
then they are also equivalent but the converse need not hold. Frameworks for
which the converse _does_ hold are called _globally rigid_ in dimension $d$,
i.e. $(G,p)$ is globally rigid if all equivalent $d$-dimensional frameworks
are congruent. If this happens only for some neighborhood $U$ around $p$, i.e.
if $(G,p)$ and $(G,q)$ are congruent whenever $q\in U$ and $(G,q)$ and $(G,p)$
are equivalent, then $(G,p)$ is said to be _rigid_ in dimension $d$.

$\leftrightarrow$

$\leftrightarrow$

Figure 1: Above are some frameworks in $\mathbb{R}^{2}$. The framework on the
left fails to be rigid because there exist arbitrarily close frameworks that
are equivalent but not congruent - one can deform it an arbitrarily small
amount as indicated. The frameworks in the middle fail to be globally rigid
since they are equivalent but not congruent. They are, however, rigid. Indeed,
neither can be perturbed an infinitesimally small amount without changing edge
lengths. Finally, the framework on the right is globally rigid and therefore
also rigid.

On an intuitive level, rigidity of a $d$-dimensional framework $(G,p)$ means
that if one were to physically build $G$ in $\mathbb{R}^{d}$ using rigid bars
for the edges and universal joints for the vertices, placed according to $p$,
then the resulting structure could not deform. Rigidity of a specific
framework is difficult to check [1], but for each dimension $d$, every graph
has a generic behavior. Following [58, 30], we use the following notion of
generic, which comes from algebraic geometry.

######  Definition 1.8.

Let $p$ be a configuration of $n$ points in $\mathbb{R}^{d}$. We say that $p$
is _generic_ if the coordinates of $p$ do not satisfy any polynomial with
rational coefficients.

The following theorem is fundamental in combinatorial or graph rigidity
theory. It tells us that by invoking a genericity assumption, we can treat
rigidity and global rigidity as properties of a graph rather than as
properties of a framework.

######  Theorem 1.9 ([4, 29]).

Let $d$ be a fixed dimension and $G$ a graph. Then either every generic
$d$-dimensional framework $(G,p)$ is (globally) rigid or every generic
$d$-dimensional framework $(G,p)$ is not (globally) rigid.

######  Definition 1.10.

Let $d$ be a fixed dimension and $G$ be a graph with $m$ edges. We call $G$
_(globally) $d$-rigid_ if its generic $d$-dimensional frameworks are
(globally) rigid. We call $G$ _$d$ -independent_ if there is an
$m$-dimensional space of differential changes to the edge lengths of a (or
any) generic framework $(G,p)$.

In Figure 1, the graphs underlying the frameworks in the middle and on the
left are $2$-independent, whereas the graph of the framework on the right is
not. To see this, note that in frameworks in the middle and left, it is
possible to increase or decrease the length of any edge a small amount without
changing any other edge lengths. This is not the case for the framework on the
right.

An important fact in rigidity theory is that the $d$-independent graphs form
the independent sets of a matroid. Gross and Sullivant [30] reformulated
Theorem 1.5 in the language of algebraic matroids (see [51] for an
introduction) and proved the following.

######  Theorem 1.11 ([30]).

Let $G$ be a graph. Then the generic completion rank of $G$ is $d+1$ if and
only if $d$ is the smallest dimension in which $G$ is $d$-independent.

This result does not improve Uhler’s upper bound on the MLT, but it does open
up the possibility of employing graph rigidity-theoretic ideas to understand
it better. An interesting example is:

######  Theorem 1.12 ([30]).

If $G$ is a planar graph, then $\operatorname{mlt}(G)\leq 4$.

The proof uses the Cauchy–Dehn–Alexandrov theorem (see [26]) which implies
that any planar graph is $3$-independent. One can immediately deduce the same
bound for the wider class of $K_{5}$-minor free graphs using a result of Nevo
[47].

Graph rigidity theory also makes it easier to compare treewidth to the generic
completion rank. The following shows just how far away from tight Buhl’s upper
bound can be. In the sequel, we will make statements about sequences of events
$E_{n}$ involving random graph families indexed by the number of vertices $n$
that hold _with high probability_ (whp). This means that
$\mathbb{P}\left(E_{n}\right)\to 1$ as $n\to\infty$.

It is well-known that, for $d\geq 2$, a random $(d+1)$-regular graph $G$ with
$n$ vertices has, whp, treewidth $\tau(G)>\beta n$, for some $\beta>0$ (see,
e.g, [39]). Since, for $d\geq 2$, the only $(d+1)$-regular graph that is not
$d$-independent is $K_{d+2}$ [33], Theorem 1.11 implies that

$\operatorname{gcr}(G)\leq d+1<\beta n<\tau(G)+1$

whp for a random $(d+1)$-regular graph $G$.

###  1.3 Results and guide to reading

In this paper, we will reformulate the MLT of a graph in terms of equilibrium
stresses, a graph rigidity-theoretic concept that plays an important role in
global rigidity. Given vertices $i$ and $j$ of a graph $G$, we write $i\sim j$
to indicate that $G$ has an edge between $i$ and $j$.

######  Definition 1.13.

Let $G$ be a graph with $n$ vertices and let $(G,p)$ be a framework. An
_equilibrium stress_ $\omega$ of $(G,p)$ is an assignment of weights
$\omega_{ij}$ to the edges of $G$ so that, for all vertices $i$

$\sum_{j\sim i}\omega_{ij}(p(j)-p(i))=0\qquad\text{(sum over neighbors $j$ of
$i$).}$

The _equilibrium stress matrix_ associated to an equilibrium stress $\omega$
is the matrix $\Omega$ obtained by setting
$\Omega_{ji}=\Omega_{ij}=-\omega_{ij}$ for all edges $ij$ of $G$,
$\Omega_{ii}=\sum_{j}\omega_{ij}$ and all other entries zero. The _rank_ and
_signature_ of $\omega$ are defined to be the rank and signature of $\Omega$,
and $\omega$ is said to be _PSD_ if $\Omega$ is positive semi-definite.

A fact going back to Maxwell [46] is that a framework $(G,p)$ in dimension $d$
is independent if and only of it has no non-zero equilibrium stress.
Similarly, a graph is $d$-independent if and only if no generic framework
$(G,p)$ has a non-zero equilibrium stress.

To see the relation with Uhler’s bound (Theorem 1.5), we can use Theorem 1.11
and the discussion above to get the following formulation.

######  Theorem 1.14 ([58, 30]).

Let $G$ be a graph with $n$ vertices. Suppose that no generic framework in
dimension $d$ supports a non-zero equilibrium stress. Then the MLT of $G$ is
at most $d+1$.

To obtain a lower bound on the MLT, we will need to consider the signature of
the equilibrium stress. Our central new tool will be the following theorem,
proved in Section 3.

######  Theorem 1.15.

Let $G$ be a graph with $n$ vertices. Then the MLT of $G$ is $d+1$ if and only
if $d$ is the smallest dimension in which no generic $d$-dimensional framework
supports a non-zero PSD equilibrium stress.

This technical theorem along with some known graph rigidity-theoretic results
and arguments will allow us to significantly expand our understanding of the
MLT (as well as directly reproduce most of what is already understood).

To return to our running example, Theorem 1.6 implies that $K_{m,m}$
generically supports equilibrium stresses in dimension $m-2$, but that they
are all indefinite. In Section 5, we will re-derive Theorem 1.6 by first
understanding the equilibrium stresses of complete bipartite graphs.

There is a geometric counterpart to Theorem 1.15, originally conjectured by
Gross and Sullivant [30]. A $d$-dimensional framework $(G,p)$ _has full affine
span_ if $p$ affinely spans $\mathbb{R}^{d}$.

######  Theorem 1.16.

Let $G$ be a graph with $n$ vertices. Then the MLT of $G$ is $d+1$ if and only
if $d$ is the smallest dimension in which every generic $d$-dimensional
framework $(G,p)$ is equivalent to an $(n-1)$-dimensional framework
$(G,\tilde{p})$ with full affine span.

$\leftrightarrow$

$\leftrightarrow$

Figure 2: The framework in $\mathbb{R}^{1}$ on the left is equivalent to a
framework in $\mathbb{R}^{3}$ with full-dimensional affine span. To see this,
first note that it is equivalent to the framework in $\mathbb{R}^{2}$ to the
right of it. Then note that this two-dimensional framework is equivalent to a
framework in $\mathbb{R}^{3}$ with full-dimensional affine span since we can
lift one of the vertices into the third dimension without changing edge-
lengths. However, the maximum likelihood threshold of the underlying graph,
the four-cycle, is _not_ two since every framework equivalent to the framework
in the middle has a one-dimensional affine span. On the other hand, the path
with four vertices has an MLT of $2$ because any generic one-dimensional
framework on it can be folded out to three dimensions. On the right, we see
such a one-dimensional framework folding out into two dimensions. We can
further fold it into three by bringing the vertex on the left out of the
affine plane spanned by the other vertices.

See Figure 2 for an illustration of Theorem 1.16.

To give combinatorial bounds, we use a connection between globally rigid
graphs and PSD equilibrium stresses from [19]. Our bounds are in terms of a
new graph parameter based on globally rigid subgraphs of $G$.

######  Definition 1.17.

The _global rigidity number_ of $G$, denoted $\operatorname{grn}(G)$, is the
maximum $d$ such that $G$ is globally $d$-rigid and has at least $d+2$
vertices. The _globally rigid subgraph number_ of $G$, denoted
$\operatorname{grn}^{*}(G)$, is the maximum $d$ so that $G$ contains a
subgraph $H$ on at least $d+2$ vertices that is globally rigid.

We obtain the following new lower bound on the MLT of a graph.

######  Theorem 1.18.

Let $G$ be a graph. Then
$\operatorname{grn}(G)+2\leq\operatorname{grn}^{*}(G)+2\leq\operatorname{mlt}(G)$.

Since complete graphs are globally $d$-rigid for all $d$, Theorem 1.18
generalizes the lower bound of Theorem 1.3. To our knowledge, this is the
first unconditional improvement of Buhl’s lower bound from 1993 (Theorem 1.3).

In our running example of $K_{m,m}$, the lower bound from Theorem 1.18 gives
the right answer. The complete bipartite graph $K_{m,m}$ has global rigidity
number $m-3$ [20] and, by Theorem 1.6, MLT $m-1$. Hence
$\operatorname{mlt}(K_{m,m})=\operatorname{grn}(K_{m,m})+2$.

In Section 7, we combine Theorem 1.18 with results on graph rigidity in
dimension $2$ to completely solve the MLT problem for small values of
$\operatorname{mlt}(G)$ and $\operatorname{gcr}(G)$. The main result (which is
best possible – see Remark 7.5) is as follows.

######  Theorem 1.19.

If $G$ is a graph and $\operatorname{mlt}(G)\leq 3$ or
$\operatorname{gcr}(G)\leq 4$, then
$\operatorname{mlt}(G)=\operatorname{gcr}(G)$.

Theorem 1.18 is also strong enough to give a quick proof of the results in
[8]. Section 5 explores the connection.

###  1.4 Improvement in MLT bounds

The following table summarizes the MLT bounds for various families of graphs
given in this paper and compares with the best known previous bounds. Let
$d>1$.

Type of Graph | Best Previous MLT interval | This Paper
---|---|---
Minimally $d$-rigid |  $[2,d+1]$ Thm 1.3 |  $d+1$ Cor 4.8
Globally $d$-rigid $d$-circuit |  $[2,d+2]$ Thm 1.3 |  $d+2$ Cor 4.10
$G(n,c/n)$ $0<c<c’_{2}$ |  $[3,4]$ Thm 1.5 [7] | 3 whp Thm 2.3
$G(n,c/n)$ $c’_{2}<c<c_{3}$ |  $[3,4]$ Thm 1.5 [7] | 4 whp Thm 2.3
$G(n,M_{d}\log n/n)$ |  $\exists k[3,(\log n)^{k}]$ whp Thm 1.3,1.5 |  $\exists k[d,(\log n)^{k}]$ whp Cor 2.9

##  2 Examples and conjectures

The families of graphs for which the MLT has been computed exactly are quite
limited in the literature. As mentioned in the introduction, Buhl [12]
computes $\operatorname{mlt}(K_{d+2})=d+1$ and Bleckhermann and Sinn [8]
compute $\operatorname{mlt}(K_{m,n})$ (see Section 5). Uhler [58] provides, in
addition, that the MLT of a cycle is $3$.

This sections contains examples illustrating improvements that can be obtained
from our methods and some remaining conjectures.

###  2.1 4-regular graphs

As discussed above, any connected $4$-regular graph $G$ on $n>5$ vertices is
$3$-independent and, hence, by Theorem 1.11, $\operatorname{gcr}(G)\leq 4$.
Since $G$ has $2n>2n-3$ edges, the Laman–Pollaczek-Geiringer Theorem (Theorem
7.2, below) implies that $G$ is $2$-dependent so $\operatorname{gcr}(G)>3$,
again via Theorem 1.11. On the other hand, it is well-known that, whp, a
random $4$-regular graph has clique number at most $3$444One way to see this
is that a $4$-regular graph containing a subgraph isomorphic to $K_{4}$ is not
essentially $6$-connected. Random $4$-regular graphs are essentially
$6$-connected with high probability [61].. We now have that, whp, for a random
$4$-regular graph $G$:

$\omega(G)\leq 3<4=\operatorname{mlt}(G).$

This gap, while not terribly impressive, was easy to get.

###  2.2 Random graphs near the 2-dimensional rigidity transition

A very sparse Erdös-Renyi random graph $G(n,c/n)$ has each of the
$\binom{n}{2}$ possible edges independently with probability $c/n$. Hence the
vertex degrees have (dependent) binomial distributions with parameters $n-1$
and $c/n$. As $n\to\infty$ the vertex degrees approach Poisson random
variables with parameter $c$. Hence, when discussing such graphs we will refer
to $c$ as the “expected average degree”.

A central result in the theory of random graphs describes the emergence and
growth of the $k$-core of an Erdös-Rényi random graph $G(n,p)$. We state a
simplified version (using the letter $d$ instead of $k$, because it makes more
sense for our application).

######  Theorem 2.1 ([49]).

For each $d\geq 2$ there are constants $c_{d}<c^{\prime}_{d}$, so that

  * •

If $c<c_{d}$, then, whp, $G(n,c/n)$ has an empty $(d+1)$-core. If $c>c_{d}$,
then, whp, $G(n,c/n)$ has a non-empty $(d+1)$-core spanning $\Omega(n)$
vertices.

  * •

If $c_{d}<c<c^{\prime}_{d}$, then, whp, the $(d+1)$-core of $G(n,c/n)$ has
average degree lower than $2d$. If $c>c^{\prime}_{d}$, then, whp, the
$(d+1)$-core has average degree at least $2d$.

Moreover, $c^{\prime}_{d}<c_{d+1}$.

For reference, the value of $c_{2}\approx 3.35$ and $c^{\prime}_{2}\approx
3.59$. As $d$ becomes large, $c^{\prime}_{d}$ approaches $2d$.

What is most important for is that $c^{\prime}_{2}/n$ is the threshold
function for an Erdös-Rényi random graph to be $2$-independent.

######  Theorem 2.2 ([37]).

In the notation of Theorem 2.1, if $c<c^{\prime}_{2}$, then, whp, $G(n,c/n)$
is $2$-independent555And, in fact, has no rigid component spanning more than
$3$ vertices.. If $c>c^{\prime}_{2}$, then, whp, $G(n,c/n)$ contains a
globally $2$-rigid666That we have global rigidity was first noted by Bill
Jackson. subgraph spanning a $(1-o(1))$-fraction of the $3$-core (hence
spanning $\Omega(n)$ vertices).

Using Theorem 1.19, we get immediately:

######  Theorem 2.3.

In the notation of Theorem 2.1,

  * •

If $c_{2}<c<c^{\prime}_{2}$, then, whp, $\operatorname{mlt}(G(n,c/n))=3$.

  * •

If $c^{\prime}_{2}<c<c_{3}$, then, whp $\operatorname{mlt}(G(n,c/n))=4$.

In particular, in this range,
$\operatorname{mlt}(G(n,c/n))=\operatorname{gcr}(G(n,c/n))$, whp.

As a comparison, since Erdös-Rényi graphs with $p=c/n$, for any $c>0$, are
well-known to have clique number $3$, whp, Theorem 1.3 would give a lower
bound of $3$ across this entire range. Combining Theorem 1.5 and [7, Corollary
4.5], we would get an upper bound of $4$ on the MLT in the range
$c_{2}<c<c^{\prime}_{2}$. Using our methods, we get an exact result in the
whole range.

###  2.3 Conjectures and a question

The following conjecture generalizes Theorem 2.3.

######  Conjecture 2.4.

Let $c>0$ be fixed. Then,
$\operatorname{mlt}(G(n,c/n))=\operatorname{gcr}(n,c/n)$, whp.

In other words, we conjecture that for _all_ very sparse Erdös-Rényi random
graphs, the MLT and GCR coincide whp.

We will go further and make a structural conjecture that goes beyond Theorem
2.3 even for GCR $4$. We need some terminology. A edge $ij$ of a graph $G$ is
_$d$ -redundant_ if there is some generic $d$-dimensional framework $(G,p)$
that has an equilibrium stress with a non-zero coefficient on the edge $ij$.
The _$d$ -redundant subgraph of $G$_ is the subgraph comprising all the
$d$-redundant edges.

######  Conjecture 2.5.

Let $c>0$ be fixed. Then, whp, if $G=G(n,c/n)$ has GCR $d+1\geq 4$, the
$(d-1)$-redundant subgraph of $G$ is generically globally $(d-1)$-rigid.

This conjecture implies that the MLT and GCR are equal, whp, using Theorem
1.18, but with the added precision of identifying the globally rigid subgraph
that certifies the lower bound. The conjecture does not include GCR $3$ and
lower, where we do not expect it to be true. The reason is that, for
$c<c^{\prime}_{2}$, the $1$-redundant subgraph is not $2$-connected whp, and
$2$-connectivity is necessary for generic global rigidity [32]. We provide
theoretical and experimental evidence for the conjecture in the next section.

We conclude with a question, which does not seem empirically resolved by our
experiments.

######  Question 2.6.

Let $c>0$ be fixed. Is it true that, whp, if $G=G(n,c/n)$ has MLT $d+1\geq 4$
that the $(d-1)$-redundant subgraph of $G$ is exactly the $d$-core?

A positive answer to the question would imply that the MLT (and also global
rigidity) of sparse Erdös-Rényi random graphs has the same evolution as the
$d$-cores.

###  2.4 Theoretical evidence for the conjectures

Aside from it being true for $d=2$, a weaker result for $d\geq 3$ provides
evidence for the conjecture. In Appendix D we will show the following
result777While this paper was in preparation, Lew, Nevo, Peled and Raz [43]
found the sharp threshold for rigidity. However, their improved result does
not lead to a qualitatively better bound on the MLT than we state here..

######  Theorem 2.7.

Let $d\geq 1$. There is a $C_{d}>0$ and a $k\in\mathbb{N}$ such that, whp,
$G(n,C_{d}(\log n)^{k}/n)$ is $d$-rigid.

We now get, by combining Theorem 2.7 and Theorem 4.4 below:

######  Theorem 2.8.

Let $d\geq 1$. There is a $M_{d}>0$ and $k\in\mathbb{N}$, such that, whp,
$\operatorname{mlt}(G(n,M_{d}(\log n)^{k}/n))\geq d$.

Since, whp, the graphs in Theorem 2.8 have clique number $3$, the lower bound
from Theorem 1.3 becomes increasingly ineffective. On the other side, we do
not have a good upper bound on $\operatorname{gcr}(G(n,M_{d}(\log n)^{k}/n))$.
A simple bound on the GCR is based on maximum degree. If a graph $G$ has
maximum degree $\Delta$ then it is $\Delta$-independent, so we can use the
fact that, whp, the maximum degree of $G(n,M_{d}(\log n)^{k}/n)$ is
$O(\operatorname{polylog}(n))$ to deduce:

######  Corollary 2.9.

In the notation of Theorem 2.8, then, there are $k,\ell\in\mathbb{N}$ such
that, whp, for every $d\geq 1$,

$d\leq\operatorname{mlt}(G(n,M_{d}(\log n)^{k}/n))\leq(\log n)^{\ell}$

where $M_{d}$ and $k$ are from Theorem 2.8.

We have not tried to optimize the upper bound, since we believe that the
maximum degree is not a good estimate of the GCR for these random graphs.

###  2.5 Experimental evidence for the conjectures

To test Conjectures 2.4 and 2.5, we ran experiments on Erdös-Rényi random
graphs. For fixed numbers of vertices $n=30,500$ and expected average degree
$c$ from $3$ to $30$ with step size $0.1$ we generated $20$ samples from
$G(n,c/n)$ and computed: the GCR $d+1$; whether the $(d-1)$-redundant subgraph
is generically globally rigid in dimension $d$; and whether the
$(d-1)$-redundant subgraph is equal to the $d$-core.

Computing the GCR, identifying the redundant subgraph, and checking global
rigidity are done using a randomized algorithm based on linear algebra over
finite fields [29].

These computations rely on the results of this paper in an essential way. In
particular, we need the lower bound from Theorem 1.18 to certify that the MLT
is equal to the GCR. Without Theorem 1.18, we would have to rely on heuristic
numerical experiments instead.

In all of our runs, when the GCR is at least $4$, the $(d-1)$-redundant
subgraph was generically globally rigid. This is consistent with Conjectures
2.5 and 2.4. (Recall that for GCR of $3$, Conjecture 2.4 is true from Theorem
2.3, and that Conjecture 2.5 is not expected to hold.)

The charts in Figure 3 show the evolution of the GCR (which is equal to the
MLT) as the expected average degree increases in our experiments for two
values of $n$ over a common range of $c$. The transition from $3$ to $4$
happens quickly between $c=3.4$ and $c=3.6$ as predicted by Theorem 2.3.

In all of our runs, when the GCR is in the range $3-6$, the equality of the
$(d-1)$-redundant subgraph and the $d$-core held at least $97\%$ of the time,
but this fraction did not seem to go up as we increased the number of vertices
from $30$ to $1000$. In all of our runs, when the GCR is at least $7$, the
equality of the $(d-1)$-redundant subgraph and the $d$-core held all of the
time.

|
---|---
Figure 3: Evolution of the GCR in $G(n,c/n)$ as the expected average degree,
$c$ increases. The $x$-axis shows the $c$ values. The $y$-axis is labeled by
the integer valued, possible GCR values. As stated in the text, all of the
given GCR values were equal to the MLT. Each curve in horizontal slice shows
the proportion of samples that produced the associated GCR. The left chart is
$n=30$ and the right is $n=500$. Already, in the left chart, we see that each
GCR values is only observed for a small range of $c$ values. The left chart
spans the range from sparse to dense graphs on $30$ vertices. In the right
chart, we see that, for most $c$ under consideration, we only observe a single
GCR value, and that these phase transition regions, especially in the lowest
$c$ ranges, have tightened. This is consistent with our conjectures. The right
chart only looks at relatively sparse graphs on $500$ vertices. Also note, in
this sparse region, that the trend of the peaks of the bumps is linear, with
GCR approximately equal to $3/2+c/2=3/2+m/n$, where $m$ is the expected number
of edges.

The code is available from the author’s web
site888https://gist.github.com/theran/994b4d355e56529f5e6642fec4aead98 and the
data used to generate the charts, including the random graphs, is available
upon request.

##  3 Stress geometry of the MLT

In this section we develop a detailed geometric understanding of the MLT. Our
main tool for doing this is the theory of PSD equilibrium stresses of
frameworks. The importance of PSD equilibrium stresses has long been known in
rigidity [14] and graph theory [57, 44]. Uhler [58] has pointed out the semi-
algebraic nature of the MLT problem. Here we make the connection precise
enough to exactly describe the MLT in terms of equilibrium stresses.

###  3.1 Linear equilibrium stresses

To connect to the optimization problem underlying the MLT, we introduce the
notion of a linear equilibrium stress, which is implicit in a number of works
around rigidity in geometries with projective models (see [48] and the
references therein). We start with some notation relating to vector
configurations.

######  Definition 3.1.

Let $q$ be a configuration of $n$ vectors in $\mathbb{R}^{d+1}$. Denote by
$t_{i}$ the last coordinate of $q(i)$ and by $Q$ the $(d+1)\times n$ matrix
with the $q(i)$ as its columns. We say that $q$ is _flat_ if all the $t_{i}$
are one, and that $q$ is _flattenable_ if all the $t_{i}$ are non-zero.

Generic configurations are clearly flattenable. There is a unique flat
configuration associated with a flattenable configuration $q$ arising from
scaling $q(i)$ by $1/t_{i}$. Flat vector configurations in $\mathbb{R}^{d+1}$
are naturally associated with affine point configurations in $\mathbb{R}^{d}$.

######  Definition 3.2.

Let $p$ be a configuration of $n$ points in $\mathbb{R}^{d}$. We denote by
$\hat{p}$, the vector configuration in $\mathbb{R}^{d+1}$ defined by the
standard homogeneous coordinates for $p$, i.e.

$\hat{p}(i)=\begin{pmatrix}p\\\ 1\end{pmatrix}.$

The matrix $\hat{P}$ is $(d+1)\times n$ with the vectors $\hat{p}(i)$ as its
columns.

######  Definition 3.3.

Let $d$ be a dimension. Let $G$ be a graph with $n$ vertices and let $q$ be a
vector configuration of $n$ vectors in $\mathbb{R}^{d+1}$. An assignment
$\omega$ of weights $\omega_{ij}$ to the edges $ij$ of $G$ and $\omega_{ii}$
to the vertices of $G$ is a _linear equilibrium stress_ for $q$ if

$\sum_{j\sim i}\omega_{ij}q(j)=\omega_{ii}q(i)\qquad\text{(all $i\in V(G)$).}$
(1)

For a fixed $\omega$, we say that _$q$ satisfies $\omega$_ if (1) holds. A
_linear equilibrium stress matrix_ $\Omega$ for $q$ is a symmetric $n$-by-$n$
matrix with $\Omega_{ij}=0$ for non-edges of $G$ such that

$\Omega Q^{T}=0,$

where $Q$ is the $(d+1)\times n$ matrix with the $q(i)$ as its columns. Given
a linear equilibrium stress $\omega$ for $q$, we can make a linear equilibrium
stress matrix for it by setting $\Omega_{ij}=\Omega_{ji}=-\omega_{ij}$ on the
edges and setting the diagonals $\Omega_{ii}=\omega_{ii}$. Hence the vector
configurations satisfying a given set of weights arise from the kernel of the
associated linear equilibrium stress matrix.

The following lemma is immediate. It gives the precise relationship between
equilibrium stresses and _linear_ equilibrium stresses.

######  Lemma 3.4.

Let $G$ be a graph with $n$ vertices and let $(G,p)$ be a $d$-dimensional
framework. Then for any equilibrium stress $\omega$ of $(G,p)$, the associated
stress matrix gives a linear equilibrium stress of $\hat{p}$. Any linear
equilibrium stress matrix $\Omega$ for $\hat{p}$ is also an equilibrium stress
matrix for $(G,p)$.

Linear equilibrium stresses are well-behaved under scaling. Results similar to
the following can be found in e.g. [18, 17].

######  Lemma 3.5.

Let $G$ be a graph with $n$ vertices and let $q$ be a vector configuration in
$\mathbb{R}^{d+1}$. If $\Omega$ is a linear equilibrium stress matrix for $q$
and $s_{1},\ldots,s_{n}$ are any non-zero real numbers, then the configuration
$\tilde{q}$, defined by

$\tilde{q}(i)=\frac{1}{s_{i}}q(i)$

has a linear equilibrium stress matrix with the same signature as $\Omega$.

###### Proof.

Take $q$ and the $s_{i}$ as in the statement, and let $\omega$ be the linear
equilibrium stress for $q$ from the statement. For each vertex $i$ and edge
$ij$, define

$\tilde{\omega}_{ij}=s_{i}s_{j}\omega_{ij}\qquad\text{and}\qquad\tilde{\omega}_{ii}=s^{2}_{i}\omega_{ii}.$

Then $\tilde{\omega}$ is a linear equilibrium stress for $\tilde{q}$ because
for each vertex $i$ we have

$\sum_{j\sim i}\tilde{\omega}_{ij}\tilde{q}(j)=s_{i}\sum_{j\sim
i}\omega_{ij}q(j)=s_{i}\omega_{ii}q(i)=s_{i}^{2}\omega_{ii}\tilde{q}(i)=\tilde{\omega}_{ii}q(i).$

Let $\tilde{\Omega}$ be the stress matrix associated to $\omega$ and let $S$
be the diagonal matrix whose diagonal entries are $s_{1},\dots,s_{n}$. Then
$\tilde{\Omega}=S\Omega S$ and thus $\Omega$ and $\tilde{\Omega}$ have the
same signature. ∎

We get an important special case when $s_{i}$ is the last coordinate of $q(i)$
for each $i$.

######  Lemma 3.6.

Let $G$ be a graph with $n$ vertices, let $q$ be a flattenable configuration
of $n$ vectors in $\mathbb{R}^{d+1}$, and let $(G,p)$ be the framework in
$\mathbb{R}^{d}$ that arises from flattening $q$ and deleting the all-ones
coordinate. If there is a linear equilibrium stress matrix $\Omega$ for $q$,
then $p$ has an equilibrium stress matrix of the same signature as $\Omega$.

###### Proof.

If we denote by $\hat{p}$ the flattening of $q$, then by Lemma 3.5 there is a
linear equilibrium stress for $\hat{p}$ with the same signature as $\Omega$.
This stress is an equilibrium stress of $(G,p)$ by Lemma 3.4. ∎

###  3.2 The optimization problem

We now describe the MLT optimization problem. For convenience, we denote the
inner product $\operatorname{Trace}(AB)$ on the set of symmetric $n\times n$
matrices by $\left\langle{A},{B}\right\rangle$.

######  Definition 3.7.

Let $G$ be a graph with $n$ vertices. Let $D$ be an $n\times(d+1)$ matrix with
columns representing $(d+1)$ samples from an $n$-variate probability
distribution. Let $S=\frac{1}{d}DD^{T}$ be the sample covariance matrix. _The
MLT optimization problem for $(G,D)$_ is to find an $n\times n$ positive
definite matrix $K$ minimizing $f(K)=\left\langle{S},{K}\right\rangle-\log\det
K$, subject to $K_{ij}=0$ for all $ij\notin E(G)$.

The rigidity-theoretic viewpoint requires us to transpose our view of the data
matrix. In particular, instead of thinking about $S$ as the sample covariance
obtained from $(d+1)$ samples of an $n$-variate distribution, we will think
about $S$ as the Gram matrix of a configuration of $n$ points in
$(d+1)$-dimensional space. This allows us to recast the MLT optimization
problem in the following equivalent way.

######  Definition 3.8.

Let $G$ be a graph with $n$ vertices and let $q$ be a configuration of $n$
vectors in dimension $d+1$. Let $S=Q^{T}Q$ be the Gram matrix of $q$. _The
Gram MLT optimization problem for $(G,q)$_ is to find an $n\times n$ positive
definite matrix $K$, minimizing
$g(K)=\left\langle{S},{K}\right\rangle-\log\det K$, subject to $K_{ij}=0$ if
$ij\notin E(G)$.

######  Lemma 3.9.

Let $G$ be a graph with $n$ vertices and let $q$ be a configuration of $n$
vectors. Then the Gram MLT optimization problem (objective function $g$) is
unbounded if and only if there is a nonzero PSD linear equilibrium stress for
$q$.

###### Proof.

Let $S$ be the Gram matrix of $q$. Suppose that $\Omega$ is the PSD stress
matrix of a non-zero linear equilibrium stress for $q$. For any $t>0$, the
matrix $I+t\Omega$ is positive definite and

$g(I+t\Omega)=\left\langle{S},{I+t\Omega}\right\rangle-\log\det(I+t\Omega).$

Since

$\left\langle{S},{I+t\Omega}\right\rangle=\left\langle{S},{I}\right\rangle+t\left\langle{S},{\Omega}\right\rangle=\left\langle{S},{I}\right\rangle+t\operatorname{Trace}{Q^{T}Q\Omega}=\left\langle{S},{I}\right\rangle+t\operatorname{Trace}{Q^{T}0}=\left\langle{S},{I}\right\rangle$

we conclude that

$g(I+t\Omega)=\operatorname{Trace}{S}-\log\det(I+t\Omega)\to-\infty\qquad\text{(as
$t\to\infty$)}.$

So the optimization problem is unbounded.

For the other direction we prove the contrapositive. Suppose that there is no
non-zero PSD linear equilibrium stress matrix for $q$. We show that the gram
MLT optimization problem has a global minimum. Let $\SS$ be be the set of
symmetric $n\times n$ matrices $\Omega$ with zeros on the non-edges of $G$
satisfying $\left\langle{\Omega},{\Omega}\right\rangle=1$. For any
$\Omega\in\SS$, there is a $t_{0}>0$ so that $K=I+t_{0}\Omega$ is a feasible
point of the Gram MLT optimization problem. Define $t^{*}\geq t_{0}>0$ to be
the supremum over values such that $I+t\Omega$ is positive definite. We will
show that, for any $\Omega\in\SS$,

$g(I+t\Omega)\to\infty\qquad\text{(as $t\to t^{*}$).}$

It then follows that, outside of a compact neighborhood of $I$,
$g(I+t\Omega)>g(I)$, which implies that $g$ has a global minimum. There are
two cases. If $\Omega\in\SS$ is not PSD, then $t^{*}$ is finite, and, as $t\to
t^{*}$,

$g(I+t\Omega)=\operatorname{Trace}S+t\left\langle{S},{\Omega}\right\rangle-\log\det(I+t\Omega)\to\infty,$

since the last term grows without bound and the linear terms have bounded
magnitude. If $\Omega$ is PSD, then $I+t\Omega$ is positive definite for any
$t>0$, and so $t^{*}=\infty$. We then have, as $t\to\infty$,

$g(I+t\Omega)=\operatorname{Trace}S+t\left\langle{S},{\Omega}\right\rangle-\log\det(I+t\Omega)=\operatorname{Trace}S+t\left\langle{S},{\Omega}\right\rangle-O(\log
t)$

because the determinant is a polynomial of degree $n$ in $t$. Finally, since
$S$ and $\Omega$ are PSD and $\Omega$ is not a linear equilibrium stress
matrix, $\left\langle{S},{\Omega}\right\rangle>0$, so

$g(I+t\Omega)\to\infty\qquad\text{(as $t\to\infty$)}.\qed$

###  3.3 Proof of Theorem 1.15

We are now ready to prove Theorem 1.15. Lemmas 3.10 and 3.11 below each give
one direction. What is left is to rigorously establish the relationship
between “almost all” and generic. The most technical statements are handled in
Appendix A. Recall that two measures are _mutually absolutely continuous_ if
they have the same null sets.

######  Lemma 3.10.

Let $G$ be a graph with $\operatorname{mlt}(G)=d+1$. Then:

  1. (a)

there is a generic framework $(G,p)$ in $\mathbb{R}^{d-1}$ with a nonzero PSD
equilibrium stress, and

  2. (b)

no generic framework $(G,p)$ in $\mathbb{R}^{d}$ has a nonzero PSD equilibrium
stress.

###### Proof.

Let $n$ be the number of vertices of $G$. Let $D$ be an $n\times d$ data
matrix whose columns are i.i.d. samples from a distribution whose probability
measure $\mu$ is mutually absolutely continuous with respect to the Lebesgue
measure. Let $q$ denote the configuration of $n$ points in $\mathbb{R}^{d}$
given by the rows of $D$. Since $\operatorname{mlt}(G)=d+1$, the Gram MLT
optimization problem for $(G,q)$ is unbounded with positive probability. Let
$X$ denote the set of vector configurations of $n$ points in $\mathbb{R}^{d}$
for which the Gram MLT optimization problem is unbounded. Then $X$ is semi-
algebraic and not $\mu$-null, so Lemma A.4 implies that $X$ contains a generic
vector configuration, which we continue to call $q$. By Lemma 3.9, there is a
non-zero PSD linear equilibrium stress matrix $\Omega$ for $q$. Since $q$ is
generic, it is flattenable. By Lemma 3.6, the $(d-1)$-dimensional framework
$(G,p)$ arising from flattening $q$ has an equilibrium stress matrix with the
same signature as $\Omega$, so this matrix must also be PSD and non-zero.
Finally, Lemma A.5 implies that $p$ is generic. Hence we have constructed a
generic $d-1$-dimensional framework $(G,p)$ with a non-zero PSD equilibrium
stress.

Let $W$ denote the set of configurations $w$ of $n$ points in
$\mathbb{R}^{d+1}$ for which the Gram MLT optimization problem $(G,w)$ is
bounded. Since $\operatorname{mlt}(G)=d+1$, the complement of $W$ is
$\mu$-null. Let $(G,p)$ be a generic framework in $\mathbb{R}^{d}$. Scaling
the vectors of $\hat{p}$ by generic weights gives, via Lemma A.5, a generic
configuration $w$ in $\mathbb{R}^{d+1}$. Since $W$ is semi-algebraic and $w$
is generic, Lemma A.4 implies $w\in W$. By Lemma 3.9, there is no non-zero PSD
linear equilibrium stress for $(G,w)$. By Lemma 3.6, there is no non-zero PSD
equilibrium stress for $(G,p)$. ∎

######  Lemma 3.11.

Let $G$ be a graph with $n$ vertices and suppose that $d$ is the smallest
dimension so that no generic $d$-dimensional framework $(G,p)$ has a non-zero
PSD equilibrium stress. Then the MLT of $G$ is $d+1$.

###### Proof.

By assumption, there must be a generic $(d-1)$-dimensional framework with a
non-zero PSD equilibrium stress, which we will call $(G,p)$. By scaling the
vectors of $\hat{p}$ by generic numbers $s_{i}$, we obtain, by Lemma A.5, a
generic vector configuration $q$ in dimension $d$. By Lemma 3.6, there must be
a non-zero PSD linear equilibrium stress for $q$. Hence, by Lemmas 3.9 and
A.4, the set of configurations for which the Gram MLT optimization problem is
unbounded must be non-null. We conclude that $\operatorname{mlt}(G)>d$.

Now we take a generic vector configuration $q$ in dimension $d+1$. As noted
above, by genericity, $q$ is flattenable, and the flattened $d$-dimensional
point configuration $p$ is also generic by Lemma A.5. By Lemma 3.6, since
$(G,p)$ does not have a non-zero PSD equilibrium stress, there is not a non-
zero PSD linear equilibrium stress for $q$. Hence, for every generic vector
configuration $q$ in dimension $d+1$, the Gram MLT optimization problem is
bounded by Lemma 3.9. Since the set of all such vector configurations is semi-
algebraic and contains all the generic points, it must have full measure by
Lemma A.4. This implies that $\operatorname{mlt}(G)\leq d+1$. ∎

The existence of a generic framework in dimension $d-1$ with a non-zero PSD
equilibrium stress implies that the Gram MLT optimization problem is unbounded
with positive probability, for any way of sampling data points that is
continuous with respect to Lebesgue measure. However, we don’t have a lower
bound on this failure probability. Any general lower bound will be quite bad,
since Buhl [12] showed that, for an $n$ cycle, if the datapoints are sampled
uniformly from the unit interval, the MLE exists after $2$ sample points with
probability $1-2n/n!$, even though the MLT of a cycle is $3$.

###  3.4 The geometric picture: lifting

Theorem 1.15, while precise, and as we will see, convenient for deriving
bounds on the MLT of a graph, is quite technical. There is an underlying
geometric idea, that we now explain.

######  Definition 3.12.

Let $G$ have $n$ vertices. Let $(G,p)$ be a $d$-dimensional framework. We say
that $(G,p)$ is _liftable_ if there is an equivalent $n-1$ dimensional
framework $(G,\tilde{p})$ with full affine span.

The following Lemma is due to Alfakih [2]. For completeness, we provide a
proof in Appendix B that uses convex geometry ideas from [28].

######  Lemma 3.13 ([2]).

A $d$-dimensional framework $(G,p)$ is liftable if and only if it does not
have a non-zero PSD equilibrium stress.

Theorem 1.16 is immediate from Theorem 1.15 and Lemma 3.13.

###  3.5 Remarks

To close a circle of ideas, we note that much of the literature on the MLT,
including [5, 8, 30, 58] does not work directly with the MLT optimization
problem. Instead, the starting point is the following matrix completion
problem.

######  Definition 3.14.

Let $G$ be a graph with $n$ vertices and $S$ an $n\times n$ PSD matrix of rank
$d+1$. The _MLT matrix completion problem for $(G,S)$_ is to find an $n\times
n$ positive definite matrix $A$ that has the same diagonal entries as $A$ and
the same off diagonal entries corresponding to edges of $G$.

Dempster [22] showed that the MLT optmization problem is bounded if and only
if the MLT matrix completion problem is feasible.999One can also derive
Dempster’s result via duality in convex programming, see e.g. [5]. A less
direct path to our results is to relate the MLT matrix completion for $G$
problem to liftability of “coned” frameworks $(v_{0}*G,p)$ [17, 60] in one
dimension higher that have a new vertex $v_{0}$ connected to all the others.
The proof of Theorem 2.7 in Appendix D uses this technique.

Finally, we note that we could have allowed the vector configurations in our
optimization problems to satisfy a condition strictly weaker than
flattenability. In particular, it would have been enough to only require that
the Gram matrix $Q^{T}Q$ have _some_ factorization that is flattenable, which
happens so long as none of the vectors in $q$ are zero. At the level of
frameworks, changing factorizations corresponds to projective transformations.
We elected to use the stronger condition to keep the proofs simpler, and in
particular, to avoid having to define and work with generic low-rank PSD
matrices.

##  4 MLT bounds from global rigidity

We can use the results of the previous section along with some facts about
global rigidity to get improved bounds for the MLT and compute it exactly for
some interesting families. The main technical tool of this section relates
generic global rigidity to PSD equilibrium stresses.

######  Theorem 4.1 ([19]).

Let $G$ be a graph with $n\geq d+2$ vertices and $d$ a dimension. If $G$
globally $d$-rigid, then there is a generic framework $(G,p)$ with a PSD
equilibrium stress of rank $n-d-1$.

We also need a straightforward lemma.

######  Lemma 4.2.

Let $G$ be a graph and $H$ a subgraph of $G$. Then
$\operatorname{mlt}(H)\leq\operatorname{mlt}(G)$.

###  4.1 Lower bounds

The main results of this section are new lower bounds on the MLT of a graph
arising from global rigidity in terms of the global rigidity number (Def.
1.17.)

###### Proof of Theorem 1.18.

Suppose that $G$ is globally $d$-rigid. By Theorem 4.1, there is a generic
framework $(G,p)$ with a non-zero PSD equilibrium stress. By Theorem 1.15,
$\operatorname{mlt}(G)>d+1$. Taking $d$ as large as possible for $G$ to remain
globally $d$-rigid we get $\operatorname{mlt}(G)>\operatorname{grn}(G)+1$. The
same argument works for any subgraph $H$ of $G$, so Lemma 4.2 implies that
$\operatorname{mlt}(G)\geq\operatorname{mlt}(H)>\operatorname{grn}(H)+1$.
Maximizing the right-hand side over $H$ we get
$\operatorname{mlt}(G)>\operatorname{grn}^{*}(G)+1.$ Since $G$ is a subgraph
of itself, plainly $\operatorname{grn}^{*}(G)\geq\operatorname{grn}(G)$. ∎

We can efficiently compute $\operatorname{grn}(G)$ [29], but we do not know
the complexity of computing $\operatorname{grn}^{*}(G)$. A related graph
parameter, which may be more computationally tractable is the local rigidity
analogue.

######  Definition 4.3.

Let $G$ be a graph with $n$ vertices. The _rigidity number_
$\operatorname{lrn}(G)$ is the largest $d$ so that $G$ is $d$-rigid and has at
least $d+1$ vertices. The _subgraph rigidity number_
$\operatorname{lrn}^{*}(G)$ is the largest $d$ so that $G$ has a subgraph $H$
on at least $d+1$ vertices that is $d$-rigid.

######  Theorem 4.4.

Let $G$ be a graph. Then
$\operatorname{lrn}(G)+1\leq\operatorname{lrn}^{*}(G)+1\leq\operatorname{mlt}(G)$.

The proof needs a result of Jordán.

######  Lemma 4.5 ([35]).

Let $G$ be a graph that is $(d+1)$-rigid. Then $G$ is globally $d$-rigid.

###### Proof of Theorem 4.4.

By Lemma 4.5 one has
$\operatorname{lrn}^{*}(G)\leq\operatorname{grn}^{*}(G)+1$. Theorem 1.18 then
implies that $\operatorname{lrn}^{*}(G)+1\leq\operatorname{mlt}(G)$. Plainly
$\operatorname{lrn}(G)\leq\operatorname{lrn}^{*}(G)$, giving the last
inequality. ∎

Theorem 4.4 is strictly weaker than Theorem 1.18. For example, for every
$n\geq 4$ there are globally rigid graphs in dimension $2$ that have $2n-2$
edges [6, 15], but if $n>4$ then $2n-2<3n-6$, so these graphs cannot be
$3$-rigid.

The rigidity number of a graph is also easy to compute [4]. We do not know the
complexity of computing $\operatorname{lrn}^{*}(G)$, but, since local rigidity
is matroidal in nature, tools from submodular optimization may apply.

###  4.2 Combined bounds and examples

Combining what we know so far gives the following.

######  Theorem 4.6.

For any graph $G$, the following inequalities hold

  1. (a)

$\omega(G)\leq\operatorname{lrn}^{*}(G)+1\leq\operatorname{grn}^{*}(G)+2\leq\operatorname{mlt}(G)\leq\operatorname{gcr}(G)\leq\tau(G)+1$,
and

  2. (b)

$\operatorname{lrn}(G)+1\leq\operatorname{grn}(G)+2\leq\operatorname{grn}^{*}(G)+2$.

######  Corollary 4.7.

If $G$ is both globally $d$-rigid and $(d+1)$-independent, then
$\operatorname{mlt}(G)=d+2$.

We now exhibit new two infinite families of graphs $G$ for which the
inequalities
$\operatorname{grn}(G)+2\leq\operatorname{grn}^{*}(G)+2\leq\operatorname{mlt}(G)\leq\operatorname{gcr}(G)$
are tight. By applying Lemma 4.5 and Corollary 4.7, we obtain our first
infinite family of graphs, which are the higher dimensional analogue of trees.

######  Corollary 4.8.

If $G$ is minimally $d$-rigid, then
$\operatorname{mlt}(G)=\operatorname{gcr}(G)=d+1$.

Our next example is, in essence, an extension of the cycle graphs to higher
dimensions.

######  Definition 4.9.

$G$ is a _$d$ -circuit_ if it is not $d$-independent, but every proper
subgraph is.

######  Corollary 4.10.

Let $G$ be a $d$-circuit. Then $\operatorname{gcr}(G)=d+2$. If, furthermore,
$G$ is globally $d$-rigid, then $\operatorname{mlt}(G)=d+2$ also.

###### Proof.

Whiteley [60] proved that $G$ is $d$-independent if and only if the coned
graph $v_{0}*G$, that adds a new vertex $v_{0}$ connected to every other
vertex, is $(d+1)$-independent. Since $G$ is a $d$-circuit, for any vertex
$v$, $G-v$ must be $d$-independent. Hence, $v_{0}*(G-v)$ is
$(d+1)$-independent by Whiteley’s result. Since $G$ is isomorphic to a
subgraph of $v_{0}*(G-v)$, it is also $(d+1)$-independent. The claim now
follows from Corollary 4.7. ∎

##  5 Complete bipartite graphs

To test the upper bound from Theorem 1.5 and the lower bound from Theorem 1.3,
Blekherman and Sinn [8] considered the case of complete bipartite graphs. They
were able to compute the MLT and generic completion ranks exactly, obtaining a
number of strong results, including the first examples of graphs $G$ with
$\operatorname{mlt}(G)<\operatorname{gcr}(G)$.

Since, equilibrium stresses of complete bipartite graphs are very well
understood [10, 16], we have an alternative path to the results from [8]. We
require the two following results on the rigidity theory of bipartite graphs.

######  Lemma 5.1 ([20]).

Fix a $d\in\mathbb{N}$ and let $m,n\geq d+1$. If $m+n\geq\binom{d+2}{2}+1$
then $K_{m,n}$ is globally rigid in dimension $d$.

Given a finite subset $S$ of a vector space, let $D(S)$ denote the linear
space of affine dependencies among $S$ and let $S^{2}$ be the image of $S$
under the _Veronese map_ $x\mapsto xx^{T}$. The following theorem collects
what we need from Bolker and Roth’s classic paper [10].

######  Theorem 5.2.

Let $m,n,d\in\mathbb{N}$ and let $(K_{m,n},p)$ be a $d$-dimensional framework.
Let $A,B\subseteq\mathbb{R}^{d}$ denote the images under $p$ of the partite
sets of $K_{m,n}$. Then the linear space of equilibrium stresses of
$(K_{m,n},p)$ has dimension

$\dim(D(A))\dim(D(B))+\dim(D((A\cup B)^{2})).$

Moreover, if $p$ is generic and $m+n\leq\binom{d+2}{2}$, then every
equilibrium stress matrix has zeros along its diagonal.

###### Proof.

The first claim follows from [10, Theorem 1]. The second claim follows from
[10, Lemma 5] and the fact that any set of $\binom{d+2}{2}$ generic symmetric
matrices of rank $1$ is a basis of the space of symmetric $(d+1)\times(d+1)$
matrices. ∎

######  Theorem 5.3 ([8]).

Let $d,m,n\in\mathbb{N}$ with $m,n\geq d+2$. If $m+n\leq\binom{d+2}{2}$, then
$\operatorname{mlt}(K_{m,n})\leq d+1$ and $\operatorname{gcr}(K_{m,n})\geq
d+2$.

###### Proof.

Let $(K_{m,n},p)$ be a generic $d$-dimensional framework. Since
$m+n\leq\binom{d+2}{2}$, Theorem 5.2 implies that every stress matrix has
zeros along its diagonal and is therefore indefinite. Theorem 1.15 then
implies that $\operatorname{mlt}(K_{m,n})\leq d+1$. On the other hand, Theorem
5.2 implies that the space of stresses has dimension at least
$\dim(D(A))\dim(D(B))$, which is positive as $m,n\geq d+2$. The existence of
an equilibrium stress implies that $\operatorname{gcr}(K_{m,n})\geq d+2$. ∎

At this point Theorem 1.6 follows quickly.

###### Proof of Theorem 1.6.

Theorem 5.2 implies that $K_{m,m}$, for $m>2$, is $(m-1)$-independent but not
$(m-2)$-independent. Hence $\operatorname{gcr}(K_{m,m})=m$. By Lemma 5.1, for
$n>2$, the global rigidity number of $K_{m,m}$ is the maximum $d$ so that
$2m\geq\binom{d+2}{2}+1$. For this $d$, Theorem 1.18 implies that
$\operatorname{mlt}(K_{m,m})\geq d+2$. For any larger $d^{\prime}$, we have
$2m\leq\binom{d^{\prime}+2}{2}$. Theorem 5.3 then tells us that
$\operatorname{mlt}(K_{m,m})\leq(d+1)+1=d+2$. Combining both bounds, we
conclude that the MLT of $K_{m,m}$ is the largest $D$ so that
$2m>\binom{D+1}{2}$ as desired. ∎

##  6 A gluing construction

In this section we prove some specialized results about giving lower bounds on
MLT of graphs. We do this by constructing PSD equilibrium stresses on generic
frameworks of a graph obtained by gluing together smaller frameworks that each
have a PSD equilibrium stress. We will need the following construction from
rigidity theory.

######  Definition 6.1.

Let $G$ be a graph with $n$ vertices and $m$ edges. The _rigidity matrix_
$R(G,p)$ of a $d$-dimensional framework $(G,p)$ is the $m\times dn$ matrix
whose rows are indexed by the edges of $G$, columns indexed by the coordinates
of $p(1),\dots,p(n)$, where the entry corresponding to edge $e$ and $p(v)_{i}$
is $p(v)_{i}-p(u)_{i}$ if $e=vu$, and $0$ if $v$ is not incident to $e$.

Given a $d$-dimensional framework $(G,p)$ on a graph $G$ with $n$ vertices,
$R(G,p)$ is the Jacobian of the map sending $n$ points in $\mathbb{R}^{d}$ to
the pairwise squared distances corresponding to the edges of $G$, evaluated at
$p$. Equilibrium stresses of $R(G,p)$ are the elements of the left kernel of
$R(G,p)$.

######  Definition 6.2.

A graph $G$ is a _$k$ -sum_ of two induced subgraphs $G_{1}$ and $G_{2}$ each
with at least $k+1$ vertices if $G$ is the union of $G_{1}$ and $G_{2}$ and
$G_{1}\cap G_{2}$ is isomorphic to $K_{k}$.

The following result on equilibrium stresses of frameworks on $k$-sums is
standard.

######  Lemma 6.3.

Let $1\leq k\leq d+1$ be integers and $G$ a $k$-sum of subgraphs $G_{1}$ and
$G_{2}$. Let $(G,p)$ be a $d$-dimensional framework with the vertices of
$G_{1}\cap G_{2}$ affinely independent. Let $S$ be the space of equilibrium
stresses of $(G,p)$ and $S_{i}$ the space of equilibrium stresses of $(G,p)$
supported on the edges of $G_{i}$. Then $S=S_{1}\oplus S_{2}$.

###### Proof.

Let $K=G_{1}\cap G_{2}$. First observe that any equilibrium stress $\omega\in
S_{1}\cap S_{2}$ must be supported by the edges of $K$ and so is an
equilibrium stress of $(K,p|_{K})$. Since $K$ has at most $d+1$ vertices and
is in general affine position, $(K,p|_{K})$ supports only the zero equilibrium
stress. Hence $S_{1}+S_{2}=S_{1}\oplus S_{2}$.

Denote $R_{i}=R(G_{i},p|_{G_{i}})$. The row spans of $R_{1}$ and $R_{2}$ are
naturally included in the row span of $R(G,p)$. Both of these spans include
$R(K,p|_{K})$. By general position of the vertices corresponding to $K$, this
latter space has dimension $\binom{k}{2}$. So by the interpretation of $S$ and
the $S_{i}$ as cokernels of the rigidity matrix and rank-nullity, we have

$\displaystyle\dim(S)$ $\displaystyle=m-\operatorname{rank}R(p)$
$\displaystyle=m_{1}+m_{2}-\binom{k}{2}-\operatorname{rank}R(p)$
$\displaystyle=m_{1}+m_{2}-\binom{k}{2}-\operatorname{rank}R_{1}-\operatorname{rank}R_{2}+\binom{k}{2}$
$\displaystyle=m_{1}-\operatorname{rank}R_{1}+m_{2}-\operatorname{rank}R_{2}$
$\displaystyle=\dim(S_{1}\oplus S_{2})$

and so we can conclude $S=S_{1}+S_{2}=S_{1}\oplus S_{2}$. ∎

A framework $(G,p)$ is _regular_ if its rigidity matrix has maximum rank over
all frameworks $(G,q)$. Regularity is preserved under non-singular projective
transforms applied to $p$. The converse of the following corollary also true,
but we do not need it.

######  Corollary 6.4.

Let $1\leq k\leq d+1$ and $G$ be a $k$-sum of $G_{1}$ and $G_{2}$. Let $(G,p)$
be a $d$-dimensional framework. If $(G_{1},p|_{V(G_{1})})$ and
$(G_{2},p|_{V(G_{2})})$ are regular then $(G,p)$ is regular.

###### Proof.

Let $G_{i}$ have $n_{i}$ vertices and $m_{i}$ edges. Assume that $p$ is such
that $(G_{1},p|_{V(G_{1})})$ and $(G_{2},p|_{V(G_{2})})$ are both regular. Let
$r_{i}$ be the rank of the rigidity matrix of each of these frameworks and
$s_{i}$ the dimension of the space of equilibrium stresses. Observing that $G$
has $n_{1}+n_{2}-k$ vertices and $m_{1}+m_{2}-\binom{k}{2}$ edges, we can see
that the maximum possible rank of the rigidity matrix for $(G,p)$ is
$r_{1}+r_{2}-\binom{k}{2}$. Since $K=G_{1}\cap G_{2}$ is complete and has at
most $d+1$ vertices in dimension $d$, regularity of $(G_{1},p|_{V(G_{1})})$
and $(G_{2},p|_{V(G_{2})})$ implies that the vertices of $K$ are affinely
independent. Otherwise there is an equilibrium stress supported only on $K$
that is not present in all frameworks. Hence, we may apply Lemma 6.3 to
$(G,p)$ to conclude that its space of equilibrium stresses is the direct sum
of equilibrium stresses supported on $G_{1}$ and $G_{2}$ respectively. The
dimension of the space of equilibrium stresses of $(G,p)$ is then
$s_{1}+s_{2}$. Then $(G,p)$ is regular since the rank of its rigidity matrix
is

$m_{1}+m_{2}-\binom{k}{2}-s_{1}-s_{2}=m_{1}+m_{2}-\binom{k}{2}-(m_{1}-r_{1})-(m_{2}-r_{2})=r_{1}+r_{2}-\binom{k}{2}.\qed$

We also have some control of the signs of stress coefficients in PSD
equilibrium stresses. The following is from [18, Lemma 4.9] and the discussion
around it.

######  Lemma 6.5.

Let $(G,p)$ be a $d$-dimensional framework and $\omega$ a PSD equilibrium
stress of $(G,p)$ and $ij$ and edge of $G$ so that $\omega_{ij}>0$. Then there
is a non-singular projective transformation $T$ on $\mathbb{R}^{d}$ so that
$(G,T(p))$ has a PSD equilibrium stress $\psi$ so that $\psi_{ij}<0$.

We have things in place for the main result of this section. Given a graph $G$
with edge $ij$, we let $G-ij$ denote the graph obtained from $G$ by deleting
the edge $ij$.

######  Lemma 6.6.

Let $1\leq k\leq d$ and $G$ be a $k$-sum of subgraphs $G_{1}$ and $G_{2}$ and
$ij$ and edge of $G_{1}\cap G_{2}$. Suppose that there are generic
$d$-dimensional frameworks $(G_{1},p^{1})$ and $(G_{2},p^{2})$ that,
respectively, support non-zero PSD equilibrium stresses $\omega^{1}$ and
$\omega^{2}$, such that $\omega^{k}_{ij}\neq 0$ for $k=1,2$. Let
$G^{\prime}=G-ij$. Then there is a generic $d$-dimensional framework
$(G^{\prime},p)$ that supports a non-zero PSD equilibrium stress.

###### Proof.

First assume that $\omega^{1}_{ij}<0$ and $\omega^{2}_{ij}>0$. Since
$G_{1}\cap G_{2}$ has at most $d$ vertices, any affinely independent framework
on $G_{1}\cap G_{2}$ cannot support an equilibrium stress. Hence, both
$\omega^{1}$ and $\omega^{2}$ have some support outside of $G_{1}\cap G_{2}$.
We create a framework $(G,p^{0})$ from the frameworks $(G_{1},p^{1})$ and
$(G_{2},p^{2})$ as follows. Pick a non-singular affine map $T$ sending the
vertices of $G_{1}\cap G_{2}$ in $(G_{1},p^{1})$ to the corresponding vertices
in $(G_{2},p^{2})$ and apply it to $p^{1}$. The defines a framework
$(G,p^{0})$.

By Corollary 6.4 and the genericity of $(G_{i},p^{i})$, the framework
$(G,p^{0})$ is regular. Since equilibrium stresses are preserved under affine
maps, $\omega^{1}$ and $\omega^{2}$ are both equilibrium stresses of
$(G,p^{0})$. Our assumptions about the signs imply that some positive linear
combination $\omega$ of $\omega^{1}$ and $\omega^{2}$ has vanishing
coefficient on the edge $ij$. Because the $\omega^{i}$ have some necessarily
disjoint support, $\omega$ is non-zero. Since a positive combination of PSD
equilibrium stresses is PSD, we conclude that $\omega$ is. Since $\omega$ is
not supported on $ij$, it is also an equilibrium stress of
$(G^{\prime},p^{0})$. Potentially, $(G^{\prime},p^{0})$ is not generic, but
since it is regular, a small perturbation $(G,p)$ that is generic will have an
equilibrium stress close to $\omega$ that is also PSD.

If $\omega^{1}_{ij}>0$, we reduce to the previous case by applying a
projective transformation, as in Lemma 6.5. The argument is then the same as
before, since we only used that the $(G_{i},p^{i})$ are generic to make them
regular. Regularity is preserved by projective transformations. ∎

###  6.1 Remarks

A natural question is whether the lower bound in Theorem 1.18 is tight. The
results of this section show that it is not. By Lemma 6.6, if we let $G$ be
the $2$-sum of two copies of $K_{d+2}$ over an edge $ij$, and $G^{\prime}$ the
graph $G-ij$, there is a generic framework $(G^{\prime},p)$ in dimension $d$
with a non-zero PSD equilibrium stress. Theorem 1.15, then implies that
$\operatorname{mlt}(G^{\prime})\geq d+2$. On the other hand, since every
induced subgraph of $G^{\prime}$ is independent in dimension $d$,
$\operatorname{grn}^{*}(G^{\prime})\leq d-1$. Hence,
$\operatorname{grn}^{*}(G^{\prime})+2<\operatorname{mlt}(G^{\prime})$.

If we ask, in addition that $G$ is $(d+1)$-connected, we do not know an
example where the lower bound in Theorem 1.18 is not tight.

##  7 Equality of small MLT and GCR

In this section, we prove Theorem 1.19, which rests on the rich combinatorial
theory of 2-rigidity of graphs (see e.g. [42] for an overview). The
cornerstone of this theory is Theorem 7.2, the Laman–Pollaczek-Geiringer
theorem. We begin with the necessary definitions.

######  Definition 7.1.

A graph $G$ with $n$ vertices is $(2,3)$-sparse if, for all subgraphs with
$n^{\prime}$ vertices and $m^{\prime}>0$ edges, $m^{\prime}\leq
2n^{\prime}-3$. If $G$ is $(2,3)$-sparse and, in addition has $2n-3$ edges, it
is called a _Laman graph_. A graph that is not $(2,3)$-sparse, but becomes so
after removing any edge is called a _Laman circuit_.

######  Theorem 7.2 ([41, 50]).

A graph $G$ is $2$-independent if and only if $G$ is $(2,3)$-sparse.

Via Theorem 1.11, Theorem 7.2 immediately gives us a combinatorial
characterization of the graphs with $\operatorname{gcr}(G)=3$; these are the
$(2,3)$-sparse graphs that contain a cycle. As we will see in Proposition 7.4,
this also characterizes graphs with $\operatorname{mlt}(G)=3$. In order to
prove this, we need the following lemma which makes crucial use of Berg and
Jordan’s [6] combinatorial characterization of global rigidity in two
dimensions.

######  Lemma 7.3.

Let $G$ be a Laman circuit. Then there are generic $2$-dimensional frameworks
$(G,p)$ satisfying a non-zero PSD equilibrium stress.

###### Proof.

If $G$ is $3$-connected, a result of Berg and Jordán [6] implies that $G$ is
globally rigid. The desired statement then follows from Theorem 4.1. If $G$ is
not $3$-connected, we can find a $2$-separation $\\{x,y\\}\subseteq V(G)$ in
$G$. A counting argument [6, Lemma 2.4, inter alia] implies that $xy$ is not
an edge of $G$ and that $G\cup\\{xy\\}$ is a $2$-sum of smaller Laman circuits
$G_{1}$ and $G_{2}$. By induction, we may assume that there are generic
$2$-dimensional frameworks $(G_{1},p^{1})$ and $(G_{2},p^{2})$ that each
support a PSD equilibrium stress $\omega^{1}$ and $\omega^{2}$. Since $G_{1}$
and $G_{2}$ are circuits, the supports of $\omega^{1}$ and $\omega^{2}$
include the edge $xy$. By Lemma 6.6, there is then a generic framework $(G,p)$
with a non-zero PSD equilibrium stress. ∎

######  Proposition 7.4.

Given a graph $G$, the following are equivalent:

  1. (a)

$G$ is $(2,3)$-sparse and contains a cycle,

  2. (b)

$\operatorname{gcr}(G)=3$, and

  3. (c)

$\operatorname{mlt}(G)=3$.

###### Proof.

Theorems 7.2 and 1.11 imply that $\operatorname{gcr}(G)=3$ if and only if $G$
is $(2,3)$-sparse and contains a cycle. Now assume $\operatorname{gcr}(G)=3$.
Since cycles are globally $1$-rigid, any graph $G$ with a cycle has
$\operatorname{grn}^{*}(G)\geq 1$, so $\operatorname{mlt}(G)\geq 3$ by Theorem
1.18. On other other hand, if a graph $G$ is $(2,3)$-sparse then
$\operatorname{gcr}(G)\leq 3$ and so $\operatorname{mlt}(G)\leq 3$ follows
from Theorem 1.5.

If $\operatorname{gcr}(G)\leq 2$ or $\operatorname{mlt}(G)\leq 2$, then $G$
cannot have a cycle. So assume $\operatorname{gcr}(G)\geq 4$. Theorems 7.2 and
1.11 now imply that $G$ contains a Laman circuit $H$ as a subgraph. By Lemma
7.3, $H$ has a generic $2$-dimensional framework $(H,p)$ with non-zero PSD
equilibrium stress. Theorem 1.15 implies $\operatorname{mlt}(H)\geq 4$ and
therefore Lemma 4.2 implies $\operatorname{mlt}(G)\geq 4$. ∎

We are now ready to prove the main result of this section.

###### Proof of Theorem 1.19.

As noted in [30], $\operatorname{mlt}(G)=1$ if and only if $G$ has no edges
and $\operatorname{mlt}(G)=2$ if and only if $G$ has no cycles. In both cases,
it is easy to see that $\operatorname{gcr}(G)=\operatorname{mlt}(G)$. If
$\operatorname{mlt}(G)=3$ or $\operatorname{gcr}(G)=3$, then
$\operatorname{mlt}(G)=\operatorname{gcr}(G)$ follows from Proposition 7.4. If
$\operatorname{gcr}(G)=4$, then Theorem 7.2 and Lemma 7.3 together imply that
$\operatorname{mlt}(G)\geq 4$ and equality follows from Theorem 1.5. ∎

######  Remark 7.5.

Theorem 1.19 is best possible in the sense that if $a\geq 4$ and $b\geq 5$,
then there exist graphs $G,H$ such that
$\operatorname{mlt}(G)=a<\operatorname{gcr}(G)$ and
$\operatorname{mlt}(H)<b=\operatorname{gcr}(H)$. In particular, let
$n=\left\lfloor\frac{1}{2}\binom{a+1}{2}\right\rfloor$, and let $D$ be the
smallest $k$ such that $\binom{k+1}{2}\geq 2b$. Then, Theorem 1.6 implies
$\operatorname{mlt}(K_{n,n})=a<n=\operatorname{gcr}(K_{n,n})$ and that
$\operatorname{gcr}(K_{b,b})=b>D=\operatorname{mlt}(K_{b,b})$.

##  8 Weak maximum likelihood threshold

This section includes connections between the _weak_ maximum likelihood
threshold of a graph, and two areas of classical combinatorics: partially
ordered sets, and graph dimension (i.e. the minimum dimension in which a graph
can be realized as a unit-distance graph).

######  Definition 8.1.

The _weak maximum likelihood threshold_ of a graph $G$, denoted
$\operatorname{wmlt}(G)$ is the smallest number of samples101010Again, we are
assuming that the samples are i.i.d. from a distribution whose probability
measure is mutually absolutely continuous with respect to Lebesgue measure.
required for the MLE of the Gaussian graphical model associated with $G$ to
exist with positive probability.

The definition of $\operatorname{wmlt}(G)$ is the same as that of
$\operatorname{mlt}(G)$, but with the phrase “almost surely” swapped out for
“with positive probability.” Arguments along the lines of Section 3 then yield
the analogue of Theorem 1.16. Since the proof is very similar, we skip it.

######  Proposition 8.2.

Let $G$ be a graph with $n$ vertices. The WMLT of $G$ is $d+1$ if and only if
$d$ is the smallest dimension such that some generic $d$-dimensional framework
$(G,p)$ is liftable.

The following implies that we can ignore genericity of our witness (cf. [30,
Definition 5.1]).

######  Proposition 8.3.

Let $d\in\mathbb{N}$ be a dimension and $G$ be a graph with $n\geq d+1$
vertices. If there is any liftable $d$-dimensional framework $(G,p)$ then
there is a generic liftable $d$-dimensional framework. In particular,
$\operatorname{wmlt}(G)\leq d+1$.

###### Proof.

Let $(G,p)$ be a liftable $d$-dimensional framework. By Lemma 3.13, $(G,p)$
does not have a non-zero PSD equilibrium stress. By lower semi-coniuity of the
rank of the rigidity matrix, there is a nbd $U$ of $p$ so that if $q\in U$,
the space of equilibrium stresses of $(G,q)$ has dimension at most that of
$(G,p)$. Hence any equilibrium stress of $(G,q)$ is a small perturbation of a
stress of $(G,p)$. For sufficiently small perturbations, signature is
preserved, so some neighborhood of $p$ consists of only frameworks without
non-zero PSD equilibrium stresses. This neighborhood contains a generic
framework. The second statement follows from Proposition 8.2. ∎

###  8.1 Existing bounds on the WMLT

The weak maximum likelihood threshold of a graph is one if and only if it has
no edges. Examples of graphs for which MLT = WMLT = $d+1$ are the _$d$
-laterations_; i.e., graphs formed from $K_{d+1}$ by a sequence of
$d$-dimensional 0-extensions. Other than this, very little is known. Gross and
Sullivant [30] showed that $\operatorname{wmlt}(G)$ is at most the chromatic
number of $G$. Buhl [12] characterized the weak maximum likelihood thresholds
of cycles, showing that $\operatorname{wmlt}(G)=3$ if $G$ is a three-cycle,
and $\operatorname{wmlt}(G)=2$ when $G$ is a cycle of length four or greater.

######  Definition 8.4.

Given a directed graph, a cycle in the underlying undirected graph is
_stretched_ if it is of the form $v_{1}\rightarrow
v_{2}\rightarrow\dots\rightarrow v_{k}\leftarrow v_{1}$. Given $(G,p)$ is a
framework in $\mathbb{R}^{1}$ with no edges of length zero, a cycle in $G$ is
_stretched_ if the corresponding cycle is stretched in the orientation of $G$
obtained by directing each edge $i$ $j$ towards $j$ if $p(j)>p(i)$ and
otherwise toward $i$.

The following proposition can be seen as the rigidity-theoretic version of
[12, Theorem 4.3].

######  Proposition 8.5.

Let $G$ be a cycle and let $(G,p)$ be a generic framework in $\mathbb{R}^{1}$.
Then $(G,p)$ has a non-zero PSD equilibrium stress if and only if it is a
stretched cycle.

The proposition is a special case of a more general statement due Kapovich and
Millson [36] which we discuss in Appendix C.

Proposition 8.5 immediately implies the following result of Gross and
Sullivant.

######  Corollary 8.6 ([30, Corollary 5.4]).

If $\operatorname{wmlt}(G)=2$, then $G$ has an acyclic orientation with no
stretched cycles.

In [30], the property of having an acyclic orientation with no stretched
cycles is called _Buhl’s cycle condition_.

###  8.2 A conjecture and a connection

Based on experimental evidence, we believe that the converse to Corollary 8.6
is true.

######  Conjecture 8.7.

If $G$ has at least one edge and an acyclic orientation with no stretched
cycles, then $\operatorname{wmlt}(G)=2$.

Directed acyclic graphs with no stretched cycles are well-studied objects in
combinatorics: they are diagrams of partially ordered sets. It is NP-hard to
determine whether a given undirected graph has an acyclic orientation with no
stretched cycles [11]. Thus Conjecture 8.7 would imply that the decision
problem of whether a given graph has $\operatorname{wmlt}(G)=2$ is NP-hard.
Via the coning construction [60], this would imply that determining weak MLT
is NP-hard in general.

The following definition is due to Erdös, Harary, and Tutte.

######  Definition 8.8 ([25]).

The _dimension_ of a graph $G$, denoted $\dim(G)$, is the minimum $d$ such
that there exists a framework $(G,p)$ in $\mathbb{R}^{d}$ such that
$\|p(i)-p(j)\|=1$ for all edges $ij\in E(G)$.

The _Hadwiger-Nelson problem_ is a longstanding open problem in combinatorics
which asks for the maximum chromatic number of a graph $G$ with $\dim(G)=2$.
See [21] for the most recent progress and a brief account of the history. The
connection to weak maximum likelihood thresholds is given by the following.

######  Proposition 8.9.

Let $G$ be a graph. Then $\operatorname{wmlt}(G)\leq\dim(G)+1$.

###### Proof.

Let $(G,p)$ be a framework in $\mathbb{R}^{\dim(G)}$ so that every edge of $G$
has length $1$. Then $(G,p)$ is liftable. A suitable witness is the framework
$(G,q)$ in $\mathbb{R}^{n-1}$ where the $q(i)$s are the vertices of a suitably
scaled unit simplex. The result now follows from Proposition 8.2. ∎

It is well-known that $\dim(G)+1\leq\chi(G)$. Indeed, if $G$ has chromatic
number $d+1$, then there is a unit-distance embedding of $G$ in dimension $d$
by putting each of the $d+1$ color classes on a distinct vertex of a regular
simplex in dimension $d$. Hence, this result improves the inequality
$\operatorname{wmlt}(G)\leq\chi(G)$ from [30].

##  9 Acknowledgements

This paper arose as part of the Fields Institute Thematic Program on Geometric
constraint systems, framework rigidity, and distance geometry. LT thanks Bill
Jackson for discussions about globally rigid $d$-circuits.

DIB was partially supported by a Mathematical Sciences Postdoctoral Research
Fellowship from the US NSF, grant DMS-1802902. SD was partially supported by
the Austrian Science Fund (FWF): P31888. AN was partially supported by the
Heilbronn Institute for Mathematical Research. SJG was partially supported by
US NSF grant DMS-1564473. MS was partially supported by US NSF grant
DMS-1564480 and US NSF grant DMS-1563234.

##  Appendix A “almost all” vs “generic”

In this appendix, we prove some technical results needed for Theorem 1.15. We
begin with a precise definition of genericity.

######  Definition A.1.

A point $x\in\mathbb{R}^{n}$ is _generic_ if its coordinates are algebraically
independent over $\mathbb{Q}$. If $S\subseteq\mathbb{R}^{n}$ is an irreducible
semi-algebraic set, then a point $x\in S$ is _generic in $S$_ if whenever a
polynomial $f$ with rational coefficients satisfies $f(x)=0$, then $f(y)=0$
for all $y\in S$.

We record some facts about semi-algebraic sets (see, e.g. [9, 56]). Recall
that a _finite boolean combination_ of sets $\\{S_{\alpha}\\}_{\alpha\in J}$
is a set obtained using finitely many unions and intersections of sets in
$\\{S_{\alpha}\\}_{\alpha\in J}$.

######  Lemma A.2.

Let $S$ be an irreducible semi-algebraic set and $X\subseteq S$ semi-
algebraic. Then:

  1. (a)

$X$ is a finite boolean combination of open and closed (standard topology)
subsets of $S$,

  2. (b)

$X$ contains an open subset of $S$ if and only if it has the same dimension as
$S$,

  3. (c)

if $X$ is of lower dimension than $S$, then each $x\in X$ satisfies some
polynomial with coefficients in the field of definition for $X$ that is not
satisfied by some points in $S$, and

  4. (d)

$X$ has finitely many irreducible components.

######  Lemma A.3.

Let $S\subseteq\mathbb{R}^{N}$ be an irreducible semi-algebraic set,
$X\subseteq S$ semi-algebraic, and suppose that $\mu$ is a Borel measure on
$S$ that is mutually absolutely continuous with respect to Lebesgue measure on
$S$. Then $X$ is $\mu$-null if and only if every irreducible component of $X$
is of lower dimension than $S$.

###### Proof.

From Lemma A.2 and the fact that $\mu$ is a Borel measure, we know that each
irreducible component $Y$ of $X$ is measurable. Since $\mu$ is a Borel measure
and Lebesgue measure on $S$ is absolutely continuous with respect to $\mu$, if
$Y$ contains an open subset of $S$, $\mu(Y)>0$. Hence, if $Y$ has the same
dimension as $S$, we must have $\mu(Y)>0$. On the other hand, if $Y$ is of
lower dimension then the (standard topology) closure $\overline{Y}$ is closed
and nowhere dense. Absolute continuity of $\mu$ with respect to Lebesgue
measure then implies that $\mu(Y)\leq\mu(\overline{Y})=0$. Repeating this
argument for each irreducible component of $X$ completes the proof. ∎

To translate between generic statements and measure theoretic ones, we use the
following.

######  Lemma A.4.

Let $S$ be an irreducible semi-algebraic subset of $\mathbb{R}^{N}$ and let
$X$ be a semi-algebraic subset of $S$, with both $S$ and $X$ defined over
$\mathbb{Q}$. Let $\mu$ be a Borel measure on $S$ mutually absolutely
continuous with respect to Lebesgue measure. Then:

  1. (a)

if $X$ is $\mu$-null, then no generic points of $S$ are in $X$,

  2. (b)

if $X$ has full $\mu$-measure, then every generic point of $S$ is in $X$, and

  3. (c)

if neither $X$ nor its complement are $\mu$-null, then some generic points of
$S$ are in $X$ and some are not.

###### Proof.

Suppose, for the moment, that $X$ is irreducible. By Lemma A.3 if $X$ is
$\mu$-null it is of lower dimension than $S$. By Lemma A.2, no point of $X$
can be generic. In general, we repeat the argument for each irreducible
component, which gives (a). Part (b) follows from (a) via complementation.

For (c), Lemma A.3 implies that a $\mu$-non-null semi-algebraic set contains
an open set. Any non-generic point must lie in a nowhere dense algebraic
subset of $S$, so if both $X$ and its complement are $\mu$-non-null both
contain a generic point. ∎

######  Lemma A.5.

Let $v$ be a generic configuration of $n$ vectors in $\mathbb{R}^{d+1}$. Then
$v$ is flattenable, and the flattened configuration $p$ in $\mathbb{R}^{d}$ is
also generic. Conversely, if $p$ is a generic configuration of $n$ points in
$\mathbb{R}^{d}$, then there is a generic vector configuration $v$ in
$\mathbb{R}^{d+1}$ so that $p$ is the flattening of $v$.

###### Proof.

First suppose that $v$ is a generic configuration of $n$ vectors in
$\mathbb{R}^{d+1}$. Letting $t_{i}$ be the last coordinate of $v(i)$, we
notice that if $t_{i}=0$ for any $i$, then $v$ satisfies a non-trivial
polynomial equation and so is non-generic. Hence, $v$ is flattenable. The map
sending a flattenable vector configuration $v$ to its flattening $p$ is
rational and surjective onto configurations of $n$ points in $\mathbb{R}^{d}$.
The result now follows from [29, Lemmas 2.7 and 2.8]. ∎

##  Appendix B Equilibrium stresses and convexity

The goal of this appendix is to give a self-contained proof of Lemma 3.13,
which originally appeared in [2]. We will denote the interior of a set $S$ by
$\operatorname{int}(S)$.

######  Lemma B.1.

Let $K$ be a convex $n$-dimensional set in $\mathbb{R}^{n}$, let $\pi$ be a
rank-$m$ linear projection from $\mathbb{R}^{n}$ to $\mathbb{R}^{m}$, and let
$k:=\pi(K)$ be the $m$-dimensional image. The following are equivalent:

  1. (a)

$\pi^{-1}(x)\cap\operatorname{int}(K)$ is nonempty,

  2. (b)

$x\in\operatorname{int}(k)$, and

  3. (c)

$x$ does not lie on a supporting hyperplane for $k$.

###### Proof.

Equivalence of the latter two conditions follows from the supporting
hyperplane theorem [54, Ch. 8].

If $\pi^{-1}(x)\cap\operatorname{int}(K)$ is nonempty, then there is a point
$X\in\pi^{-1}(x)$ with open neighborhood $N$ satisfying
$N\subseteq\operatorname{int}(K)$. Since $\pi$ is a linear map, it is open
onto its image, which is $\mathbb{R}^{m}$, so $\pi(N)$ is open. Since
$x\in\pi(N)\subseteq k$, it is interior in $k$ (here we used that $K$ is full-
dimensional, so that $\operatorname{int}(K)$ is open and nonempty in
$\mathbb{R}^{n}$).

Now assume $\pi^{-1}(x)\cap\operatorname{int}(K)=\emptyset$. Since
$\pi^{-1}(x)$ is convex, there must be an affine hyperplane $H$ in
$\mathbb{R}^{n}$ weakly separating $\pi^{-1}(x)$ from $\operatorname{int}(K)$.
Since $\pi^{-1}(x)$ is an affine subspace, we have $\pi^{-1}(x)\subseteq H$.
Let $\ell$ be the linear functional and $\alpha$ the real number so that

$H=\\{y\in\mathbb{R}^{N}:\ell(y)=\alpha\\}.$

Since $\pi^{-1}(x)$ is parallel to the kernel of $\pi$, we have that
$\ker\ell\supseteq\ker\pi$. Hence, we have a well-defined linear map
$\overline{\ell}:\mathbb{R}^{m}\cong\mathbb{R}^{n}/\ker\pi\to\mathbb{R}$ given
by

$\overline{\ell}(x^{\prime})=\ell(y^{\prime})\qquad\text{(any
$y^{\prime}\in\pi^{-1}(x^{\prime})$)}.$

Hence, since $H$ supports $K$, the hyperplane
$\\{y\in\mathbb{R}^{m}:\overline{\ell}(y)=\alpha\\}$ supports $k$ at $x$. ∎

###### Proof of Lemma 3.13.

Let $K$ be the PSD cone. Points in $K$ are Gram matrices of $n$-point
configurations in $\mathbb{R}^{n}$; points in the interior correspond to
configurations with $n$-dimensional linear span. Such configurations will have
an $n-1$-dimensional affine span. Fixing a graph $G$ with $m$ edges, $\pi$
will be the map to $\mathbb{R}^{m}$, which measures the squared lengths of the
corresponding framework; i.e. indexing $\mathbb{R}^{m}$ by the edges of $G$,
for each edge $ij$ of $G$, we have

$\pi(X)_{ij}=X_{ii}+X_{jj}-2X_{ij}.$

The image $\pi(K)$ is an $m$-dimensional convex cone
$k\subseteq\mathbb{R}^{m}$. Using Lemma B.1, it now suffices to show that
$\pi(p)$ lies on the boundary of $k$ if and only if $(G,p)$ has a PSD
equilibrium stress.

Given a configuration $q$ of $n$ points in $\mathbb{R}^{n}$, let $q^{l}$
denote the vector $q(1)_{l},\dots,q(n)_{l}$ consisting of the $l^{\rm th}$
coordinate of each point in $q$. Now assume $\pi(p)$ lies on the boundary of
$k$, let $\omega$ be the normal vector of the hyperplane tangent to $k$ at
$\pi(p)$, and let $\Omega$ be the matrix obtained by setting
$\Omega_{ij}=\Omega_{ji}=-\omega_{ij}$ for all edges $ij$ of $G$,
$\Omega_{ii}=\sum_{j}\omega_{ij}$ for $i=1,\dots,n$, and all other entries
zero. This means that for any configuration $q$ of $n$ points in
$\mathbb{R}^{n}$, the following inequality holds, and is moreover an equality
when $q=p$:

$\displaystyle 0\leq\sum_{ij{\rm\ edge\ of\
}G}\omega_{ij}||(q_{i}-q_{j})||^{2}=\sum_{l}(q^{l})^{T}\Omega q^{l}.$ (2)

This implies that $\Omega$ is PSD and that $(p^{l})^{T}\Omega p^{l}=0$ for all
$l$. Together, these imply that $\Omega p^{l}=0$ for each $l$, which is
exactly the condition for $\omega$ to be an equilibrium stress of $p$. Thus
$\omega$ is a PSD equilibrium stress for $p$.

Finally, note that if $\Omega$ is a PSD equilibrium stress of $p$, then the
above arguments can be reversed to show that $\Omega$ defines a supporting
hyperplane of $k$ at $p$. ∎

##  Appendix C the signature of a cycle stress

######  Definition C.1.

Let $C_{n}$ denote the directed cycle on vertex set $\\{1,\dots,n\\}$ with
edges $1\rightarrow 2,2\rightarrow 3,\dots,(n-1)\rightarrow n,n\rightarrow 1$.
A _framework_ $(C_{n},p)$ on $C_{n}$ refers to a framework on the undirected
graph underlying $C_{n}$. In a general position framework $(C_{n},p)$ in
$\mathbb{R}^{1}$, an edge $i\rightarrow(i+1)$ is _forwards_ if $p(i)<p(i+1)$
and _backwards_ otherwise.

Note that every general position framework $(C_{n},p)$ in $\mathbb{R}^{1}$ has
at least one forwards edge and at least one backwards edge. Proposition 8.5 is
a corollary of the following, which classifies the signatures of the stresses
of cycles in $\mathbb{R}^{1}$.

######  Theorem C.2 ([36]).

Let $(C_{n},p)$ be a generic framework in $\mathbb{R}^{1}$ and let $f$ be the
number of forwards edges and $b$ the number of backwards edges. Then, for
every nonzero equilibrium stress matrix $\Omega$ of $(C_{n},p)$, the signature
of $\Omega$ is either $(f-1,2,b-1)$ or $(b-1,2,f-1)$.

It is easy to see from Theorem C.2 that any cycle framework $(C_{n},p)$ with
exactly one backwards edge, or exactly one forwards edge, must be stretched
and vice versa. Since the proof in [36] uses Hodge theory, we provide a
linear-algebraic argument.

######  Lemma C.3.

Let $(G,p)$ be a general position framework in $\mathbb{R}^{1}$ with the edge
$\\{1,n\\}$, wlog (after cyclic relabeling) backwards and $p(n)$ the rightmost
vertex. Then $(G,p)$ has a unique, up to nonzero scaling, equilibrium stress
$\omega$, and this scaling can be chosen such that every forward edge has
positive coefficient and every negative edge has negative coefficient.

###### Proof.

Without loss of generality, set the coefficient $\omega_{1,n}$ on the edge
$\\{1,n\\}$ to $-1$. Now walk, in cyclic order, starting from vertex $1$,
solving the equilibrium condition locally, by setting $\omega_{i,1+1}$ to
solve (indices taken cyclically):

$\omega_{i,i+1}(p(i+1)-p(i))=\omega_{i-1,i}(p(i)-p(i-1)).$

Notice that the sign changes whenever we switch from forwards to backwards
edges, so we have the desired sign pattern. General position implies that we
do not get any zero coefficients. We have, automatically, equilibrium at every
vertex except, possibly $p(n)$. To check that we have equilibrium, notice
that, by induction, all the vectors $\omega_{i,i+1}(p(i+1)-p(i))$ have
magnitude $|p(n)-p(1)|$ and that $\omega_{n-1,n}$ is positive. ∎

Our next lemma is a general fact that can be verified by direct computation.

######  Lemma C.4.

Let $H$ be any graph and $\omega$ an equilibrium stress with associated matrix
$\Omega$. For any subset $S$ of vertices of $H$, let $x(S)$ be the
characteristic vector of $S$. Then

$x(S)^{T}\Omega x(S)=\sum_{\text{edges $ij$: $i\in S$, $j\notin
S$}}\omega_{ij}.$

In particular, if $S$ is the set of vertices on one side of a cut consisting
of edges with positive (resp negative) stress coefficients, then $x(S)$ has
positive (resp negative) Rayleigh quotient.

###### Proof of Theorem C.2.

Let $(G,p)$ be as in the statement and $\Omega$ scaled as in Lemma C.3.
Uniqueness, up to nonzero scale, of the equilibrium stress on $(G,p)$ implies
this is possible. Now recall that removing any two edges from a cycle
determines a cut. If we have $b$ backwards edges, $e_{1},\ldots,e_{b}$, each
of the cuts $\\{e_{1},e_{j}\\}$ for $2\leq j\leq b$ gives rise to a collection
of $b-1$ independent incidence vectors with negative Rayleigh quotient, from
Lemma C.4. Hence $\Omega$ has at least $b-1$ negative eigenvalues. Similarly,
the $f$ edges $e^{\prime}_{1},\ldots,e^{\prime}_{f}$ with positive stress
coefficients give $f-1$ independent incidence vectors with positive Rayleigh
quotient. Since $\Omega$ has a nullity of at least $2$, as an equilibrium
stress matrix, the proof is complete. ∎

##  Appendix D Random graphs

In this section, we prove Theorem 2.7. We will use results of Candès and Tao
[13] as a “black box” along with some ideas from Saliola and Whiteley [52].

The results in this appendix are based on those from [38], but slightly
weaker. We include the proofs here to keep this paper self-contained and
because they are somewhat simpler.

###  D.1 Low-rank matrix completion

Matrix completion is the problem of imputing an unknown $n\times n$ matrix $M$
from a subset of its entries. A fundamental result of Candès and Tao
(specialized to the case where $r$ is a fixed constant is):

######  Theorem D.1 ([13]).

If $M$ is an $n\times n$ symmetric rank $r$ matrix with the strong incoherence
property with constant $\mu>0$, there is a constant $C_{r,\mu}>0$ such that,
if

$m\geq C_{r}\mu^{2}n(\log n)^{2}$

entries of $M$ are sampled uniformly at random, then with probability at least
$1-n^{-3}$, a nuclear norm minimization algorithm recovers all of $M$ from the
observed entries.

For our purposes we do not need to know the exact definition of strong
incoherence. What we do need is that Candès and Tao also prove:

######  Theorem D.2 ([13, Sec. 1.5.1]).

For any rank $r$ and some $\mu=O(\sqrt{\log n})$, there are open sets of
matrices satisfying the strong incoherence property.

In particular, there is a generic symmetric rank $r$ matrix satisfying the
strong incoherence property.

######  Theorem D.3.

Let $r$ be a fixed rank. There is a constant $C^{\prime}_{r}>0$ so that, if

$m\geq C^{\prime}_{r}n(\log n)^{3}$

entries of a generic symmetric matrix $M$ of rank $r$ are sampled uniformly at
random, there are finitely many symmetric matrices $M^{\prime}$ of rank $r$
agreeing with $M$ on the observed entries with probability at least
$1-n^{-3}$.

For a set of observed entries, if, for a generic rank $r$ symmetric matrix
$M$, there are finitely many rank $r$ matrices agreeing with $M$ on the
observed entries, the pattern is said to be _finitely completable_.

###### Proof.

Let $M$ be a generic, rank $r$ symmetric matrix with the strong incoherence
property where $\mu=O(\sqrt{\log n})$ from Theorem D.2. Take $C^{\prime}_{r}$
to be $C_{r}$ from the statement of Theorem D.1. Such an $M$ exists by Theorem
D.2. By Theorem D.1, if $m$ (from the statement) entries are sampled uniformly
at random, the nuclear norm minimization algorithm finds $M$ with probability
$1-n^{-3}$.

If there were any other way to complete the observed entries to get a
different rank $r$ matrix, this would be impossible as soon as the success
probability rises above $1/2$. Hence, for $n\geq r+1$, all but a
$n^{-3}$-fraction of observation patterns with $m$ observed entries yield a
matrix completion problem that is generic and uniquely completable, which is
the matrix completion analogue of global rigidity (see [34, 55]).

We do not know that unique completability is a generic property, even for
symmetric matrices, but the existence of a generic rank $r$ matrix $M$ with a
uniquely completable matrix completion problem for some pattern does imply
that the observation pattern is finitely completable, which is a generic
property [34, 55]. ∎

We notice that, although we are not dealing with symmetrically chosen
observation patterns, since we assume the underlying matrix is symmetric, the
probability of finite completability is not changed when making this
assumption. Similarly, the probability of a pattern being generically finitely
completable can only go up if we deterministically observe the diagonal and
then uniformly sample $m$ other entries.

###  D.2 Rigidity in pseduo-Euclidean spaces

A $d$-dimensional _pseudo-Euclidean_ space $\mathbb{M}^{d}_{s}$ is
$\mathbb{R}^{d}$ equipped with a bilinear form

$\beta_{s}(x,y)=-\gamma_{1}\delta_{1}-\cdots-\gamma_{s}\delta_{s}+\gamma_{s+1}\delta_{s+1}+\cdots+\gamma_{d}\delta_{d}$

where $x=(\gamma_{i})$ and $y=(\delta_{i})$. We can use $\beta_{s}$ to measure
length and define local and global rigidity similarly to the Euclidean case
(see [27, 52] for details).

######  Theorem D.4 ([52]).

For every dimension $d\geq 1$ and $d$-dimensional pseudo-Euclidean space
$\mathbb{M}_{s}^{d}$, local $d$-rigidity is a generic property. Moreover, a
graph $G$ is locally $d$-rigid in $\mathbb{M}_{s}^{d}$ if and only if $G$ is
locally $d$-rigid in Euclidean space.

Meanwhile, as observed by Gortler and Thurston in [27], any symmetric $n\times
n$ matrix of rank $d+1$ and signature $(d+1-s,n-d-1,s)$ arises as the Gram
matrix of a configuration of $n$ vectors in a pseudo-Euclidean space with
$\beta_{s}$ as the bilinear form. Translating language slightly, we have:

######  Theorem D.5 ([27]).

Let $G$ be a graph on $n$ vertices. Then $G$ is locally $d$-rigid in a pseudo-
Euclidean space $\mathbb{M}_{s}^{d}$ if and only if the associated symmetric
set of observed entries, plus the diagonal, is generically finitely
completable for rank $d+1$.

###  D.3 Putting things together

We are now in a position to prove Theorem 2.7. From Theorem D.3, for each rank
$d+1$, there is a constant $C_{d+1}$ so that, if the diagonals and $m\geq
C_{d+1}n\operatorname{polylog}(n)$ uniformly selected entries of a generic
symmetric matrix are observed, the resulting pattern is, whp, finitely
completable. Theorem D.5 then implies that the graph arising from symmetrising
the observed entries is generically $d$-rigid in a pseudo-Euclidean space, and
then, by Theorem D.4 generically $d$-rigid.

## References

  * Abbot [2008] T. G. Abbot.  Generalizations of Kempe’s universality theorem.  Master’s thesis, Massachusetts Institute of Technology, Cambridge, MA, 2008.
  * Alfakih [2011] A. Y. Alfakih.  On bar frameworks, stress matrices and semidefinite programming.  _Mathematical programming_ , 129(1):113–128, 2011\.
  * Améndola et al. [2021] C. Améndola, K. Kohn, P. Reichenbach, and A. Seigal.  Invariant theory and scaling algorithms for maximum likelihood estimation.  _SIAM Journal on Applied Algebra and Geometry_ , 5(2):304–337, 2021.
  * Asimow and Roth [1978] L. Asimow and B. Roth.  The rigidity of graphs.  _Transactions of the American Mathematical Society_ , 245:279–289, 1978.
  * Ben-David [2015] E. Ben-David.  Sharp lower and upper bounds for the Gaussian rank of a graph.  _Journal of Multivariate Analysis_ , 139(C):207–218, 2015.  doi: 10.1016/j.jmva.2015.03.00.
  * Berg and Jordán [2003] A. R. Berg and T. Jordán.  A proof of Connelly’s conjecture on 3-connected circuits of the rigidity matroid.  _J. Combin. Theory Ser. B_ , 88(1):77–97, 2003\.  doi: 10.1016/S0095-8956(02)00037-0.
  * Bernstein et al. [2020] D. I. Bernstein, G. Blekherman, and R. Sinn.  Typical and generic ranks in matrix completion.  _Linear Algebra Appl._ , 585:71–104, 2020.  doi: 10.1016/j.laa.2019.09.001.
  * Blekherman and Sinn [2019] G. Blekherman and R. Sinn.  Maximum likelihood threshold and generic completion rank of graphs.  _Discrete & Computational Geometry_, 61(2):303–324, 2019.
  * Bochnak et al. [1998] J. Bochnak, M. Coste, and M.-F. Roy.  _Real algebraic geometry_ , volume 36 of _Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)]_.  Springer-Verlag, Berlin, 1998.  doi: 10.1007/978-3-662-03718-8.  Translated from the 1987 French original, Revised by the authors.
  * Bolker and Roth [1980] E. Bolker and B. Roth.  When is a bipartite graph a rigid framework?  _Pacific Journal of Mathematics_ , 90(1):27–44, 1980.
  * Brightwell [1993] G. Brightwell.  On the complexity of diagram testing.  _Order_ , 10(4):297–303, 1993.
  * Buhl [1993] S. L. Buhl.  On the existence of maximum likelihood estimators for graphical Gaussian models.  _Scandinavian Journal of Statistics_ , pages 263–270, 1993.
  * Candès and Tao [2010] E. J. Candès and T. Tao.  The power of convex relaxation: near-optimal matrix completion.  _IEEE Trans. Inform. Theory_ , 56(5):2053–2080, 2010.  doi: 10.1109/TIT.2010.2044061.
  * Connelly [1982] R. Connelly.  Rigidity and energy.  _Invent. Math._ , 66(1):11–33, 1982.  doi: 10.1007/BF01404753.
  * Connelly [2005] R. Connelly.  Generic global rigidity.  _Discrete Comput. Geom._ , 33(4):549–563, 2005\.  doi: 10.1007/s00454-004-1124-4.
  * Connelly and Gortler [2017] R. Connelly and S. J. Gortler.  Universal rigidity of complete bipartite graphs.  _Discrete Comput. Geom._ , 57(2):281–304, 2017\.  doi: 10.1007/s00454-016-9836-9.
  * Connelly and Whiteley [2010] R. Connelly and W. Whiteley.  Global rigidity: the effect of coning.  _Discrete & Computational Geometry_, 43(4):717–735, 2010.
  * Connelly et al. [2018] R. Connelly, S. J. Gortler, and L. Theran.  Affine rigidity and conics at infinity.  _Int. Math. Res. Not. IMRN_ , (13):4084–4102, 2018.  doi: 10.1093/imrn/rnx014.
  * Connelly et al. [2020] R. Connelly, S. J. Gortler, and L. Theran.  Generically globally rigid graphs have generic universally rigid frameworks.  _Combinatorica_ , 40(1):1–37, 2020.  doi: 10.1007/s00493-018-3694-4.
  * Connelly et al. [2021] R. Connelly, S. J. Gortler, and L. Theran.  Global rigidity of complete bipartite graphs.  arXiv:2105.01389, 2021.
  * de Grey [2018] A. D. N. J. de Grey.  The chromatic number of the plane is at least 5.  _Geombinatorics_ , 28(1):18–31, 2018.
  * Dempster [1972] A. P. Dempster.  Covariance selection.  _Biometrics_ , pages 157–175, 1972.
  * Dobra et al. [2004] A. Dobra, C. Hans, B. Jones, J. R. Nevins, G. Yao, and M. West.  Sparse graphical models for exploring gene expression data.  _Journal of Multivariate Analysis_ , 90(1):196–212, 2004.
  * Drton et al. [2019] M. Drton, C. Fox, A. Käufl, and G. Pouliot.  The maximum likelihood threshold of a path diagram.  _Ann. Statist._ , 47(3):1536–1553, 2019.  doi: 10.1214/18-AOS1724.
  * Erdős et al. [1965] P. Erdős, F. Harary, and W. T. Tutte.  On the dimension of a graph.  _Mathematika_ , 12:118–122, 1965.  doi: 10.1112/S0025579300005222.
  * Gluck [1975] H. Gluck.  Almost all simply connected closed surfaces are rigid.  In _Geometric topology (Proc. Conf., Park City, Utah, 1974)_ , pages 225–239. Lecture Notes in Math., Vol. 438, 1975.
  * Gortler and Thurston [2014a] S. J. Gortler and D. P. Thurston.  Generic global rigidity in complex and pseudo-Euclidean spaces.  In _Rigidity and symmetry_ , volume 70 of _Fields Inst. Commun._ , pages 131–154. Springer, New York, 2014a.  doi: 10.1007/978-1-4939-0781-6“˙8.
  * Gortler and Thurston [2014b] S. J. Gortler and D. P. Thurston.  Characterizing the universal rigidity of generic frameworks.  _Discrete Comput. Geom._ , 51(4):1017–1036, 2014b.  doi: 10.1007/s00454-014-9590-9.
  * Gortler et al. [2010] S. J. Gortler, A. D. Healy, and D. P. Thurston.  Characterizing generic global rigidity.  _American Journal of Mathematics_ , 132(4):897–939, 2010.
  * Gross and Sullivant [2018] E. Gross and S. Sullivant.  The maximum likelihood threshold of a graph.  _Bernoulli_ , 24(1):386–407, 2018.
  * Hastie et al. [2009] T. Hastie, R. Tibshirani, and J. Friedman.  _The elements of statistical learning_.  Springer Series in Statistics. Springer, New York, second edition, 2009\.  doi: 10.1007/978-0-387-84858-7.  Data mining, inference, and prediction.
  * Hendrickson [1992] B. Hendrickson.  Conditions for unique graph realizations.  _SIAM J. Comput._ , 21(1):65–84, 1992.  doi: 10.1137/0221008.
  * Jackson and Jordán [2005] B. Jackson and T. Jordán.  The $d$-dimensional rigidity matroid of sparse graphs.  _Journal of Combinatorial Theory, Series B_ , 95(1):118–133, 2005.  doi: https://doi.org/10.1016/j.jctb.2005.03.004.
  * J.Király et al. [2015] F. J.Király, L. Theran, and R. Tomioka.  The algebraic combinatorial approach for low-rank matrix completion.  _Journal of Machine Learning Research_ , 16(41):1391–1436, 2015.
  * Jordán [2017] T. Jordán.  Extremal problems and results in combinatorial rigidity.  In _Proc. of the 10th Japanese Hungarian Symposium on Discrete Mathematics and its Applications_ , pages 297–304, Budapest, May 2017.
  * Kapovich and Millson [1997] M. Kapovich and J. J. Millson.  Hodge theory and the art of paper folding.  _Publ. Res. Inst. Math. Sci._ , 33(1):1–31, 1997\.  doi: 10.2977/prims/1195145531.
  * Kasiviswanathan et al. [2011] S. P. Kasiviswanathan, C. Moore, and L. Theran.  The rigidity transition in random graphs.  In _Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms_ , pages 1237–1252, 2011.
  * Király and Theran [2013] F. J. Király and L. Theran.  Coherence and sufficient sampling densities for reconstruction in compressed sensing.  Preprint, arXiv:1302.2767, 2013.
  * Kloks [1994] T. Kloks.  _Treewidth_ , volume 842 of _Lecture Notes in Computer Science_.  Springer-Verlag, Berlin, 1994.  doi: 10.1007/BFb0045375.  Computations and approximations.
  * Krumsiek et al. [2011] J. Krumsiek, K. Suhre, T. Illig, J. Adamski, and F. J. Theis.  Gaussian graphical modeling reconstructs pathway reactions from high-throughput metabolomics data.  _BMC systems biology_ , 5(1):1–16, 2011.
  * Laman [1970] G. Laman.  On graphs and rigidity of plane skeletal structures.  _J. Engrg. Math._ , 4:331–340, 1970.  doi: 10.1007/BF01534980.
  * Lee and Streinu [2008] A. Lee and I. Streinu.  Pebble game algorithms and sparse graphs.  _Discrete Math._ , 308(8):1425–1437, 2008.  doi: 10.1016/j.disc.2007.07.104.
  * Lew et al. [2022] A. Lew, E. Nevo, Y. Peled, and O. E. Raz.  Sharp threshold for rigidity of random graphs.  Preprint, arXiv:2202.09917, 2022.
  * Linial et al. [1988] N. Linial, L. Lovász, and A. Wigderson.  Rubber bands, convex embeddings and graph connectivity.  _Combinatorica_ , 8(1):91–102, 1988.  doi: 10.1007/BF02122557.
  * Makam et al. [2021] V. Makam, P. Reichenbach, and A. Seigal.  Symmetries in directed gaussian graphical models.  _arXiv preprint arXiv:2108.10058_ , 2021.
  * Maxwell [1864] J. C. Maxwell.  On the calculation of the equilibrium and stiffness of frames.  _The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science_ , 27(182):294–299, 1864.  doi: 10.1080/14786446408643668.
  * Nevo [2007] E. Nevo.  On embeddability and stresses of graphs.  _Combinatorica_ , 27(4):465–472, 2007.  doi: 10.1007/s00493-007-2168-x.
  * Nixon and Whiteley [2019] A. Nixon and W. Whiteley.  Change of metrics in rigidity theory.  In _Handbook of geometric constraint systems principles_ , Discrete Math. Appl. (Boca Raton), pages 351–374. CRC Press, Boca Raton, FL, 2019\.
  * Pittel et al. [1996] B. Pittel, J. Spencer, and N. Wormald.  Sudden emergence of a giant $k$-core in a random graph.  _J. Combin. Theory Ser. B_ , 67(1):111–151, 1996\.  doi: 10.1006/jctb.1996.0036.
  * Pollaczek-Geiringer [1927] H. Pollaczek-Geiringer.  Über die gliederung ebener fachwerke.  _Zeitschrift für Angewandte Mathematik und Mechanik_ , 7:58–72, 1927.
  * Rosen et al. [2020] Z. Rosen, J. Sidman, and L. Theran.  Algebraic matroids in action.  _Amer. Math. Monthly_ , 127(3):199–216, 2020\.  doi: 10.1080/00029890.2020.1689781.
  * Saliola and Whiteley [2007] F. V. Saliola and W. Whiteley.  Some notes on the equivalence of first-order rigidity in various geometries.  Preprint, arXiv:0709.3354, 2007.
  * Schäfer and Strimmer [2005] J. Schäfer and K. Strimmer.  An empirical Bayes approach to inferring large-scale gene association networks.  _Bioinformatics_ , 21(6):754–764, 2005.
  * Simon [2011] B. Simon.  _Convexity_ , volume 187 of _Cambridge Tracts in Mathematics_.  Cambridge University Press, Cambridge, 2011.  doi: 10.1017/CBO9780511910135.  An analytic viewpoint.
  * Singer and Cucuringu [2009/10] A. Singer and M. Cucuringu.  Uniqueness of low-rank matrix completion by rigidity theory.  _SIAM J. Matrix Anal. Appl._ , 31(4):1621–1641, 2009/10.  doi: 10.1137/090750688.
  * Stasica [2003] J. Stasica.  Smooth points of a semialgebraic set.  _Ann. Polon. Math._ , 82(2):149–153, 2003.  doi: 10.4064/ap82-2-5.
  * Tutte [1963] W. T. Tutte.  How to draw a graph.  _Proc. London Math. Soc. (3)_ , 13:743–767, 1963.  doi: 10.1112/plms/s3-13.1.743.
  * Uhler [2012] C. Uhler.  Geometry of maximum likelihood estimation in gaussian graphical models.  _Annals of Statistics_ , 40(1):238–261, 2012\.
  * Vandenberghe et al. [1998] L. Vandenberghe, S. Boyd, and S.-P. Wu.  Determinant maximization with linear matrix inequality constraints.  _SIAM journal on matrix analysis and applications_ , 19(2):499–533, 1998.
  * Whiteley [1983] W. Whiteley.  Cones, infinity and $1$-story buildings.  _Structural Topology_ , (8):53–70, 1983.  With a French translation.
  * Wormald [1999] N. C. Wormald.  Models of random regular graphs.  In _Surveys in combinatorics, 1999 (Canterbury)_ , volume 267 of _London Math. Soc. Lecture Note Ser._ , pages 239–298. Cambridge Univ. Press, Cambridge, 1999.
  * Wu et al. [2003] X. Wu, Y. Ye, and K. R. Subramanian.  Interactive analysis of gene interactions using graphical gaussian model.  In _Proceedings of the 3rd International Conference on Data Mining in Bioinformatics_ , pages 63–69, 2003.