# Stress-linked pairs of vertices and the generic stress matroid

Dániel Garamvölgyi Department of Operations Research, ELTE Eötvös Loránd
University, and the HUN-REN–ELTE Egerváry Research Group on Combinatorial
Optimization, Pázmány Péter sétány 1/C, 1117 Budapest, Hungary. e-mail:
<EMAIL_ADDRESS>
###### Abstract

Given a graph $G$ and a mapping $p:V(G)\rightarrow\mathbb{R}^{d}$, we say that
the pair $(G,p)$ is a ($d$-dimensional) realization of $G$. Two realizations
$(G,p)$ and $(G,q)$ are equivalent if each of the point pairs corresponding to
the edges of $G$ have the same distance under the embeddings $p$ and $q$. A
pair of vertices $\\{u,v\\}$ is globally linked in $G$ in $\mathbb{R}^{d}$ if
for every generic realization $(G,p)$ and every equivalent realization
$(G,q)$, $(G+uv,p)$ and $(G+uv,q)$ are also equivalent.

In this paper we introduce the notion of ${d}$-stress-linked vertex pairs.
Roughly speaking, a pair of vertices $\\{u,v\\}$ is ${d}$-stress-linked in $G$
if the edge $uv$ is generically stressed in $G+uv$ and for every generic
$d$-dimensional realization $(G,p)$, every configuration $q$ that satisfies
all of the equilibrium stresses of $(G,p)$ also satisfies the equilibrium
stresses of $(G+uv,p)$. Among other results, we show that ${d}$-stress-linked
vertex pairs are globally linked in $\mathbb{R}^{d}$, and we give a
combinatorial characterization of ${2}$-stress-linked vertex pairs that
matches the conjecture of Jackson et al. about the characterization of
globally linked pairs in $\mathbb{R}^{2}$.

As a key tool, we introduce and study the “algebraic dual” of the
$d$-dimensional generic rigidity matroid of a graph, which we call the
$d$-dimensional generic stress matroid of the graph. We believe that our
results about this matroid, which describes the global behaviour of
equilibrium stresses of generic realizations of $G$, may be of independent
interest.

We use our results to give positive answers to conjectures of Jordán,
Connelly, and Grasegger et al.

##  1 Introduction

One of the central unsolved problems in combinatorial rigidity theory is
finding a combinatorial characterization of globally $d$-rigid graphs for
$d\geq 3$. Roughly speaking, a graph $G$ is _globally $d$-rigid_ if for every
generic embedding $p:V(G)\rightarrow\mathbb{R}^{d}$ of its vertices into
Euclidean space, the (labeled) collection of edge lengths $||p(u)-p(v)||,uv\in
E(G)$ uniquely determine all of the pairwise distances $||p(u)-p(v)||,u,v\in
V(G)$. (We shall give precise definitions and references in the next section.)
It is folklore that a graph is globally $1$-rigid if and only if it is
$2$-connected, and Jackson and Jordán [19] gave a combinatorial
characterization of globally $2$-rigid graphs, but the $d\geq 3$ case is still
wide open.

A major breakthrough in the study of global rigidity is due to Gortler, Healy
and Thurston [12] who, by proving a conjecture of Connelly [4], characterized
globally rigid graphs in terms of equilibrium stresses. A $d$-dimensional
_realization_ of a graph $G$ is a pair $(G,p)$ with
$p:V(G)\rightarrow\mathbb{R}^{d}$. A vector $\omega\in\mathbb{R}^{E(G)}$ is an
_equilibrium stress_ , or simply a _stress_ , of $(G,p)$ if it satisfies a
certain system of equilibrium conditions determined by $(G,p)$. The main
result of [12] states, roughly, that a graph on at least $d+2$ vertices is
globally $d$-rigid if and only if for any generic $d$-dimensional realization
$(G,p)$ and any generic equilibrium stress $\omega$ of $(G,p)$, the
realizations $(G,q)$ that have $\omega$ as a stress are precisely the affine
images of $(G,p)$. Although this is not a combinatorial characterization, it
has nonetheless proved to be a fundamental tool in the combinatorial approach.
Apart from the characterization itself, a major contribution of [12] is the
introduction of tools from algebraic geometry to rigidity theory. In
particular, the authors gave a geometric interpretation of stresses as the
tangent hyperplanes of the _measurement variety_ of $G$, the affine variety of
every edge measurement that can be obtained from $d$-dimensional realizations
of a graph $G$. This geometric picture is at the heart of our investigations
in this paper.

While there has been a number of important advances in the combinatorial
understanding of global rigidity in the more than one decade since the
publication of [12], a general combinatorial characterization still seems
elusive. One possible avenue for progress is the investigation of globally
linked pairs. A pair of vertices $u,v\in V(G)$ is _globally linked_ in $G$ in
$\mathbb{R}^{d}$ if for every generic $d$-dimensional realization $(G,p)$, the
distances $||p(u^{\prime})-p(v^{\prime})||,u^{\prime}v^{\prime}\in E(G)$
uniquely determine the distance $||p(u)-p(v)||$. It is apparent by comparing
the definitions that a graph is globally $d$-rigid if and only if every pair
of vertices is globally linked in it. This shows that characterizing globally
linked pairs is at least as difficult as characterizing global rigidity, and
indeed it seems to be more difficult: a characterization (combinatorial or
otherwise) of globally linked pairs is not even available in the $d=2$ case.
Nonetheless, there are a number of conjectures in the literature about
globally linked pairs, many of which we will recall throughout the paper, and
we believe that even partial progress on these problems may help in
understanding the combinatorial nature of global rigidity.

A natural objective, following [12], is to find a characterization of globally
linked pairs based on equilibrium stresses. An apparent difficulty for this is
the fact that, in contrast with global rigidity, being globally linked is not
a “generic property”: it can happen that some generic realizations $(G,p)$
satisfy the condition defining globally linked pairs, while other generic
realizations do not. This problem can be rectified by extending our setting to
include _complex realizations_ , that is, pairs $(G,p)$ where
$p:V(G)\rightarrow\mathbb{C}^{d}$ maps the vertices of $G$ into complex space.
In this way one can define what it means for a pair of vertices to be globally
linked in $G$ in $\mathbb{C}^{d}$, and this does turn out to be a generic
property. However, this approach presents another difficulty: it seems that
the proof method of [12], which is based on degree theory, cannot be adapted
to the complex setting.

Nonetheless, we initiate this line of study by introducing a stress-based
analogue of globally linked vertex pairs in $\mathbb{R}^{d}$ (and in
$\mathbb{C}^{d}$). Roughly speaking, we say that a pair of vertices
$\\{u,v\\}$ is _${d}$ -stress-linked_ if the edge $uv$ is generically stressed
in $G+uv$ in $d$ dimensions and for every generic $d$-dimensional realizaton
$(G,p)$ and every realization $(G,q)$ that satisfies the equilibrium stresses
of $(G,p)$, $(G+uv,q)$ satisfies the equilibrium stresses of $(G+uv,p)$. We
show that ${d}$-stress-linked vertex pairs are globally linked in
$\mathbb{C}^{d}$ (and hence in $\mathbb{R}^{d}$). We conjecture that the
reverse implication also holds (6.1). As partial evidence for this, we prove
the ${d}$-stress-linked analogue of a number of conjectures about globally
linked pairs. For example, we show that the combinatorial characterization
conjectured by Jackson, Jordán and Szabadka [21] for globally linked pairs in
$\mathbb{R}^{2}$ (and later by Jackson and Owen [23] for globally linked pairs
in $\mathbb{C}^{2}$) characterizes ${2}$-stress-linked vertex pairs (Theorem
4.20). We also settle a significant special case of a “gluing conjecture” made
by Jordán and the author in [10] about globally linked pairs in
$\mathbb{R}^{d}$ by proving that the analogous statement holds for
${d}$-stress-linked pairs (Theorem 4.15). Our most significant result that is
not based on a conjecture about globally linked pairs is given by Corollary
4.9: it states that if a pair of vertices $\\{u,v\\}$ is ${d}$-stress-linked
in $G$, then it remains so after the deletion of any $\mathcal{R}_{d}$-bridge
in $G$, and similarly, if an edge $e$ of $G$ is an $\mathcal{R}_{d}$-bridge,
then it remains an $\mathcal{R}_{d}$-bridge after adding an edge between any
${d}$-stress-linked vertex pair.

The study of ${d}$-stress-linked vertex pairs requires a deeper understanding
of the “global” behaviour of stresses of generic frameworks. For example, is
it possible that two such stresses (possibly belonging to different
realizations) only differ in one coordinate? Or, when can we find such a
stress whose values are prescribed on some set of edges? In order to handle
such questions we introduce the _dual variety_ of the measurement variety,
which we call the _( $d$-dimensional generic) stress variety_ of the graph.
While the generic stress variety already appeared implicitly in [12], we
believe that its full significance in rigidity theory is yet to be understood.
In fact, in [12], the dual relationship between the measurement variety and
the generic stress variety was only used through its corollary that the
generic contact locus of the measurement variety is a linear space.

We explore and use this duality to a deeper extent using the perspective of
matroid theory. It is well-known that to each affine variety $X$ we can
associate its _algebraic matroid_ $\mathcal{M}(X)$, a matroid defined via
properties of the coordinate projections of $X$. We call the matroid
associated to the stress variety in this way the _( $d$-dimensional generic)
stress matroid_ of the graph. We rely on matroid theory more as a language
rather than a tool, and our results on the generic stress matroid could be
rephrased as purely geometric statements about the stress variety. However,
the perspective of algebraic matroids highlights a connection that turns out
to be of central importance in this paper: the fact that the algebraic matroid
of a complex affine variety is the same as the linear matroid defined by its
tangent space at a generic point. In the case of the rigidity matroid this is
a well-known observation, roughly stating that a generic realization $(G,p)$
is infinitesimally rigid if and only if there is, up to congruence, a finite
number of realizations $(G,q)$ equivalent to $(G,p)$. However, in the case of
the stress variety this connection leads to a novel insight: it gives a
geometric interpretation of the dual matroid of the stress matroid in terms of
the generic contact locus of the measurement variety (Theorem 3.2). This
correspondence illuminates both the combinatorial structure of the stress
matroid and the geometric structure of the generic contact locus.

We note that in the recent preprint [5], the authors introduce and study the
_variety of general position stress matrices_ of a graph. This variety
coincides with the generic stress variety when $G$ is globally $d$-rigid, but
in general the two varieties can be different. For example, if $G$ is
$(d+1)$-connected but generically stress-free in $d$ dimensions, then the
variety of general position stress matrices of $G$ has positive dimension,
while the generic stress variety of $G$ is zero-dimensional.

In Section 5, we give three applications of our results on ${d}$-stress-linked
vertex pairs. The first is related to _minimally globally $d$-rigid_ graphs,
that is, graphs $G$ that are globally $d$-rigid but for which $G-e$ is not
globally $d$-rigid for every $e\in E(G)$. In [25], Jordán gave a conjectured
upper bound on the number of edges in a minimally globally $d$-rigid graph
that is linear in the number of its vertices. He also posed the stronger
conjecture that if $G$ is globally $d$-rigid but $G-e$ is not, then $e$ is an
$\mathcal{R}_{d+1}$-bridge in $G$. The latter conjecture implies that
minimally globally $d$-rigid graphs are not only sparse, but “everywhere
sparse”, that is, they satisfy a certain $(d+1)$-sparsity count. While in [9]
Jordán and the author proved the upper bound on the number of edges, the other
conjecture remains open. However, using the notion of ${d}$-stress-linked
vertex pairs we give a quick proof that minimally globally $d$-rigid graphs
are indeed everywhere sparse (Corollary 5.3). More precisely, we show that if
$G$ is minimally globally $d$-rigid, then every subset $X\subseteq V(G)$ of
size at least $d+2$ induces at most $(d+1)|X|-\binom{d+2}{2}$ edges. We also
show that this upper bound is strict unless $X$ is a clique of size $d+2$.

We also settle two conjectures about graphs with small separators. In [3],
Connelly showed that if $G_{1}$ and $G_{2}$ are globally $d$-rigid graphs with
$d+1$ vertices in common, then $G_{1}\cup G_{2}-uv$ is globally $d$-rigid for
any edge $uv\in E(G_{1})\cap E(G_{2})$. He asked whether the analogous result
holds for redundantly $d$-rigid graphs. In [15], Grasegger et al. considered a
similar question for so-called $\mathcal{R}_{d}$-circuits. They conjectured
that if $G_{1}$ and $G_{2}$ are $\mathcal{R}_{d}$-circuits such that
$G_{1}\cap G_{2}$ is a complete graph on $t$ vertices with $2\leq t\leq d+1$,
then $G_{1}\cup G_{2}-uv$ is an $\mathcal{R}_{d}$-circuit for any edge $uv\in
E(G_{1})\cap E(G_{2})$. We give affirmative answers to both of these problems
(Theorems 5.4 and 5.5). In fact, the two proofs are almost identical. In both
cases our strategy is to use the “gluing” result given by Theorem 4.15 to show
that $\\{u,v\\}$ is ${d}$-stress-linked in $G_{1}\cup G_{2}-uv$, and then use
Corollary 4.9 to deduce that since $G_{1}\cup G_{2}$ has no
$\mathcal{R}_{d}$-bridges, neither does $G_{1}\cup G_{2}-uv$.

##  2 Preliminaries

In this section we give a fairly comprehensive account of the tools and
results from algebraic geometry that we will use. Section 2.1 deals with basic
definitions regarding affine varieties. Everything in this subsection is
standard and can be found in most textbooks on basic algebraic geometry, such
as [17] or [33] (often in much greater generality). Section 2.2 describes the
notion of a “generic point” that is used in this paper. Its content is
somewhat specialized, but is not new in the rigidity theory literature, see
[8, 13] for example. Section 2.3 introduces algebraic matroids, which in our
context will be matroids defined by coordinate projections of varieties. See
[29] for a good general reference on this topic. Finally, in Section 2.4 we
give the basic definitions of rigidity theory from an algebraic geometric
point of view. This approach is not the standard one, but it has been explored
and used in many recent papers, including the three cited above. For a general
reference on rigidity theory see, for example, [24] and [31].

To avoid some trivialities, we always implicitly assume that the graphs
considered in this paper have a nonempty set of edges. Given a graph $G$, we
use $V(G)$ and $E(G)$ to denote the vertex set and the edge set of $G$,
respectively. We assume familiarity with the basic notions of matroid theory;
the standard reference is [28]. Given a matroid $\mathcal{M}$, we use
$\mathcal{M}^{*}$ to denote the dual matroid of $\mathcal{M}$. Suppose that
$\mathcal{M}$ has ground set $E$ and rank function $r$. A bipartition
$(E_{1},E_{2})$ of $E$ is a _separation_ of $\mathcal{M}$ if
$r(E)=r(E_{1})+r(E_{2})$. A matroid is _connected_ if it has no nontrivial
separations, or equivalently, if for every pair of elements of $E$ there is a
circuit of $\mathcal{M}$ containing them. Every matroid can be uniquely
written as the direct sum of connected matroids, which are called the
_connected components_ of the matroid. For two matroids
$\mathcal{N},\mathcal{M}$ we write $\mathcal{N}\preceq\mathcal{M}$ to mean
that every independent set in $\mathcal{N}$ is also independent in
$\mathcal{M}$.

###  2.1 Affine varieties

A set $X\subseteq\mathbb{C}^{k}$ is an _affine variety_ if it is the set of
common zeroes of some polynomials
$f_{1},\ldots,f_{l}\in\mathbb{C}[x_{1},\ldots,x_{k}]$. The _Zariski topology_
on $\mathbb{C}^{k}$ is the topology whose closed sets are the affine varieties
of $\mathbb{C}^{k}$, and more generally, the Zariski topology on a subset of
$\mathbb{C}^{k}$ is the subspace topology inherited from the Zariski topology
on $\mathbb{C}^{k}$. For an arbitrary set $X\subseteq\mathbb{C}^{k}$, we use
$\overline{X}$ to denote the _Zariski closure_ of $X$, which is the smallest
affine variety containing $X$. We say that a set is Zariski closed/open/dense
to mean that it is closed/open/dense in the Zariski topology.

An affine variety is _irreducible_ if it is nonempty and cannot be written as
the proper union of two affine varieties. We stress that our definition of
affine varieties does not include irreducibility, although most of the
varieties we shall be dealing with are irreducible. Every nonempty affine
variety $X$ can be uniquely written as the union of a finite number of
irreducible affine varieties, which are called the _components_ of $X$. An
interesting feature of the Zariski topology is that for an irreducible variety
$X$, every nonempty Zariski open subset (that is, every nonempty subset of the
form $X\setminus Y$ for some affine variety $Y$) is Zariski dense in $X$.

An affine variety $X$ is _homogeneous_ if it is invariant under scaling, that
is, $cx\in X$ for every $x\in X$ and $c\in\mathbb{C}$. An important class of
homogeneous irreducible affine varieties are _linear spaces_ , which are just
linear subspaces of $\mathbb{C}^{k}$.

The _dimension_ of an affine variety $X$, denoted by $\dim(X)$, is the largest
number $k$ for which there exists a chain of irreducible varieties
$X_{0}\subsetneq X_{1}\subsetneq\ldots\subsetneq X_{k}\subseteq X$. It can be
seen from this definition that if $X^{\prime}\subsetneq X$ are irreducible
varieties, then $\dim(X^{\prime})<\dim(X)$.

A subset $X\subseteq\mathbb{C}^{k}$ is _Zariski constructible_ if can be
obtained from a finite number of affine varieties by taking intersections,
unions and complements. A Zariski constructible set $X$ is _irreducible_ if
its Zariski closure is irreducible. Every Zariski constructible set contains a
dense Zariski open subset of its closure. Let $X\subseteq\mathbb{C}^{k}$ be an
irreducible Zariski constructible set. A function
$f:X\rightarrow\mathbb{C}^{l}$ is a _polynomial map_ if there exist
polynomials $f_{1},\ldots,f_{l}\in\mathbb{C}[x_{1},\ldots,x_{k}]$ such that
$f(x)=(f_{1}(x),\ldots,f_{l}(x))$ for all $x\in X$. Polynomial maps are
continuous with respect to the Zariski topology, and it follows from
topological considerations that if $X$ is an irreducible Zariski constructible
set and $f:X\rightarrow\mathbb{C}^{l}$ is a polynomial map, then
$\overline{f(X)}$ is also irreducible.

Let $X\subseteq\mathbb{C}^{k}$ be an irreducible affine variety defined by
some polynomials $f_{1},\ldots,f_{l}\in\mathbb{C}[x_{1},\ldots,x_{k}]$.
Consider the polynomial map
$f=(f_{1},\ldots,f_{l}):\mathbb{C}^{k}\rightarrow\mathbb{C}^{l}$ and let $df$
be the _Jacobian_ of $f$, which can be thought of as a $k\times l$ matrix of
polynomials. At each point $x\in X$, we define the _tangent space of $X$ at
$x$_ (denoted by $T_{x}(X)$) as the kernel of $df_{x}$, the Jacobian of $f$
evaluated at $x$. This is a linear subspace of $\mathbb{C}^{k}$, and it is
independent of the choice of generating polynomials $f$ of $X$. The dimension
of $T_{x}(X)$ is always at least the dimension of $X$, and if the two
quantities are the same, then $x$ is said to be a _smooth point_ of $X$;
otherwise it is a _singular point_. The singular points of $X$ form a proper
subvariety called the _singular locus_ of $X$. If $X^{\prime}$ is an
irreducible affine variety with $X^{\prime}\subseteq X$ and $x\in X^{\prime},$
then $T_{x}(X^{\prime})$ is a linear subspace of $T_{x}(X)$.

Let $x\in X$ be a smooth point and let $\omega\in\mathbb{C}^{k}$ be a vector.
By a slight abuse of terminology we say that $\omega$ is a _tangential
hyperplane to $X$ at $x$_ if
$\omega^{\perp}=\\{y\in\mathbb{C}^{k}:\sum_{i=1}^{k}\omega_{i}y_{i}=0\\}$
contains $T_{x}(X)$. We denote the set of tangential hyperplanes to $T_{x}(X)$
by $T_{x}(X)^{\perp}$, and call this the _orthogonal complement_ of
$T_{x}(X)$.111Instead of considering the tangential hyperplane $\omega$ as a
vector, it would perhaps be more proper to consider it as a functional, i.e.,
a member of the dual vector space of $\mathbb{C}^{k}$. For simplicity and to
follow the existing rigidity theory literature, we instead chose to identify
the dual space with $\mathbb{C}^{k}$ using the isomorphism given by the
bilinear form $\langle x,y\rangle=\sum_{i=1}^{k}x_{i}y_{i}$.

Let $f:X\rightarrow\mathbb{C}^{l}$ be a polynomial map and suppose that
$f(X)\subseteq Y$ for some irreducible affine variety $Y$. Consider $x\in X$
and let $y=f(x)\in Y$. Then we have $df_{x}(T_{x}(X))\subseteq T_{y}(Y)$,
i.e., the restriction of the Jacobian of $f$ at $x$ to $T_{x}(X)$ gives a
(well-defined) map $df_{x}:T_{x}(X)\rightarrow T_{y}(Y)$. The following is one
of the many results called Bertini’s theorem. It is an algebraic analogue of
Sard’s lemma from differential topology.

######  Theorem 2.1.

([33, Section 6.2]) Let $X\subseteq\mathbb{C}^{k}$ be an irreducible affine
variety, $f:X\rightarrow\mathbb{C}^{l}$ a polynomial map and
$Y=\overline{f(X)}$. Then for a nonempty Zariski open subset of points $x\in
X$ the map $df_{x}:T_{x}(X)\rightarrow T_{f(x)}(Y)$ is surjective. If moreover
every point of $X$ is smooth, then there is a nonempty Zariski open subset of
points $y\in Y$ such that for every $x\in f^{-1}(y)$ the map
$df_{x}:T_{x}(X)\rightarrow T_{y}(Y)$ is surjective.

Let $f:X\rightarrow\mathbb{C}^{l}$ be a polynomial map and $y\in\text{Im}(f)$.
We call $f^{-1}(y)$ the _fiber of $f$ over $y$_ in $X$. This is also an affine
variety. The first part of the following result is often called the fiber
dimension theorem.

######  Theorem 2.2.

([33, Theorem 1.25])

Let $X\subseteq\mathbb{C}^{k}$ be an irreducible affine variety,
$f:X\rightarrow\mathbb{C}^{l}$ a polynomial map and $Y=\overline{f(X)}$. Then
for a nonempty Zariski open subset of points $x\in X$, every component of the
fiber of $f$ over $f(x)$ has dimension $\dim(X)-\dim(Y)$.

###  2.2 Varieties defined over $\mathbb{Q}$

In algebraic geometry a property of points of an irreducible affine variety
$X$ is sometimes said to be “generic” if it holds on a nonempty Zariski open
(and hence dense) subset of $X$. However, in the rigidity theory literature it
is common to use a stronger notion of genericity which will be more convenient
for us as well. Although the results in this subsection are routine, for
future reference we provide proofs in the Appendix whenever references are not
available.

An affine variety $X\subseteq\mathbb{C}^{k}$ is _defined over $\mathbb{Q}$_ if
it is the set of common zeroes of some polynomials with rational coefficients.
More generally, a Zariski constructible set $X\subseteq\mathbb{C}^{k}$ is
_defined over $\mathbb{Q}$_ if it can be obtained from a finite number of
affine varieties defined over $\mathbb{Q}$ by taking intersections, unions and
complements. The first part of the following proposition is (a special case
of) Chevalley’s theorem.

######  Proposition 2.3.

Let $X\subseteq\mathbb{C}^{k}$ be a Zariski constructible set defined over
$\mathbb{Q}$ and $f:X\rightarrow\mathbb{C}^{l}$ a polynomial map with rational
coefficients.

  1. (a)

([1, Theorem 1.22]) The image $f(X)$ is also Zariski constructible and defined
over $\mathbb{Q}$.

  2. (b)

([11, Theorem A.8]) The Zariski closure $\overline{X}$ is also defined over
$\mathbb{Q}$.

  3. (c)

([13, Lemma A.4]) There is a subvariety $X^{\prime}$ of $\overline{X}$ defined
over $\mathbb{Q}$ such that $\overline{X}\setminus X^{\prime}\subseteq X$.

Let $X\subseteq\mathbb{C}^{k}$ be an irreducible variety defined over
$\mathbb{Q}$. We say that a point $x\in\mathbb{C}^{k}$ is _$X$ -generic_ if
$x\in X$ and the only polynomials with rational coefficients that vanish at
$x$ are those that vanish at every point of $X$. More generally, a point of an
irreducible Zariski constructible set $X$ is _$X$ -generic_ if it is
$\overline{X}$-generic. Note that by the Proposition 2.3(c), every
$\overline{X}$-generic point lies in $X$. The following lemmas describe some
of the basic properties of generic points.

######  Lemma 2.4.

([13, Lemma A.6]) Let $X^{\prime}\subseteq X\subseteq\mathbb{C}^{k}$ be
irreducible affine varieties with $X$ defined over $\mathbb{Q}$. If
$X^{\prime}$ contains an $X$-generic point, then the set of $X$-generic points
in $X^{\prime}$ is Zariski dense in $X^{\prime}$.

######  Lemma 2.5.

Let $X\subseteq\mathbb{C}^{k}$ be an irreducible affine variety defined over
$\mathbb{Q}$, $f:X\rightarrow\mathbb{C}^{l}$ a polynomial map with rational
coefficients and $Y=\overline{f(X)}\subseteq\mathbb{C}^{l}$.

  1. (a)

([13, Lemma A.7]) If $x\in X$ is $X$-generic, then $f(x)$ is $Y$-generic.

  2. (b)

([13, Lemmas 4.4 and A.8]) If $y\in Y$ is $Y$-generic, then the fiber
$f^{-1}(y)$ contains an $X$-generic point. In particular, every $Y$-generic
point lies in $f(X)$.

  3. (c)

([11, Lemma A.6]) If $\dim(X)=\dim(Y)$ and $y\in Y$ is $Y$-generic, then every
point in the fiber $f^{-1}(y)$ is $X$-generic.

Note that in the preceding statement $Y$ is irreducible and it is defined over
$\mathbb{Q}$ by Proposition 2.3, so it is reasonable to talk about $Y$-generic
points.

######  Lemma 2.6.

Let $X\subseteq\mathbb{C}^{k}$ be an irreducible affine variety defined over
$\mathbb{Q}$, $x\in X$ an $X$-generic point and $f:X\rightarrow\mathbb{C}^{l}$
a polynomial map with rational coefficients. Let $Y=\overline{f(X)}$. Each of
the following statements hold.

  1. (a)

$x$ is a smooth point.

  2. (b)

The fiber of $f$ over $f(x)$ has dimension $\dim(X)-\dim(Y)$.

  3. (c)

The map $df_{x}:T_{x}(X)\rightarrow T_{f(x)}(Y)$ is surjective.

  4. (d)

If every point of $X$ is smooth, then
$df_{x^{\prime}}:T_{x^{\prime}}(X)\rightarrow T_{f(x^{\prime})}(Y)$ is
surjective for every point $x^{\prime}$ in the fiber of $f$ over $f(x)$.

###  2.3 Matroids of varieties

In this subsection we define the algebraic matroid of an irreducible affine
variety $X$. Again, [29] is a good reference. Oxley [28, Section 6.7] also
discusses algebraic matroids, but from the perspective of algebraic
independence in field extensions rather than coordinate projections of affine
varieties. As discussed in [29], the two approaches are equivalent when one is
working over an algebraically closed field, as we shall do.

Let $E$ be a finite set and let us consider the affine space $\mathbb{C}^{E}$
with coordinate axes indexed by $E$. Let $X\subseteq\mathbb{C}^{E}$ be an
irreducible affnie variety. For every subset $E_{0}\subseteq E$, we denote by
$\pi_{E_{0}}$ the restriction of the coordinate projection
$\mathbb{C}^{E}\rightarrow\mathbb{C}^{E_{0}}$ to $X$. Throughout the paper we
will use the notation $X_{E_{0}}=\overline{\pi_{E_{0}}(X)}$. To every
irreducible variety $X\subseteq\mathbb{C}^{E}$ we associate a matroid
$\mathcal{M}(X)$ on ground set $E$ defined by

$E_{0}\subseteq E\text{ is independent in }\mathcal{M}(X)\Longleftrightarrow
X_{E_{0}}=\mathbb{C}^{E_{0}}.$

We call $\mathcal{M}(X)$ the _algebraic matroid_ associated to $X$, and we say
that $X$ is an _algebraic representation_ of $\mathcal{M}(X)$. The rank of
$\mathcal{M}(X)$ is $\dim(X)$, and the restriction of $\mathcal{M}(X)$ to a
subset $E_{0}\subseteq E$ is the algebraic matroid associated to the
projection $X_{E_{0}}$. The following characterization of spanning subsets in
algebraic matroids follows from Theorem 2.2 and its “generic” version Lemma
2.6(b).

######  Lemma 2.7.

Let $X\subseteq\mathbb{C}^{E}$ be an irreducible affine variety,
$E_{0}\subseteq E$ a subset and $\pi_{E_{0}}:X\rightarrow X_{E_{0}}$ the
projection of $X$ onto $\mathbb{C}^{E_{0}}$.

  1. (a)

$E_{0}$ is spanning in $\mathcal{M}(X)$ if and only if for a nonempty Zariski
open subset of points $x\in X$, the fiber of $\pi_{E_{0}}$ over
$\pi_{E_{0}}(x)$ is finite.

  2. (b)

If $X$ is defined over $\mathbb{Q}$ and $x$ is an $X$-generic point, then
$E_{0}$ is spanning in $\mathcal{M}(X)$ if and only if the fiber of
$\pi_{E_{0}}$ over $\pi_{E_{0}}(x)$ is finite.

The next lemma relates the separations of $\mathcal{M}(X)$ to the geometry of
$X$. It is an easy consequence of the fact that the Cartesian product of
irreducible affine varieties is an irreducible affine variety.

######  Lemma 2.8.

([8, Lemma 3.1]) Let $X\subseteq\mathbb{C}^{E}$ be an irreducible affine
variety. A bipartition $(E_{1},E_{2})$ of $E$ is a separation of
$\mathcal{M}(X)$ if and only if $X=X_{E_{1}}\times X_{E_{2}}$, where
$X_{E_{i}}=\overline{\pi_{E_{i}}(X)}$. In particular, $e\in E$ is a bridge of
$\mathcal{M}(X)$ if and only if $X=X_{E-e}\times\mathbb{C}$.

If $X^{\prime}\subseteq X\subseteq\mathbb{C}^{E}$ are irreducible varieties,
then clearly $\overline{\pi_{E_{0}}(X^{\prime})}=\mathbb{C}^{E_{0}}$ also
implies $\overline{\pi_{E_{0}}(X)}=\mathbb{C}^{E_{0}}$ for any subset
$E_{0}\subseteq E$. Thus in this case every independent set of
$\mathcal{M}(X^{\prime})$ is also independent in $\mathcal{M}(X)$, or more
concisely, $\mathcal{M}(X^{\prime})\preceq\mathcal{M}(X)$.

The following folklore result relates the algebraic matroid of $X$ to the
algebraic matroid of its tangent space at a suitable point. This connection
will be of central importance in this paper.

######  Theorem 2.9.

If $X\subseteq\mathbb{C}^{E}$ is an irreducible affine variety, then
$\mathcal{M}(X)=\mathcal{M}(T_{x}(X))$ holds for a nonempty Zariski open
subset of points $x\in X$. If $X$ is defined over $\mathbb{Q}$, then
$\mathcal{M}(X)=\mathcal{M}(T_{x}(X))$ holds for every $X$-generic point $x$.

###### Proof.

Note that the projection $\pi_{E_{0}}:X\rightarrow\mathbb{C}^{E_{0}}$ is a
linear mapping and hence it coincides with its differential at any point. Let
$X_{E_{0}}$ denote $\overline{\pi_{E_{0}}(X)}$. It follows by Theorem 2.1 that
there is a nonempty Zariski open subset $X^{\prime}$ of points $x\in X$ for
which the projection $\pi_{E_{0}}:T_{x}{X}\rightarrow
T_{\pi_{E_{0}}(x)}(X_{E_{0}})$ is surjective for every subset $E_{0}\subseteq
E$. Since $X_{E_{0}}=\mathbb{C}^{E_{0}}$ if and only if the tangent space of
$X_{E_{0}}$ at some smooth point is all of $\mathbb{C}^{E_{0}}$, it follows
that for every $x\in X^{\prime}$ we have
$\mathcal{M}(X)=\mathcal{M}(T_{x}(X))$. The statement for generic points is
proved in the same way by using Lemma 2.6(d) instead of Theorem 2.1. ∎

We shall often consider algebraic matroids of linear spaces. Unsurprisingly,
such matroids can also be viewed as linear matroids, as described by the
following lemma.

######  Lemma 2.10.

Let $X\subseteq\mathbb{C}^{E}$ be a linear space.

  1. (a)

If $M$ is any $|E|\times k$ matrix whose columns span $X$, then
$\mathcal{M}(X)$ is the linear matroid (over $\mathbb{C}$) defined by the rows
of $M$.

  2. (b)

We have $\mathcal{M}(X^{\perp})=\mathcal{M}(X)^{*}$, where
$X^{\perp}=\\{y\in\mathbb{C}^{E}:\sum_{e\in E}x_{e}y_{e}=0\,\,\forall x\in
X\\}$ is the orthogonal complement of $X$.

###### Proof.

(a) Since $X$ is linear, a subset $E_{0}\subseteq E$ is independent in
$\mathcal{M}(X)$ if and only if the projection of $X$ to $\mathbb{C}^{E_{0}}$
is surjective. This projection is the same as the image of the matrix
$M_{E_{0}}$ that consists of the rows of $M$ corresponding to $E_{0}$. Thus
the projection is surjective if and only if $M_{E_{0}}$ has full row rank,
which is equivalent to $E_{0}$ being independent in the linear matroid defined
by the rows of $M$. (b) This now follows from the well-known fact that the
linear matroid of a vector space is dual to the linear matroid of the
orthogonal complement of the vector space, see, e.g., [28, Section 2.2]. ∎

The following lemma strengthens Lemma 2.7 for algebraic matroids of linear
spaces.

######  Lemma 2.11.

Let $X\subseteq\mathbb{C}^{E}$ be a linear space, and $E_{0}\subseteq E$. The
following are equivalent.

  1. (a)

The fiber of $\pi_{E_{0}}$ over $\pi_{E_{0}}(x)$ is a singleton for every
$x\in X$.

  2. (b)

$E_{0}$ is spanning in $\mathcal{M}(X)$.

  3. (c)

The fiber of $\pi_{E_{0}}$ over $\pi_{E_{0}}(x)$ is a singleton for some $x\in
X$.

###### Proof.

This follows from Lemma 2.7 and the observation that
$\pi_{E_{0}}:X\rightarrow\pi_{E_{0}}(X)$ is a linear transformation and hence
its fibers are pairwise isomorphic affine subspaces. ∎

###  2.4 The rigidity matroid

In this subsection we recall the basic notions of combinatorial rigidity
theory. This exposition is nonstandard for two (related) reasons: we work over
the complex field $\mathbb{C}$ instead of $\mathbb{R}$, and we mainly work
with the algebraic representation of the rigidity matroid given by the
measurement variety, rather than the linear representation given by the
rigidity matrix of a generic realization.

####  2.4.1 Basic notions

Let $G=(V,E)$ be a graph on $n$ vertices and let $d\geq 1$ be an integer.
Given a function $p:V\rightarrow\mathbb{C}^{d}$ we say that the pair $(G,p)$
is a _realization_ of $G$ in $\mathbb{C}^{d}$, or that $(G,p)$ is a
_framework_ in $\mathbb{C}^{d}$. We identify the set of functions
$V\rightarrow\mathbb{C}^{d}$ with $\mathbb{C}^{nd}$ and call the elements of
this space _configurations_ of $V$. If
$p\in\mathbb{R}^{nd}\subseteq\mathbb{C}^{nd}$, then we say that $(G,p)$ is a
realization in $\mathbb{R}^{d}$. A framework $(G,p)$ in $\mathbb{C}^{d}$ is
_generic_ if $p$ is $\mathbb{C}^{nd}$-generic. This means that the coordinates
of $p$ do not satisfy any nonzero polynomial with rational coefficients.

For a pair of vertices $u,v\in V$ we let the “distance map”
$m_{uv}:\mathbb{C}^{nd}\rightarrow\mathbb{C}$ be

$m_{uv}(p)=\sum_{i=1}^{d}(p(u)_{i}-p(v)_{i})^{2},$

and we define the _edge measurement map_
$m_{d,G}:\mathbb{C}^{nd}\rightarrow\mathbb{C}^{E}$ as

$m_{d,G}(p)=(m_{uv}(p))_{uv\in E}.$

Two realizations $(G,p)$ and $(G,q)$ in $\mathbb{C}^{d}$ are _equivalent_ if
$m_{d,G}(p)=m_{d,G}(q)$.

The _$d$ -dimensional measurement variety_ of $G$, denoted by $M_{d,G}$, is
the Zariski closure of $m_{d,G}(\mathbb{C}^{nd})$. This is an irreducible
affine variety, and by Proposition 2.3 it is defined over $\mathbb{Q}$. Since
the coordinate functions of $m_{d,G}$ are homogeneous polynomials, $M_{d,G}$
is also homogeneous. The _( $d$-dimensional generic) rigidity matroid_ of $G$,
which we denote by $\mathcal{R}_{d}(G)$, is the algebraic matroid
$\mathcal{M}(M_{d,G})$ associated to $M_{d,G}$. We use $r_{d}(G)$ to denote
the rank of $\mathcal{R}_{d}(G)$, which is equal to the dimension of
$M_{d,G}$. We say that $G$ is _$\mathcal{R}_{d}$ -independent_ if
$r_{d}(G)=|E(G)|$, and that it is an _$\mathcal{R}_{d}$ -circuit_ if it is not
$\mathcal{R}_{d}$-independent but every proper subgraph of $G$ is
$\mathcal{R}_{d}$-independent. The graph $G$ is _$d$ -rigid_ if $E$ is
spanning in $\mathcal{R}_{d}(K_{V})$, the rigidity matroid of the complete
graph on $V$. When $n\geq d+1$, this is equivalent to the condition that
$r_{d}(G)=nd-\binom{d+1}{2}$. (If $n\leq d+1$, then $G$ is $d$-rigid if and
only if it is a complete graph.) An edge $e$ of $G$ is an _$\mathcal{R}_{d}$
-bridge_ if $r_{d}(G)=r_{d}(G-e)+1$, or equivalently if $e$ is not contained
in any subgraph of $G$ that is an $\mathcal{R}_{d}$-circuit. A pair of
vertices $\\{u,v\\}$ is _$\mathcal{R}_{d}$ -linked_ in $G$ if
$r_{d}(G+uv)=r_{d}(G)$. When $u$ and $v$ are nonadjacent in $G$, this means
that there is an $\mathcal{R}_{d}$-circuit in $G+uv$ that contains the edge
$uv$, or equivalently that $uv$ is not an $\mathcal{R}_{d}$-bridge in $G+uv$.
We say that $G$ is _$\mathcal{R}_{d}$ -connected_ if $\mathcal{R}_{d}(G)$ is
connected. The _$\mathcal{R}_{d}$ -connected components_ of $G$ are the
subgraphs induced by the connected components of $\mathcal{R}_{d}(G)$.

####  2.4.2 Small separators

We will need the following “gluing lemma” of Whiteley.

######  Lemma 2.12.

[35, Lemma 11.1.9] Let $G$ be the union of the graphs $G_{1}$ and $G_{2}$.

  1. (a)

If $|V(G_{1})\cap V(G_{2})|\geq d$ and $G_{1}$ and $G_{2}$ are both $d$-rigid,
then $G$ is $d$-rigid.

  2. (b)

If $G_{1}\cap G_{2}$ is $d$-rigid and $G_{1}$ and $G_{2}$ are both
$\mathcal{R}_{d}$-independent, then $G$ is $\mathcal{R}_{d}$-independent.

  3. (c)

If $|V(G_{1})\cap V(G_{2})|\leq d-1,u\in V(G_{1})-V(G_{2})$ and $v\in
V(G_{2})-V(G_{1})$, then $\\{u,v\\}$ is not $\mathcal{R}_{d}$-linked in $G$.

The following is a well-known consequence of Lemma 2.12(b).

######  Lemma 2.13.

If $C=(V,E)$ is an $\mathcal{R}_{d}$-circuit, then $C$ is $2$-connected, and
furthermore if $u,v\in V$ is separating vertex pair, then $uv\notin E$.

Let $G$ be a graph and let $u,v\in V(G)$ be a nonadjacent separating pair of
vertices. We say that the graphs $G_{1},G_{2}$ are obtained by a _$2$
-separation of $G$ along $\\{u,v\\}$_ if $V(G_{1})\cap V(G_{2})=\\{u,v\\}$,
$uv\in E(G_{1})\cap E(G_{2})$ and $G=G_{1}\cup G_{2}-uv$. (The inverse
operation, where we glue a pair of graphs $G_{1}$ and $G_{2}$ along a pair of
edges and then delete the identified edge, is called taking the _$2$ -sum_ of
$G_{1}$ and $G_{2}$.)

######  Lemma 2.14.

([9, Lemma 4.9] and [15, Lemma 10] (see also [32, Theorem 1])) Let $G$ be a
graph, $u,v\in V(G)$ a separating vertex pair with $uv\notin E(G)$ and let
$G_{1},G_{2}$ be obtained by a $2$-separation of $G$ along $\\{u,v\\}$. The
following are equivalent.

  1. (a)

$G_{1}$ and $G_{2}$ are both $\mathcal{R}_{d}$-connected;

  2. (b)

$G$ is $\mathcal{R}_{d}$-connected;

  3. (c)

$G+uv$ is $\mathcal{R}_{d}$-connected.

Moreover, $G$ is an $\mathcal{R}_{d}$-circuit if and only if $G_{1}$ and
$G_{2}$ are both $\mathcal{R}_{d}$-circuits.

####  2.4.3 Equilibrium stresses

Let $(G,p)$ be a framework in $\mathbb{C}^{d}$. The _rigidity matrix_ of
$(G,p)$, denoted by $R(G,p)\in\mathbb{C}^{|E|\times nd}$, is the Jacobian of
$m_{d,G}$ evaluated at $p$. By combining Lemma 2.6(d), Theorem 2.9 and Lemma
2.10(a) we obtain that for any generic $(G,p)$, the row matroid of $R(G,p)$ is
$\mathcal{R}_{d}(G)$. (This is commonly taken as the definition of
$\mathcal{R}_{d}(G)$.)

A vector $\omega\in\mathbb{C}^{E}$ is an _equilibrium stress_ , or simply a
_stress_ of $(G,p)$ if $\omega^{T}R(G,p)=0$, that is, $\omega$ lies in the
cokernel of $R(G,p)$. The stresses of $(G,p)$ form a linear space $S(G,p)$
called the _space of stresses_ of $(G,p)$. The next lemma gives a geometric
interpretation of $S(G,p)$ for generic frameworks.

######  Lemma 2.15.

(E.g., [12, Lemma 2.21]) If $(G,p)$ be a generic framework in $\mathbb{C}^{d}$
and $x=m_{d,G}(p)$, then $S(G,p)=T_{x}(M_{d,G})^{\perp}$. That is, $S(G,p)$ is
the set of hyperplanes tangent to $x$ at $M_{d,G}$.

###### Proof.

The space of stresses is just the cokernel of $R(G,p)$, which by elementary
linear algebra is the orthogonal complement of the column space of $R(G,p)$.
Since $(G,p)$ is generic, by Lemma 2.6(d) this column space is precisely the
tangent space $T_{x}(M_{d,G})$. ∎

When expanded, the condition $\omega R(G,p)=0$ yields the _equilibrium
conditions_ stating that for every vertex $v\in V$,

$\sum_{uv\in E}\omega(uv)(p(u)-p(v))=0.$

This formulation highlights the important fact that given a vector
$\omega\in\mathbb{C}^{E}$, the set

$K_{{d},{G}}(\omega)=\\{p\in\mathbb{C}^{nd}:\omega\text{ is a stress of
}(G,p)\\}$

is a linear space. We call $K_{{d},{G}}(\omega)$ the _( $d$-dimensional)
stress kernel_ of $\omega$.222We note that in [12], the name “stress kernel”
was reserved for what we call the one-dimensional stress kernel, and the
$d$-dimensional stress kernel was called the space of “stress satisfiers.”
This space will play an important role throughout this paper. Since every
equilibrium condition gives an independent condition for each of the $d$
coordinate vectors of $p$, we have
$K_{{d},{G}}(\omega)=(K_{{1},{G}}(\omega))^{d}$ as linear spaces. If $(G,p)$
is in affine general position, then the coordinate vectors of $p$ and the all
ones vector form a linearly independent set contained in
$K_{{1},{G}}(\omega)$, so in this case we have $\dim(K_{{1},{G}}(\omega))\geq
d+1$. It is also clear that the equilibrium conditions are preserved under
affine transformations, and hence we have $A(G,p)\subseteq
K_{{d},{G}}(\omega)$, where $A(G,p)$ denotes the set of configurations arising
as affine images of $(G,p)$.

Combining Lemma 2.6(e) with Lemma 2.15 we obtain the following result that was
originally proved by Connelly in the real setting.

######  Theorem 2.16.

([4]) Let $(G,p)$ and $(G,q)$ be equivalent frameworks in $\mathbb{C}^{d}$. If
$(G,p)$ is generic, then $S(G,p)=S(G,q)$.

The following lemma collects some useful observations about the space of
stresses of graphs with small separators. Some of these may be considered
folklore. For completeness, we give a proof in Section A.

######  Lemma 2.17.

Let $G$ be the union of the induced subgraphs
$G_{1}=(V_{1},E_{1}),G_{2}=(V_{2},E_{2})$. Consider a realization $(G,p)$ in
$\mathbb{C}^{d}$ and let $(G_{i},p_{i})$ be the subframeworks corresponding to
$G_{i}$ for $i\in\\{1,2\\}$. Finally, let $S_{i}$ be the subspace of $S(G,p)$
of stresses supported on $E_{i}$, for $i\in\\{1,2\\}$.

  1. (a)

If $(G,p)$ is generic and $G_{1}\cap G_{2}$ is $d$-rigid, then $S_{1}\cup
S_{2}$ generates $S(G,p)$.

  2. (b)

Suppose that $(G_{i},p_{i})$ is generic for both $i\in\\{1,2\\}$, $|V_{1}\cap
V_{2}|\leq d+1$, and for every pair of vertices $u,v\in V_{1}\cap V_{2}$,
either $uv\in E$ or $\\{u,v\\}$ is $\mathcal{R}_{d}$-linked in precisely one
of $G_{1}$ and $G_{2}$. Then $S(G,p)=S_{1}\oplus S_{2}$.

  3. (c)

If $(G_{i},p_{i})$ is generic for both $i\in\\{1,2\\}$ and $V_{1}\cap
V_{2}=\\{u,v\\}$, where $\\{u,v\\}$ is $\mathcal{R}_{d}$-linked in at most one
of $G_{1}$ and $G_{2}$, then $S(G,p)=S_{1}\oplus S_{2}$.

####  2.4.4 Globally linked pairs and global rigidity

A pair of vertices $\\{u,v\\}$ is _globally linked in $G$ in $\mathbb{C}^{d}$_
if whenever $(G,p)$ is a generic realization and $(G,q)$ is equivalent to
$(G,p)$, we have $m_{uv}(p)=m_{uv}(q)$, or in other words, $(G+uv,p)$ and
$(G+uv,q)$ are also equivalent. Although we shall not use it, we note that
being globally linked in $\mathbb{C}^{d}$ has another natural interpretation:
it means that there is a rational function
$F:\mathbb{C}^{E(G)}\dashrightarrow\mathbb{C}$ with rational coefficients such
that $m_{uv}(p)=F(m_{d,G}(p))$ for any generic realization $(G,p)$ in
$\mathbb{C}^{d}$.

Similarly, a pair of vertices $\\{u,v\\}$ is _globally linked in $G$ in
$\mathbb{R}^{d}$_ if whenever $(G,p)$ is a generic realization in
$\mathbb{R}^{d}$ and $(G,q)$ is another realization in $\mathbb{R}^{d}$
equivalent to $(G,p)$, we have $m_{uv}(p)=m_{uv}(q)$. Being globally linked in
$G$ in $\mathbb{C}^{d}$ clearly implies being globally linked in $G$ in
$\mathbb{R}^{d}$, and it is unclear whether the two notions are in fact
equivalent. We note that (in contrast with the complex case) it can happen
that the condition in the definition of being globally linked in
$\mathbb{R}^{d}$ only holds for some, but not all generic realizations of $G$
in $\mathbb{R}^{d}$. If this is the case, then $\\{u,v\\}$ is said to be
_weakly globally linked in $G$ in $\mathbb{R}^{d}$_; see [26] for recent
results regarding this notion.

Interestingly, the three notions of “being globally linked” are known to be
equivalent when we require them to hold for all pairs of vertices.

######  Theorem 2.18.

([26, Lemma 3.2] and [14, Theorem 1]) The following are equivalent for a graph
$G$.

  1. (a)

Every pair of vertices is weakly globally linked in $G$ in $\mathbb{R}^{d}$.

  2. (b)

Every pair of vertices is globally linked in $G$ in $\mathbb{R}^{d}$.

  3. (c)

Every pair of vertices is globally linked in $G$ in $\mathbb{C}^{d}$.

If any of the above three equivalent conditions holds, then we say that $G$ is
_globally $d$-rigid_. By unraveling condition (c) we arrive at the definition
that for every generic realization $(G,p)$ in $\mathbb{C}^{d}$, if $(G,q)$ is
an equivalent framework in $\mathbb{C}^{d}$, then
$m_{d,K_{V}}(p)=m_{d,K_{V}}(q)$, where $K_{V}$ is the complete graph on vertex
set $V=V(G)$.

As we noted in the Introduction, it is a folklore result that a graph is
globally $1$-rigid if and only if it is $2$-connected. The combinatorial
characterization of globally $2$-rigid graphs is due to Jackson and Jordán. We
will need the following form of their result.

######  Theorem 2.19.

([19], see also [21, Theorem 5.1]) Let $G$ be a graph on at least four
vertices. The following are equivalent.

  1. (a)

$G$ is globally $2$-rigid.

  2. (b)

$G$ is $3$-connected and $\mathcal{R}_{2}$-connected.

  3. (c)

$G$ is $3$-connected and does not contain $\mathcal{R}_{2}$-bridges.

One of the main results of [12] is the following characterization of globally
$d$-rigid graphs. The original result was stated for real frameworks, and
subsequently in [14] it was extended to the complex setting. It is often
formulated in terms of the maximum rank of stress matrices, but the following
equivalent form will be more convenient for us. Recall that we use
$K_{{d},{G}}(\omega)$ to denote the $d$-dimensional stress kernel of $\omega$,
while $A(G,p)$ denotes the set of affine images of $(G,p)$.

######  Theorem 2.20.

([12], see also [14, Theorem 1]) Let $G$ be a graph and $(G,p)$ a generic
realization in $\mathbb{C}^{d}$. Then $G$ is globally $d$-rigid if and only if
there is a stress $\omega\in S(G,p)$ for which $K_{{d},{G}}(\omega)=A(G,p)$.

We note that in [12], another characterization of globally $d$-rigid graphs
was given in terms of the “shared stress kernel” instead of the stress kernel.
We postpone the introduction of shared stress kernels and this result until
Section 4, where they shall play an important role.

##  3 The generic stress matroid

In this section we introduce and study the $d$-dimensional generic stress
variety of $G$, which is the dual variety of the measurement variety of $G$.
As the name suggests, the generic stress variety describes the global geometry
of equilibrium stresses of generic realizations. We shall be particularly
interested in the coordinate projections of this variety, and hence we will
study its algebraic matroid, which we call the $d$-dimensional generic stress
matroid of $G$.

Motivated by possible applications in other areas, in Section 3.1 we recall
the notion of the dual variety and consider the associated “algebraic dual
matroid” in a general setting. While the duality theory of varieties is a
well-studied topic, we are not aware of other works that consider duality from
the perspective of algebraic matroids. In Section 3.3 we specialize to the
setting of rigidity theory and consider the algebraic dual matroid of the
rigidity matroid (as represented by the measurement variety). In particular,
we obtain some results about the independent sets and the spanning sets of
this matroid which we will use in our investigation of ${d}$-stress-linked
vertex pairs in the next section. Before this, in Section 3.2 we briefly
consider another matroid which we call the affine edge measurement matroid of
$G$. The significance of this matroid will become apparent in Section 3.3
where we show, essentially by rephrasing Theorem 2.20, that whenever $G$ is
globally $d$-rigid, the affine edge measurement matroid of $G$ is the dual of
the stress matroid of $G$.

###  3.1 The algebraic dual matroid

We start by defining the dual variety and stating the reflexivity theorem
along with some of its consequences. A good reference on this topic is [7,
Chapter 2], with the caveat that the authors use the language of projective
varieties, while we are working with the affine cones of such varieties.

Let $X\subseteq\mathbb{C}^{E}$ be an irreducible homogeneous affine variety.
The _conormal bundle_ $C_{X}\subseteq\mathbb{C}^{E}\times\mathbb{C}^{E}$ of
$X$ is the Zariski closure of

$\\{(x,\omega):x\in X\text{ is smooth and }\omega\text{ is a tangent
hyperplane of }X\text{ at }x\\}.$

This is an irreducible affine variety of dimension $|E|$. Let $\pi_{1}$ and
$\pi_{2}$ denote the projection of $\mathbb{C}^{E}\times\mathbb{C}^{E}$ onto
the first and second factor, respectively. It is known that for every smooth
point $x\in X$,

$\pi_{2}(\pi_{1}^{-1}(x))=T_{x}(X)^{\perp},$ (1)

see [7, Section 2.1.4]. In other words, taking the Zariski closure in the
definition of $C_{X}$ does not add new points over smooth points of $X$. The
_dual variety_ of $X$ is defined as $X^{*}=\overline{\pi_{2}(C_{X})}.$ This is
a homogeneous irreducible affine variety in $\mathbb{C}^{E}$. It can be more
concretely described as the Zariski closure of

$\bigcup\left\\{T_{x}(X)^{\perp}:x\in X\text{ is a smooth point}\right\\}.$
(2)

In general, we have the inequalities $|E|-\dim(X)\leq\dim X^{*}\leq|E|-1,$
where the first inequality is strict whenever $X$ does not lie in a linear
hyperplane of $\mathbb{C}^{E}$.

The _reflexivity theorem_ states that $C_{X^{*}}$, the conormal bundle of
$X^{*}$, is the same as $C_{X}$ with the two factors switched around:

$C_{X^{*}}=\overline{\\{(\omega,x):x\in X\text{ is smooth and }\omega\text{ is
a tangent hyperplane of }X\text{ at }x\\}.}$

This implies in particular that $(X^{*})^{*}=X$. For a smooth point $\omega\in
X^{*}$, the _contact locus_ of $\omega$ in $X$ is

$L_{X}(\omega)=\overline{\\{x\in X:x\text{ is smooth and }\omega\text{ is a
tangent hyperplane of }X\text{ at }x\\}}.$

It follows from the reflexivity theorem and 1 that
$L_{X}(\omega)=T_{\omega}(X^{*})^{\perp}$. In particular, $L_{X}(\omega)$ is a
linear space of dimension $|E|-\dim(X^{*})$; this is sometimes called the
_linearity theorem_.

The following lemma shows that if an affine variety is defined over
$\mathbb{Q}$, then so is its dual. Its importance in our case will be that it
lets us work with generic points of the dual variety. We give a proof sketch
in the Appendix.

######  Lemma 3.1.

If $X$ is defined over $\mathbb{Q}$, then so are $C_{X}$ and $X^{*}$. In this
case $X^{*}$ can be written as the closure of

$\bigcup\left\\{T_{x}(X)^{\perp}:x\in X\text{ is }X\text{-generic}\right\\}.$
(3)

Whenever $\omega\in X^{*}$ is $X^{*}$-generic, there is a $C_{X}$-generic pair
$(x,\omega)$. For every such pair, $x$ is $X$-generic and $\omega\in
T_{x}(X)^{\perp}$.

We define the _algebraic dual matroid_ of $\mathcal{M}(X)$ to be
$\mathcal{M}(X^{*})$. Note that the algebraic dual is determined not by the
matroid $\mathcal{M}(X)$, but rather its algebraic representation $X$. The
rank of the algebraic dual matroid is $\dim(X^{*})$. If $X$ does not lie in a
linear hyperplane, then
$\dim(X^{*})\geq|E|-\dim(X)+1=\operatorname{rk}(\mathcal{M}(X)^{*})+1$, which
shows that in general $\mathcal{M}(X^{*})$ is not the dual matroid of
$\mathcal{M}(X)$. On the other hand, since $(X^{*})^{*}=X$, the algebraic dual
of $\mathcal{M}(X^{*})$ is $\mathcal{M}(X)$, which is why we use the term
“dual” for this construction. We note that if $X$ is a linear space, then
$X^{*}=X^{\perp}$ and hence by Lemma 2.10 we have
$\mathcal{M}(X^{*})=\mathcal{M}(X^{\perp})=\mathcal{M}(X)^{*}$. That is, for
linear spaces the algebraic dual matroid does coincide with the dual matroid.

The following theorem highlights another connection between $\mathcal{M}(X)$
and its algebraic dual. It follows almost immediately from Theorem 2.9.
Nonetheless, it turns out to be of central importance in this paper.

######  Theorem 3.2.

Let $X\subseteq\mathbb{C}^{E}$ be an irreducible homogeneous affine variety
defined over $\mathbb{Q}$, and let $\omega\in X^{*}$ be a generic point of the
dual variety. Then $\mathcal{M}(L_{X}(\omega))=\mathcal{M}(X^{*})^{*}$. That
is, the algebraic matroid of the contact locus of $\omega$ is the dual matroid
of $\mathcal{M}(X^{*})$.

###### Proof.

Recall that $L_{X}(\omega)=T_{\omega}(X^{*})^{\perp}$. Lemma 2.10(b) implies
that $\mathcal{M}(L_{X}(\omega))$ is the dual matroid of
$\mathcal{M}(T_{\omega}(X^{*}))$, and it follows from Theorem 2.9 that the
latter is just $\mathcal{M}(X^{*})$. ∎

######  Corollary 3.3.

Let $X\subseteq\mathbb{C}^{E}$ be an irreducible homogeneous affine variety.
We have $\mathcal{M}(X)^{*}\preceq\mathcal{M}(X^{*})$, and similarly
$\mathcal{M}(X^{*})^{*}\preceq\mathcal{M}(X)$.

###### Proof.

We repeat the previous proof for $X$ instead of $X^{*}$. By Theorem 2.9 there
is some smooth point $x\in X$ such that
$\mathcal{M}(X)=\mathcal{M}(T_{x}(X)).$ By Lemma 2.10 we thus have
$\mathcal{M}(X)^{*}=\mathcal{M}(T_{x}(X)^{\perp})$. But from 2 we have
$T_{x}(X)^{\perp}\subseteq X^{*},$ and hence
$\mathcal{M}(T_{x}(X)^{\perp})\preceq\mathcal{M}(X^{*})$. The other statement
follows from duality. ∎

It is a standard result that for a matroid $\mathcal{M}$ on ground set $E$, a
bipartition $(E_{1},E_{2})$ of $E$ is a separation of $\mathcal{M}$ if and
only if it is a separation of the dual matroid $\mathcal{M}^{*}$. The
following proposition is the analogous statement for the algebraic dual
matroid.

######  Proposition 3.4.

Let $X$ be an irreducible homogeneous affine variety in $\mathbb{C}^{E}$ and
$E=E_{1}\cup E_{2}$ a bipartition of $E$. Then $(E_{1},E_{2})$ is a separation
of $\mathcal{M}(X)$ if and only if $(E_{1},E_{2})$ is a separation of
$\mathcal{M}(X^{*})$. Moreover, if $(E_{1},E_{2})$ is a separation of
$\mathcal{M}(X)$, then $X^{*}=(X_{E_{1}})^{*}\times(X_{E_{2}})^{*}$, where
$X_{E_{i}}=\overline{\pi_{E_{i}}(X)}$ is the projection of $X$ onto
$\mathbb{C}^{E_{i}}$.

Note that by Lemma 2.8, if $(E_{1},E_{2})$ is a separation of
$\mathcal{M}(X^{*})$, then $X^{*}=(X^{*})_{E_{1}}\times(X^{*})_{E_{2}}$, where
the subscripts again mean that we take the Zariski closure of the projection.
However, it is a priori not clear whether $(X^{*})_{E_{i}}=(X_{E_{i}})^{*}$
holds, and indeed, this is not true in general. We shall show that when
$(E_{1},E_{2})$ is a separation of $\mathcal{M}(X)$, then this equality does
hold.

###### Proof of Proposition 3.4.

By symmetry it is enough to show the “only if” direction. Let us suppose that
$(E_{1},E_{2})$ is a separation of $\mathcal{M}(X)$. From Lemma 2.8 we have
$X=X_{E_{1}}\times X_{E_{2}}$. This means that if $X_{E_{1}}$ is defined by
the polynomials $f_{1},\ldots,f_{k}$ in variables $x_{e},e\in E_{1}$ and
$X_{E_{2}}$ is defined by the polynomials $g_{1},\ldots,g_{l}$ in variables
$y_{e},e\in E_{2}$, then $X$ is defined by the polynomials
$f_{1},\ldots,f_{k},g_{1},\ldots,g_{l}$. It follows from the definitions now
that for every smooth point $x=(x_{1},x_{2})\in X$ we have
$T_{x}(X)=T_{x_{1}}(X_{E_{1}})\times T_{x_{2}}(X_{E_{2}})$ and thus
$T_{x}(X)^{\perp}=T_{x_{1}}(X_{E_{1}})^{\perp}\times
T_{x_{2}}(X_{E_{2}})^{\perp}$. Combined with the fact that
$\dim(X)=\dim(X_{E_{1}})+\dim(X_{E_{2}})$ this also shows that
$x=(x_{1},x_{2})$ in $X$ is smooth if and only if $x_{i}$ is smooth in
$X_{E_{i}}$ for $i\in\\{1,2\\}$.

Let us denote the set of smooth points in $X_{i}$ by $\text{Sm}(X_{i})$. From
2 it follows that $X^{*}$ is the Zariski closure of
$\bigcup\\{T_{x}(X)^{\perp}:x\in X\text{ is a smooth point}\\}.$ By the
discussion in the preceding paragraph, this set can be also written as

$\displaystyle\bigcup\left\\{T_{x_{1}}(X_{E_{1}})^{\perp}\times
T_{x_{2}}(X_{E_{2}})^{\perp}:x_{i}\in\text{Sm}(X_{i}),i\in\\{1,2\\}\right\\}$
$\displaystyle=\bigcup\left\\{T_{x_{1}}(X_{E_{1}})^{\perp}:x_{1}\in\text{Sm}(X_{1})\right\\}\times\bigcup\left\\{T_{x_{2}}(X_{E_{2}})^{\perp}:x_{2}\in\text{Sm}(X_{2})\right\\}.$

Using 2 and the well-known fact that the Zariski closure of a Cartesian
product of two sets is the Cartesian product of the respective Zariski
closures, we obtain $X^{*}=(X_{E_{1}})^{*}\times(X_{E_{2}})^{*}$. This implies
that $(X^{*})_{E_{i}}=(X_{E_{i}})^{*}$ for $i\in\\{1,2\\}$, and now Lemma 2.8
shows that $(E_{1},E_{2})$ is a separation of $\mathcal{M}(X^{*})$. This
proves the “only if” direction, while the other direction follows by symmetry.
∎

######  Corollary 3.5.

([7, Section 2.2.6]) Let $X$ be an irreducible homogeneous affine variety in
$\mathbb{C}^{E}$ and $e\in E$. Then $e$ is a bridge in $\mathcal{M}(X)$ if and
only if it is a loop in $\mathcal{M}(X^{*})$.

###### Proof.

By Lemma 2.8 we have $X=X_{E-e}\times\mathbb{C}$. Since the dual of
$\mathbb{C}$ (as a subvariety of $\mathbb{C}$) is the single point $\\{0\\}$,
Proposition 3.4 implies that $X^{*}=X^{*}_{E-e}\times\\{0\\}$, so $e$ is a
loop in $\mathcal{M}(X^{*})$. Conversely, if $e$ is a loop in
$\mathcal{M}(X^{*})$, then the projection of $X^{*}$ onto the coordinate axis
of $e$ is a zero-dimensional homogeneous variety, so it must be the singleton
$\\{0\\}$. Hence we have $X^{*}=X^{*}_{E-e}\times\\{0\\}$, and it follows from
Lemmas 2.8 and 3.4 again $e$ is a bridge in $\mathcal{M}(X)$. ∎

###  3.2 The affine edge measurement matroid

Our goal is to investigate the algebraic dual matroid of the generic rigidity
matroid $\mathcal{R}_{d}(G)=\mathcal{M}(M_{d,G})$. Before that, we take a
brief detour to examine another matroid that we shall call the $d$-dimensional
affine edge measurement matroid of $G$. This matroid will play an important
role in the next subsection.

Let $G$ be a graph on $n$ vertices and $(G,p)$ a realization in
$\mathbb{C}^{d}$ such that the configuration $p$ is in affine general
position. Recall that we use $A(G,p)\subseteq\mathbb{C}^{nd}$ to denote the
linear space of (possibly singular) affine images of $p$. Since $p$ is in
affine general position and an affine transformation is uniquely determined by
its image on $d+1$ points in general position, we have
$\dim(A(G,p))=d\cdot\min(d+1,n)$.

Let $B(G,p)=m_{d,G}(A(G,p))$ be the space of edge measurements of affine
images of $(G,p)$. It turns out that $B(G,p)$ is also a linear space, which we
can describe concretely. Let us define the edge vectors $e_{uv}=p(u)-p(v)$ for
each $uv\in E$. Note that $e_{uv}$ is only defined up to sign; to be more
precise, we could take an arbitrary orientation of $G$ and define $e_{uv}$
using this orientation. Finally, let us denote the space of symmetric $d\times
d$ matrices over $\mathbb{C}$ by $\text{Sym}(\mathbb{C}^{d\times d})$.

######  Lemma 3.6.

[13, Lemma 4.6] Let $(G,p)$ and $e_{uv},uv\in E$ be as in the preceding
discussion. Then

$B(G,p)=\\{(e_{uv}^{T}Qe_{uv})_{uv\in E}:Q\in\text{Sym}(\mathbb{C}^{d\times
d})\\}.$

In particular, $B(G,p)$ is a linear space of dimension at most
$\binom{d+1}{2}$.

We say that _the edge directions of $(G,p)$ lie on a conic at infinity_ if
there is a nonzero symmetric matrix $Q\in\text{Sym}(\mathbb{C}^{d\times d})$
such that $e_{uv}^{T}Qe_{uv}=0$ for every $uv\in E$. This means that the
linear mapping $Q\mapsto(e_{uv}^{T}Qe_{uv})_{uv\in E}$ is singular, which by
Lemma 3.6 is equivalent to the condition that $\dim(B(G,p))<\binom{d+1}{2}.$
The following is a classic result of Connelly. The original statement was for
frameworks in $\mathbb{R}^{d}$, but the same proof works for frameworks in
$\mathbb{C}^{d}$.

######  Proposition 3.7.

([4, Proposition 4.3]) Let $G$ be a graph. Suppose that $G$ has a subgraph
$G_{0}$ in which the degree of every vertex is at least $d$. Let $(G,p)$ be a
realization in $\mathbb{C}^{d}$. If $(G,p)$ is generic, then the edge
directions of $(G,p)$ do not lie on a conic at infinity.

######  Proposition 3.8.

Let $G$ be a graph. The matroid $\mathcal{M}(B(G,p))$ is the same for every
generic realization $(G,p)$ in $\mathbb{C}^{d}$. Its rank is at most
$\binom{d+1}{2}$, and is equal to $\binom{d+1}{2}$ if $G$ is not
$\mathcal{R}_{d}$-independent.

###### Proof.

Recall that by Lemma 2.10, the algebraic matroid of a linear space is the same
as the row matroid of any matrix whose columns span the space. By fixing a
basis of $\text{Sym}(\mathbb{C}^{d\times d})$ consisting of integer-valued
matrices and considering the linear transformation
$\text{Sym}(\mathbb{C}^{d\times d})\rightarrow B(G,p)$ described in Lemma 3.6
in this basis, we obtain a matrix $M(G,p)$ whose column space is $B(G,p)$.
Since the minors of $M(G,p)$ are polynomials with rational coefficients in the
coordinates of $p(v),v\in V(G)$, the rank of each submatrix of $M(G,p)$ is the
same for every generic choice of $p$, and thus so is the row matroid of
$M(G,p)$.

Recall that the rank of $\mathcal{M}(B(G,p))$ is just $\dim(B(G,p)$, which is
at most $\binom{d+1}{2}$ by Lemma 3.6. If $G$ is not
$\mathcal{R}_{d}$-independent, then it contains an $\mathcal{R}_{d}$-circuit
$C$ as a subgraph. It is well-known (and can be deduced from Lemma 2.12(c))
that such a graph has minimum degree at least $d+1$. Hence by Proposition 3.7,
the edge directions of $(G,p)$ do not lie on a conic at infinity for any
generic realization $(G,p)$. This means by Lemma 3.6 that $B(G,p)$ is linearly
isomorphic to the space of symmetric $d\times d$ matrices, which has dimension
$\binom{d+1}{2}$. ∎

Following Proposition 3.8, we define the _( $d$-dimensional generic) affine
edge measurement matroid_ of $G$, denoted by $\mathcal{A}_{d}(G)$, to be
$\mathcal{M}(B(G,p))$, where $(G,p)$ is any generic realization of $G$ in
$\mathbb{C}^{d}$. For us, the most important property of this matroid will be
the following.

######  Proposition 3.9.

Let $G$ be a graph and $E_{0}\subseteq E(G)$. If $E_{0}$ spans at most $d+1$
vertices, then it is independent in $\mathcal{A}_{d}(G)$.

###### Proof.

Let $G_{0}=G[E_{0}]$ and $k=|V(G_{0})|$. Consider a generic realization
$(G,p)$ of $G$ in $\mathbb{R}^{d}$ and let $(G_{0},p_{0})$ be the subframework
corresponding to $G_{0}$. Since $k\leq d+1$ and $(G_{0},p_{0})$ is generic, we
can map it to any configuration using affine transformations, so
$A(G_{0},p_{0})=\mathbb{C}^{kd}$. It is well-known (and can be deduced from
Lemma 2.12) that graphs on at most $d+1$ vertices are
$\mathcal{R}_{d}$-independent, so

$\overline{m_{d,G_{0}}(A(G_{0},p_{0}))}=\overline{m_{d,G_{0}}(\mathbb{C}^{kd})}=M_{d,G_{0}}=\mathbb{C}^{E_{0}}.$

But clearly

$\pi_{E_{0}}(B(G,p))=\pi_{E_{0}}(m_{d,G}(A(G,p)))=m_{d,G_{0}}(A(G_{0},p_{0})),$

so we have $\overline{\pi_{E_{0}}(B(G,p))}=\mathbb{C}^{E_{0}}$, which shows
that $E_{0}$ is independent in $\mathcal{M}(B(G,p))=\mathcal{A}_{d}(G)$. ∎

When $d=1$, Propositions 3.8 and 3.9 give a complete description of
$\mathcal{A}_{d}(G)$.

######  Corollary 3.10.

For any graph $G$, $\mathcal{A}_{1}(G)$ is the rank $1$ uniform matroid on
$E(G)$.

A computer-assisted computation shows that for $d\leq 4$, $\mathcal{A}_{d}(G)$
is the uniform matroid of rank $\binom{d+1}{2}$ for any graph with at least
$\binom{d+1}{2}$ edges. It is unclear if this holds for all $d$.

######  Conjecture 3.11.

If $G$ is a graph with at least $\binom{d+1}{2}$ edges, then
$\mathcal{A}_{d}(G)$ is the uniform matroid of rank $\binom{d+1}{2}.$

Recall that the rank of $\mathcal{A}_{d}(G)$ is $\binom{d+1}{2}$ if and only
if for generic realizations $(G,p)$ in $\mathbb{C}^{d}$, the edge directions
of $(G,p)$ do not lie on a conic at infinity. Hence 3.11 would imply a
strengthening of Proposition 3.7, namely that the edge directions of a generic
realization $(G,p)$ do not lie on a conic at infinity provided that $G$ has at
least $\binom{d+1}{2}$ edges.

###  3.3 The generic stress matroid

In this subsection we specialize the discussion of Section 3.1 to the
measurement variety $M_{d,G}$. We refer the reader to Figure 1 for a summary
of the different spaces and matroids considered throughout this subsection.

Let $G$ be a graph on $n$ vertices, $d\geq 1$ a fixed integer, and $(G,p)$ a
framework in $\mathbb{C}^{d}$. Recall that $S(G,p)$ denotes the linear space
of stresses of $(G,p)$, and that for a stress $\omega\in S(G,p)$, we use
$K_{{d},{G}}(\omega)\subseteq\mathbb{C}^{nd}$ to denote the stress kernel of
$\omega$, which is the linear space of configurations $q$ in $\mathbb{C}^{d}$
such that $\omega\in S(G,q)$. As we noted before, $A(G,p)\subseteq
K_{{d},{G}}(\omega)$ holds for any stress $\omega$.

Now let us consider the measurement variety. Recall that for a generic
realization $(G,p)$ with $x=m_{d,G}(p)$, we have
$S(G,p)=T_{x}(M_{d,G})^{\perp}$ by Lemma 2.15. Also, it follows from Lemma 2.5
that the $M_{d,G}$-generic points are precisely the images of generic
configurations under $m_{d,G}$. Thus by specializing 3 we can write the dual
variety $M_{d,G}^{*}$ as the Zariski closure of

$\bigcup\left\\{S(G,p):(G,p)\text{ is a generic framework in
}\mathbb{C}^{d}\right\\}.$ (4)

Based on 4, we shall call $M_{d,G}^{*}$ the _( $d$-dimensional generic) stress
variety_ of $G$, and we shall call $\mathcal{M}(M_{d,G}^{*})$ the _(
$d$-dimensional generic) stress matroid_ of $G$. That is, the $d$-dimensional
generic stress matroid, which we will denote by $\mathcal{S}_{d}(G)$, is the
algebraic dual matroid of $\mathcal{R}_{d}(G)=\mathcal{M}(M_{d,G})$.

Let us say that a vector $\omega\in\mathbb{C}^{E}$ is a _generic $d$-stress of
$G$_ if $\omega$ is $M_{d,G}^{*}$-generic. By specializing Lemma 3.1 to the
measurement variety, we obtain the following basic lemma, which we shall use
without reference in the rest of the paper.

######  Lemma 3.12.

Let $\omega\in\mathbb{C}^{E}$ be a generic $d$-stress of the graph $G$. Then
$\omega\in S(G,p)$ for some generic framework $(G,p)$ in $\mathbb{C}^{d}$.
Conversely, every generic framework $(G,p)$ in $\mathbb{C}^{d}$ has a generic
stress $\omega$.

As a weaker notion, we say that the vector $\omega\in\mathbb{C}^{E}$ is an
_almost generic $d$-stress of $G$_ if $\omega\in S(G,p)$ for some generic
framework $(G,p)$ in $\mathbb{C}^{d}$. When the dimension $d$ is clear from
the context, we shall sometimes wimply write generic stress and almost generic
stress, respectively. The description of the stress variety given by 4 shows
that every almost generic stress is contained in $M_{d,G}^{*}$. Note that if
$G$ is $\mathcal{R}_{d}$-independent, then $M_{d,G}^{*}=\\{0\\}$ and in this
case the only almost generic stress is the zero vector.

Next, we consider the _contact locus_

$L_{d,G}(\omega)=\overline{\\{x\in X:x\text{ is smooth and }\omega\in
T_{x}(M_{d,G})^{\perp}\\}}.$

By the general results of Section 3.1, whenever $\omega$ is a generic stress,
$L_{d,G}(\omega)$ is a linear space, and thus it is irreducible. The following
proposition describes how the contact locus of $\omega$ relates to the stress
kernel of $\omega$.

######  Lemma 3.13.

If $\omega$ is a generic $d$-stress of the graph $G$, then
$L_{d,G}(\omega)=\overline{m_{d,G}(K_{{d},{G}}(\omega))}$.

###### Proof.

Let $(G,p)$ be a generic framework in $\mathbb{C}^{d}$ with $\omega\in
S(G,p)$. By Lemma 2.5 $x=m_{d,G}(p)$ is an $M_{d,G}$-generic point, and
consequently it is a smooth point by Lemma 2.6(a). It follows from Lemma 2.15
that $x\in L_{d,G}(\omega)\subseteq M_{d,G}$. In particular, $L_{d,G}(\omega)$
contains an $M_{d,G}$-generic point. Now Lemma 2.4 implies that the
$M_{d,G}$-generic points are Zariski dense in $L_{d,G}(\omega)$, and hence we
can write

$L_{d,G}(\omega)=\overline{\\{m_{d,G}(p):(G,p)\text{ is generic and }p\in
K_{{d},{G}}(\omega)\\}}.$

Let us denote the set of generic configurations in $K_{{d},{G}}(\omega)$ by
$K_{{d},{G}}(\omega)^{g}$. Since $K_{{d},{G}}(\omega)$ is a linear space that
contains at least one generic configuration (namely, $p$), Lemma 2.4 implies
that $K_{{d},{G}}(\omega)=\overline{K_{{d},{G}}(\omega)^{g}}$. It follows that

$L_{d,G}(\omega)=\overline{m_{d,G}(K_{{d},{G}}(\omega)^{g})}=\overline{m_{d,G}(\overline{K_{{d},{G}}(\omega)^{g}})}=\overline{m_{d,G}(K_{{d},{G}}(\omega))},$

where the second equality uses the continuity of $m_{d,G}$. ∎

For convenience, we state the specialization of Theorem 3.2 to the measurement
variety as a separate theorem.

######  Theorem 3.14.

Let $\omega\in\mathbb{C}^{E}$ be a generic $d$-stress of the graph $G$. Then
$\mathcal{M}(L_{d,G}(\omega))=\mathcal{S}_{d}(G)^{*}$.

The following result reveals the connection between the affine edge
measurement matroid and the generic stress matroid. The second statement is
essentially a restatement of Theorem 2.20 based on the stress matroid.

######  Theorem 3.15.

We have $\mathcal{A}_{d}(G)\preceq\mathcal{S}_{d}(G)^{*}$ for any graph $G$.
If $G$ is $d$-rigid, then $\mathcal{A}_{d}(G)=\mathcal{S}_{d}(G)^{*}$ if and
only if $G$ is globally $d$-rigid.

###### Proof.

Let $\omega$ be a generic $d$-stress of $G$ and $(G,p)$ a generic framework in
$\mathbb{C}^{d}$ with $\omega\in S(G,p)$. Since $A(G,p)\subseteq
K_{{d},{G}}(\omega)$, we have (using Lemma 3.13)

$B(G,p)=m_{d,G}(A(G,p))\subseteq\overline{m_{d,G}(K_{{d},{G}}(\omega))}=L_{d,G}(\omega).$

Combined with Theorem 3.14 this implies

$\mathcal{A}_{d}(G)=\mathcal{M}(B(G,p))\preceq\mathcal{M}(L_{d,G}(\omega))=\mathcal{S}_{d}(G)^{*},$

as claimed.

Now suppose that $G$ is $d$-rigid. If $G$ is globally $d$-rigid, then we have
$A(G,p)=K_{{d},{G}}(\omega)$ by Theorem 2.20 and hence
$B(G,p)=L_{d,G}(\omega)$, so $\mathcal{A}_{d}(G)=\mathcal{S}_{d}(G)^{*}$.
Suppose now that $G$ is not globally $d$-rigid. By Theorem 2.20 we have
$A(G,p)\subsetneq K_{{d},{G}}(\omega)$, and in particular
$\dim(K_{{d},{G}}(\omega))>d(d+1)$. (Note that since $G$ is $d$-rigid but not
globally $d$-rigid, it necessarily has at least $d+2$ vertices.) We shall show
that $\dim(L_{d,G}(\omega))>d(d+1)-\binom{d+1}{2}=\binom{d+1}{2}$, and hence
the rank of $\mathcal{S}_{d}(G)^{*}$ is larger than the rank of
$\mathcal{A}_{d}(G)$.

To this end, let $n=|V(G)|$ and consider the set
$R_{p}\subseteq\mathbb{C}^{nd}$ of configurations $q$ such that $(G,q)$ is
equivalent to $(G,p)$. This is the fiber of
$m_{d,G}:\mathbb{C}^{nd}\rightarrow M_{d,G}$ over $m_{d,G}(p)$. By Lemma
2.6(b) and the assumption that $G$ is $d$-rigid we have

$\dim(R_{p})=\dim(\mathbb{C}^{nd})-\dim(M_{d,G})=nd-
nd+\binom{d+1}{2}=\binom{d+1}{2}.$

Now we make the same computation for the restriction
$m_{d,G}:K_{{d},{G}}(\omega)\rightarrow L_{d,G}(\omega)$. The key observation
is that by Theorem 2.16, we have $R_{p}\subseteq K_{{d},{G}}(\omega)$, and
hence the fiber of this restricted map over $m_{d,G}(p)$ is still $R_{p}$. It
follows that

$\dim(L_{d,G}(\omega))=\dim(K_{{d},{G}}(\omega))-\dim(R_{p})>d(d+1)-\binom{d+1}{2}=\binom{d+1}{2}=\dim(B(G,p)),$

as desired.

∎

${{\mathbb{C}^{nd}}}$${{M_{d,G}}}$${{M_{d,G}^{*}}}$${{K_{{d},{G}}(\omega)}}$${{L_{d,G}(\omega)}}$${{S(G,p)}}$${{A(G,p)}}$${{B(G,p)}}$$\scriptstyle{m_{d,G}}$dual${\subseteq}$$\scriptstyle{m_{d,G}}$${\subseteq}$${\subseteq}$$\scriptstyle{m_{d,G}}$${\subseteq}$${\subseteq}$
(a)

${\mathcal{R}_{d}(G)}$${\mathcal{S}_{d}(G)}$${\mathcal{S}_{d}(G)^{*}}$${\mathcal{R}_{d}(G)^{*}}$${\mathcal{A}_{d}(G)}$alg.
dual${\leq}$${\leq}$${\leq}$ (b)

Figure 1: Relationships between (a) some spaces considered in this paper, and
(b) their algebraic matroids. Here $(G,p)$ is a generic realization in
$\mathbb{C}^{d}$ and $\omega$ is a generic $d$-stress with $\omega\in S(G,p)$.
In (b), $\mathcal{R}_{d}(G)$ is the ($d$-dimensional generic) rigidity matroid
of $G$, $\mathcal{S}_{d}(G)$ is the ($d$-dimensional generic) stress matroid
of $G$, and $\mathcal{A}_{d}(G)$ is the ($d$-dimensional generic) affine edge
measurement matroid of $G$.

In particular, Propositions 3.8 and 3.15 imply that if $G$ is not
$\mathcal{R}_{d}$-independent, then the rank of $\mathcal{S}_{d}(G)^{*}$ is at
least $\binom{d+1}{2}$, and hence the rank of $\mathcal{S}_{d}(G)$ is at most
$|E|-\binom{d+1}{2}$. By combining Propositions 3.9 and 3.15 we obtain the
following corollary.

######  Corollary 3.16.

Let $G=(V,E)$ be a graph and let $E_{0}\subseteq E$ be a set of edges. If
$E_{0}$ spans at most $d+1$ vertices in $G$, then $E_{0}$ is independent in
$\mathcal{S}_{d}(G)^{*}$. Dually, $E-E_{0}$ is spanning in
$\mathcal{S}_{d}(G)$.

Corollary 3.16 shows that for a generic $d$-stress $\omega$, the fiber of
$\pi_{E-E_{0}}$ over $\pi_{E-E_{0}}(\omega)$ is finite whenever $E_{0}$ spans
at most $d+1$ vertices. Our next result strengthens this by showing that the
only almost generic $d$-stress in the fiber is $\omega$. Although we shall not
use it, we note that it follows from Lemma 2.5(c) that every point in the
fiber is a generic, and hence almost generic, $d$-stress. Thus our result
actually shows that the fiber in question has size one.

######  Lemma 3.17.

Let $G=(V,E)$ be a graph on $n$ vertices and let $(G,p)$ be a generic
realization in $\mathbb{C}^{d}$ with a generic stress $\omega$. Let $(G,q)$ be
another realization in $\mathbb{C}^{d}$ with a stress
$\omega^{\prime}\neq\omega$. If the subset of edges $E_{0}=\\{e\in
E:\omega(e)\neq\omega^{\prime}(e)\\}$ spans at most $d+1$ vertices, then the
subframework $(G[E_{0}],q_{0})$ is not affinely independent. In particular,
$\omega^{\prime}$ is not an almost generic $d$-stress of $G$.

###### Proof.

Let us suppose, for a contradiction, that $(G[E_{0}],q_{0})$ is affinely
independent and let us put $V_{0}=V(G[E_{0}])$. By applying an affine
transformation to $(G,q)$ we may suppose that $q_{0}=p|_{V_{0}}$. By Corollary
3.16, $E-E_{0}$ is spanning in $\mathcal{S}_{d}(G)$, which in particular means
that there are only a finite number of almost generic $d$-stresses that agree
with $\omega$ on $E-E_{0}$ (see Lemma 2.7). We shall contradict this by
explicitly finding an infinite number of such stresses.

To this end, let $\alpha,\beta\in\mathbb{C}$ be scalars with $\alpha+\beta\neq
0$ and let us consider the framework $(G,\alpha p+\beta q)$. We claim that the
vector $\omega_{\alpha,\beta}$ defined by

$\omega_{\alpha,\beta}(uv)=\frac{\alpha\omega(uv)+\beta\omega^{\prime}(uv)}{\alpha+\beta}$

is a stress of $(G,\alpha p+\beta q)$. It suffices to check the equilibrium
condition at each vertex $v\in V$. Note that $\omega_{\alpha,\beta}$ agrees
with $\omega$ and $\omega^{\prime}$ on $E-E_{0}$. Consequently if $v\notin
V_{0}$, then $\omega,\omega^{\prime}$ and $\omega_{\alpha,\beta}$ agree on
each edge incident to $v$ and the equilibrium condition clearly holds. Thus
let us suppose that $v\in V_{0}$ and let us consider partition the neighbours
of $v$ into the sets $A=\\{u\in V:uv\in E-E_{0}\\}$ and $B=\\{u\in V:uv\in
E_{0}\\}$. Using the equilibrium condition on $\omega$ and $\omega^{\prime}$
and the observation that if $u\in A,$ then
$\omega(uv)=\omega^{\prime}(uv)=\omega_{\alpha,\beta}(uv)$, we have

$\displaystyle\sum_{u\in A}\omega_{\alpha,\beta}(uv)$
$\displaystyle\left((\alpha p+\beta q)(u)-(\alpha p+\beta q)(v)\right)$
$\displaystyle=\alpha\sum_{u\in A}\omega(uv)(p(u)-p(v))+\beta\sum_{u\in
A}\omega^{\prime}(uv)(q(u)-q(v))$ $\displaystyle=-\alpha\sum_{u\in
B}\omega(uv)(p(u)-p(v))-\beta\sum_{u\in B}\omega^{\prime}(uv)(q(u)-q(v))$
$\displaystyle=-\sum_{u\in
B}\left(\alpha\omega(uv)+\beta\omega^{\prime}(uv)\right)(p(u)-p(v))$
$\displaystyle=-\sum_{u\in
B}\frac{\alpha\omega(uv)+\beta\omega^{\prime}(uv)}{\alpha+\beta}(\alpha+\beta)(p(u)-p(v))$
$\displaystyle=-\sum_{u\in B}\omega_{\alpha,\beta}(uv)\left((\alpha p+\beta
q)(u)-(\alpha p+\beta q)(v)\right),$

where the third and the last equalities used our assumption that $q(u)=p(u)$
for $u\in V_{0}$. This shows that the equilibrium condition is satisfied at
$v$, and hence $\omega_{\alpha,\beta}$ is indeed a stress of $(G,\alpha
p+\beta q)$. Since $\\{\alpha p+\beta
q:\alpha,\beta\in\mathbb{C}\\}\subseteq\mathbb{C}^{nd}$ is a linear space
containing the generic configuration $p$, the generic configurations are dense
in it by Lemma 2.4. It follows by a simple computation (looking at the values
of $\omega_{\alpha,\beta}(e)$ for some fixed $e\in E_{0}$) that among
$\omega_{\alpha,\beta},\alpha,\beta\in\mathbb{C}$ there is an infinite number
of pairwise different almost generic $d$-stresses. But as we noted before,
this contradicts the fact that $E-E_{0}$ is spanning in $\mathcal{S}_{d}(G)$.
∎

######  Corollary 3.18.

Let $G$ be a graph, $\omega$ a generic $d$-stress of $G$ and $\omega^{\prime}$
an almost generic $d$-stress of $G$. If the subset of edges $E_{0}=\\{e\in
E:\omega(e)\neq\omega^{\prime}(e)\\}$ spans at most $d+1$ vertices, then
$\omega=\omega^{\prime}$.

So far we have considered the spanning sets of $\mathcal{S}_{d}(G)$. Now we
turn our attention to the independent sets. For the next proof, we recall the
definition of a projective transformation and we introduce some terminology.

Let $(G,p)$ be a realization of the graph $G$ in $\mathbb{C}^{d}$, and let
$\tilde{p}$ denote the configuration in $\mathbb{C}^{d+1}$ obtained by
augmenting each vector $p(v),v\in V(G)$ with the number $1$ in the last
coordinate. Let us say that a nonsingular matrix
$A\in\mathbb{C}^{(d+1)\times(d+1)}$ is _feasible_ (for $(G,p)$) if
$\lambda_{v}=(A\tilde{p}(v))_{d+1}\neq 0$ for every $v\in V(G)$. Given a
feasible matrix $A$, let us consider the configuration $q$ in $\mathbb{C}^{d}$
obtained by deleting the last coordinate of $A\tilde{p}(v)/\lambda_{v}$, for
each $v\in V(G)$. We call the configuration $q$ obtained in this way the
_projective image of $p$ under $A$_. The key fact, first observed in [30], is
that if $\omega\in\mathbb{C}^{E}$ is a stress of $(G,p)$, then the vector
$\omega^{\prime}$ defined by
$\omega^{\prime}(uv)=\lambda_{u}\lambda_{v}\omega(uv)$ (where
$\lambda_{v},v\in V(G)$ are defined as above) is a stress of $(G,q)$. For
convenience, we will say that the pair $(q,\omega^{\prime})$ is the
_projective image of the pair $(p,\omega)$ under $A$_. Let $P(G,p,\omega)$
denote the set of projective images of $(p,\omega)$. We shall need the
following technical lemma, whose proof we leave to the Appendix.

######  Lemma 3.19.

Let $G$ be a graph on $n$ vertices, $(G,p)$ a generic realization in
$\mathbb{C}^{d}$ and $\omega$ a generic $d$-stress with $\omega\in S(G,p)$.
Consider the set $P(G,p,\omega)\subseteq\mathbb{C}^{nd}\times\mathbb{C}^{E}$
defined as above and let
$\pi_{2}:\mathbb{C}^{nd}\times\mathbb{C}^{E}\rightarrow\mathbb{C}^{E}$ denote
the projection onto the second factor. Then the almost generic $d$-stresses
are Zariski dense in $\pi_{2}(P(G,p,\omega))$, and consequently
$\pi_{2}(P(G,p,\omega))\subseteq M_{d,G}^{*}$.

######  Theorem 3.20.

Let $G$ be a graph and let $E_{0}\subseteq E$ be a set of edges. Suppose that
either

  1. (a)

$E_{0}$ is the edge set of a forest in $G$ on at most $d+1$ vertices, or

  2. (b)

$d=2$ and $E_{0}$ consists of two disjoint edges.

If none of the edges in $E_{0}$ are $\mathcal{R}_{d}$-bridges in $G$, then
$E_{0}$ is independent in $\mathcal{S}_{d}(G)$.

###### Proof.

Let $\omega$ be a generic $d$-stress of $G$ and let $(G,p)$ be a generic
realization in $\mathbb{C}^{d}$ with $\omega\in S(G,p)$. Note that
$\omega(uv)\neq 0$ for every $uv\in E_{0}$. Indeed, since $\omega$ is
$M_{d,G}^{*}$-generic, if it satisfied the equation $x_{uv}=0$, then every
element of $M_{d,G}^{*}$ would satisfy it. But since $uv$ is not an
$\mathcal{R}_{d}$-bridge of $G$, we know that there exist almost generic
stresses of $G$ that are nonzero on $uv$.

Let $P(G,p,\omega)$ be defined as above. By Lemma 3.19, the projection of
$P(G,p,\omega)$ onto $\mathbb{C}^{E}$ is contained in $M_{d,G}^{*}$. Hence to
show that $E_{0}$ is independent in
$\mathcal{S}_{d}(G)=\mathcal{M}(M_{d,G}^{*})$, it is enough to show that the
projection of $P(G,p,\omega)$ onto $\mathbb{C}^{E_{0}}$ is full-dimensional.
In other words, it suffices to show that for almost all collection of values
$\sigma_{e}\in\mathbb{C},e\in E_{0}$ there is a projective image
$(q,\omega^{\prime})$ of $(p,\omega)$ such that
$\omega^{\prime}(e)=\sigma_{e}$ for all $e\in E_{0}$.

Recall the notation for projective transformations introduced in the paragraph
before Lemma 3.19. Let $V_{0}=V(E_{0})$ and let us first consider case (a). In
this case $|V_{0}|\leq d+1$ and hence the “lifted” points $\tilde{p}(v),v\in
V_{0}$ are linearly independent (otherwise the points $p(v),v\in V_{0}$ would
not be in affine general position). This means that we can freely map these
points to any collection of $d+1$ points in $\mathbb{C}^{d+1}$ using a linear
transformation, and in particular we can freely choose the values
$\lambda_{v},v\in V_{0}$ (provided that they are nonzero). Thus all we need to
do is to solve the system of equations

$\lambda_{u}\lambda_{v}\omega(uv)=\sigma_{uv},\hskip 20.00003pt\forall uv\in
E_{0}$ (5)

in the variables $\lambda_{v},v\in V_{0}$. Since $E_{0}$ is the edge set of a
forest, we can do this whenever $\sigma_{uv}\neq 0$ for every $uv\in E_{0}$ by
taking a leaf vertex $v$ of this forest with incident edge $uv\in E_{0}$,
solving the equations for $E_{0}-uv$ recursively and then choosing the value
of $\lambda_{v}$ suitably.

A similar approach works in case (b), but we have to be a bit more careful.
Let $E_{0}=\\{v_{1}v_{2},v_{3}v_{4}\\}$. The vectors
$\tilde{p}(v_{1}),\tilde{p}(v_{2}),\tilde{p}(v_{3})\in\mathbb{C}^{3}$ are
linearly independent and we have
$\tilde{p}(v_{4})=\sum_{i=1}^{3}\alpha_{i}\tilde{p}(v_{i})$ for some nonzero
scalars $\alpha_{1},\alpha_{2},\alpha_{3}$. As before, we have to solve 5; now
we can freely choose the values
$\lambda_{v_{1}},\lambda_{v_{2}},\lambda_{v_{3}}$, and by linearity we have
$\lambda_{v_{4}}=\sum_{i=1}^{3}\alpha_{i}\lambda_{v_{i}}$. If we now set
$\lambda_{v_{1}}=1,\lambda_{v_{2}}=\sigma_{v_{1}v_{2}}\omega(v_{1}v_{2})^{-1}$
and $\lambda_{v_{3}}=c\in\mathbb{C}$, then the value
$\lambda_{v_{3}}\lambda_{v_{4}}\omega(v_{3}v_{4})$ is a quadratic function of
$c$, and hence it is surjective on $\mathbb{C}$. It follows that by suitably
choosing the value of $c$ we can solve the system of equations 5 for any
choice of $\sigma_{v_{1}v_{2}},\sigma_{v_{3}v_{4}}$, as desired. ∎

The proof technique of Theorem 3.20 seems quite weak in that it only uses
projective images of $(p,\omega)$, and these form a small-dimensional subset
of all pairs $(q,\omega^{\prime})$ with $\omega^{\prime}\in S(G,q)$. The
problem is that even though we know that there are many almost generic
stresses $\omega^{\prime}$, it is not clear how to control precisely the
values of $\omega^{\prime}$ on a given set of edges. It seems likely that the
proof method of Theorem 3.20 can be taken a bit further to show that if
$E_{0}$ forms a forest on $d+2$ vertices, or a pseudoforest on $d+1$ vertices,
then it is independent in $\mathcal{S}_{d}(G)$. However, we will not pursue
this direction. In fact, the only result we will need is the following
corollary.

######  Corollary 3.21.

The stress matroid $\mathcal{S}_{d}(G)$ does not contain circuits of size two
for any graph $G=(V,E)$.

###### Proof.

If $d=1$, then the statement follows from Proposition 3.23 below, so let us
assume that $d\geq 2$ and let $\\{e_{1},e_{2}\\}\subseteq E$. If $e_{i}$ is an
$\mathcal{R}_{d}$-bridge in $G$, then by Corollary 3.5 it is a loop in
$\mathcal{S}_{d}(G)$ and hence $\\{e_{1},e_{2}\\}$ is not a circuit. Otherwise
Theorem 3.20 implies that $\\{e_{1},e_{2}\\}$ is independent in
$\mathcal{S}_{d}(G)$ and hence, again, it is not a circuit. ∎

We close this section by describing the one-dimensional generic stress
matroid. We will need the specialization of Proposition 3.4 to the measurement
variety.

######  Proposition 3.22.

Let $G$ be a graph and let $G_{i},i\in\\{1,\ldots,k\\}$ denote the
$\mathcal{R}_{d}$-components of $G$. Then
$\mathcal{S}_{d}(G)=\bigoplus_{i=1}^{k}\mathcal{S}_{d}(G_{i})$, and moreover
$M_{d,G}^{*}=M_{d,G_{1}}^{*}\times\ldots\times M_{d,G_{k}}^{*}$.

The $\mathcal{R}_{1}$-components of a graph are just its $2$-connected
components, which are globally $1$-rigid. Using this observation and the
preceding results on the stress matroid we can determine the one-dimensional
generic stress matroid of any graph $G$.

######  Proposition 3.23.

Let $G=(V,E)$ be a graph and $E_{1},\ldots,E_{k}$ be the edge sets of its
$2$-connected components. Let $m_{i}=|E_{i}|$ for $i\in\\{1,\ldots,k\\}.$ Then
$\mathcal{S}_{1}(G)=\bigoplus_{i=1}^{k}U_{m_{i}-1}(E_{i})$, where $U_{k}(X)$
denotes the rank $k$ uniform matroid on ground set $X$.

###### Proof.

The $\mathcal{R}_{1}$-components of a graph are just its $2$-connected
components. By Proposition 3.22 we may assume that $G$ is $2$-connected (i.e.,
globally $1$-rigid). From Theorem 3.15 we have that $\mathcal{S}_{1}(G)$ is
the dual of $\mathcal{A}_{1}(G)$. By Corollary 3.10,
$\mathcal{A}_{1}(G)=U_{1}(E)$, so $\mathcal{S}_{1}(G)=U_{|E|-1}(E)$, as
required. ∎

##  4 Stress-linked vertex pairs

In this section we introduce and investigate ${d}$-stress-linked vertex pairs,
one of the central new ideas in this paper. While the definition of being
${d}$-stress-linked does not involve the generic stress matroid, we will make
use of the structural results of the previous section in order to prove our
main results about this notion. Before we start, we recall another pair of
definitions from [12]: that of the shared stress kernel and the shared stress
nullity.

Let $G$ be a graph on $n$ vertices. For a framework $(G,p)$ in
$\mathbb{C}^{d}$ let $K(G,p)$ denote the set of configurations
$q\in\mathbb{C}^{nd}$ for which $S(G,p)\subseteq S(G,q)$, or in other words,
for which the framework $(G,q)$ satisfies every stress of $(G,p)$. Following
[12], we call $K(G,p)$ the _( $d$-dimensional) shared stress kernel_ of
$(G,p)$. Similarly, we define $K_{1}(G,p)$ to be the set of one-dimensional
configurations $q\in\mathbb{C}^{n}$ for which $S(G,p)\subseteq S(G,q)$; this
is the _one-dimensional shared stress kernel_ of $(G,p)$. Both $K(G,p)$ and
$K_{1}(G,p)$ are linear spaces, and we have $K(G,p)=(K_{1}(G,p))^{d}$ as
linear spaces. We also have the description

$K(G,p)=\bigcap_{\omega\in S(G,p)}K_{{d},{G}}(\omega),\hskip 10.00002pt\text{
and }\hskip 10.00002ptK_{1}(G,p)=\bigcap_{\omega\in
S(G,p)}K_{{1},{G}}(\omega).$

Since $K_{1}(G,p)\subseteq\mathbb{C}^{n}$, we trivially have
$\dim(K_{1}(G,p))\leq n$. On the other hand, the $d$ coordinate-vectors of
$(G,p)$ belong to $K_{1}(G,p)$, as well as the all ones vector. If $(G,p)$ has
full affine span, then these $d+1$ vectors are linearly independent, which
shows that in this case $\dim K_{1}(G,p)\geq d+1$.

By general principles the dimension of $K_{1}(G,p)$ is the same for every
generic framework $(G,p)$ in a given dimension, see [12, Remark 4.2].333In
[12] the authors define and consider $K_{1}(G,p)$ using only real frameworks
and stresses. However, their reasoning also works in the complex setting, and
it also shows that the dimension of $K_{1}(G,p)$ for generic $(G,p)$ is the
same in both settings. Following [12], we call this number the _shared stress
nullity_ of $G$ in $d$ dimensions, and denote it by $k_{\text{sh}}(G,d)$. By
the previous discussion we have $d+1\leq k_{\text{sh}}(G,d)\leq n$ whenever
$G$ has at least $d+1$ vertices. It is not difficult to show (and we shall do
so in Lemma 4.10) that $k_{\text{sh}}(G,d)=n$ if and only if $G$ is
$\mathcal{R}_{d}$-independent.

One of the main results of [12] was the following characterization of globally
$d$-rigid graphs in terms of the shared stress nullity.

######  Theorem 4.1.

([12, Theorem 4.4]) A graph $G$ on at least $d+2$ vertices is globally
$d$-rigid if and only if $k_{\text{sh}}(G,d)=d+1$.

Note that $A(G,p)\subseteq K(G,p)$ always holds. We will need the following
consequence of Theorem 4.1, although we will only use it in the case when $G$
is a complete graph.

######  Corollary 4.2.

If $G$ is globally $d$-rigid, then for every generic realization $(G,p)$ in
$\mathbb{C}^{d}$ we have $K(G,p)=A(G,p)$.

###### Proof.

If $G$ has at most $d+1$ vertices, then it is $\mathcal{R}_{d}$-independent
and hence both $K(G,p)$ and $A(G,p)$ are equal to the whole configuration
space $\mathbb{C}^{nd}$. If $G$ has at least $d+2$ vertices, then the
statement follows from Theorem 4.1 by the dimension count

$\dim(K(G,p))=d\cdot k_{\text{sh}}(G,d)=d(d+1)=\dim(A(G,p)).\qed$

We now arrive to one of the main new notions of this paper. Let $G$ be a graph
and $u,v\in V(G)$ a pair of vertices. We say that $\\{u,v\\}$ is _${d}$
-stress-linked in $G$_ if $\\{u,v\\}$ is $\mathcal{R}_{d}$-linked in $G$ and
$k_{\text{sh}}(G+uv,d)=k_{\text{sh}}(G,d)$. Note that if $uv\in E(G)$, then
$\\{u,v\\}$ trivially satisfies these conditions. The following proposition
rephrases the definition of being ${d}$-stress-linked in a number of
convenient forms.

######  Proposition 4.3.

Let $G$ be a graph and $u,v\in V(G)$ a nonadjacent pair of vertices such that
$\\{u,v\\}$ is $\mathcal{R}_{d}$-linked in $G$. Let $(G,p)$ be a generic
realization in $\mathbb{C}^{d}$ and let $\omega\in S(G+uv,p)$ be a stress that
is nonzero on $uv$. The following are equivalent.

  1. (a)

$\\{u,v\\}$ is ${d}$-stress-linked in $G$;

  2. (b)

$K(G+uv,p)=K(G,p)$;

  3. (c)

$\omega$ is a stress of $(G+uv,q)$ for every configuration $q\in K(G,p)$;

  4. (d)

$\omega$ is a stress of $(G+uv,q)$ for every generic configuration $q\in
K(G,p)$.

###### Proof.

Since the pair $\\{u,v\\}$ is $\mathcal{R}_{d}$-linked, it is ${d}$-stress-
linked if and only if $k_{\text{sh}}(G+uv,d)=k_{\text{sh}}(G,d)$. This is
equivalent to $\dim(K_{1}(G+uv,p))=\dim(K_{1}(G,p))$. We clearly have
$K_{1}(G+uv,p)\subseteq K_{1}(G,p)$, and hence we must also have
$K_{1}(G+uv,p)=K_{1}(G,p)$. Using the observation that
$K(G,p)=(K_{1}(G,p))^{d}$ (and similarly for $(G+uv,p)$), this is further
equivalent to condition (b). On the other hand, a dimension count shows that
$S(G+uv,p)$ is generated by $S(G,p)\cup\\{\omega\\}$, and hence
$K(G+uv,p)=K(G,p)\cap K_{{d},{G+uv}}(\omega)$. In other words,
$K(G+uv,p)=K(G,p)$ holds if and only if $K(G,p)\subseteq
K_{{d},{G+uv}}(\omega)$, which is the content of (c). This shows the
equivalence of the first three conditions. Condition (c) clearly implies (d).
For the reverse direction, note that since $(G,p)$ is generic, the linear
space $K(G,p)$ contains a generic configuration and hence by Lemma 2.4 the
generic configurations are Zariski dense in it. The condition that $\omega$ is
a stress of $(G+uv,q)$ is described by polynomial equations, so if it holds
for a Zariski dense subset of $K(G,p)$, then it holds for all of it. ∎

We can also give a characterization of ${d}$-stress-linked vertex pairs in
terms of Gauss fibers. Given a generic framework $(G,p)$ in $\mathbb{C}^{d}$,
its _Gauss fiber_ is the set $L(G,p)=\overline{m_{d,G}(K(G,p)})$. It can be
shown that the Gauss fiber of $(G,p)$ is the intersection of the contact loci
$L_{d,G}(\omega)$ for $\omega\in S(G,p)$. In particular, it is a linear space.
The following statement can be shown by a dimension counting argument similar
to the one we saw in the proof of Theorem 3.15. Since we shall not use this
result, we leave its proof to the Appendix.

######  Proposition 4.4.

Let $G$ be a graph on $n$ vertices and $u,v\in V(G)$ a pair of vertices. Let
$(G,p)$ be a generic framework in $\mathbb{C}^{d}$. The vertex pair
$\\{u,v\\}$ is ${d}$-stress-linked if and only if
$\dim(L(G+uv,p))=\dim(L(G,p))$, where $L(G,p)$ is the Gauss fiber of $(G,p)$.

###  4.1 Basic properties of stress-linked pairs

In this subsection we establish some basic results about ${d}$-stress-linked
vertex pairs. We start with the two most interesting ones: that ${d}$-stress-
linked vertex pairs are globally linked in $\mathbb{C}^{d}$, and that
$\mathcal{R}_{d}$-bridges and ${d}$-stress-linked pairs “do not interact” with
each other.

######  Theorem 4.5.

Let $G$ be a graph and $u,v\in V(G)$ a pair of vertices. If $\\{u,v\\}$ is
${d}$-stress-linked in $G$, then $\\{u,v\\}$ is globally linked in $G$ in
$\mathbb{C}^{d}$.

###### Proof.

Suppose in the converse that $\\{u,v\\}$ is $\mathcal{R}_{d}$-linked in $G$
but not globally linked in $G$ in $\mathbb{C}^{d}$. Let $(G,p),(G,q)$ be
equivalent frameworks in $\mathbb{C}^{d}$ with $(G,p)$ generic and such that
$(G+uv,p)$ and $(G+uv,q)$ are not equivalent. Let $G^{\prime}=G+uv$ and let
$\omega^{\prime}$ be a generic $d$-stress of $G^{\prime}$ with
$\omega^{\prime}\in S(G^{\prime},p)$. Note that Theorem 2.16 implies that
$q\in K(G,p)$. Thus by Proposition 4.3(c), in order to show that $\\{u,v\\}$
is not ${d}$-stress-linked in $G$, it is enough to show that $\omega^{\prime}$
is not a stress of $(G^{\prime},q)$. Suppose for a contradiction that it is;
then $q\in K_{{d},{G}}(\omega)$ and hence the contact locus
$L_{d,G^{\prime}}(\omega^{\prime})=\overline{m_{d,G^{\prime}}(K_{{d},{G^{\prime}}}(\omega^{\prime}))}$
contains both $m_{d,G^{\prime}}(p)$ and $m_{d,G^{\prime}}(q)$. Since
$L_{d,G^{\prime}}(\omega^{\prime})\subseteq M_{d,G^{\prime}}$ is a linear
space, this means that the fiber of the projection
$\pi_{E}:M_{d,G^{\prime}}\rightarrow M_{d,G}$ over $m_{d,G}(p)$ is all of
$\\{m_{d,G}(p)\\}\times\mathbb{C}$, so in particular the fiber is one-
dimensional. Since $m_{d,G^{\prime}}(p)$ is $M_{d,G^{\prime}}$-generic by
Lemma 2.5, Lemma 2.6(b) now implies that
$\dim(M_{d,G^{\prime}})-\dim(M_{d,G})=1$, or equivalently,
$r_{d}(G^{\prime})=r_{d}(G)+1.$ It follows that $uv$ is an
$\mathcal{R}_{d}$-bridge in $G^{\prime}$, a contradiction. ∎

It is natural to also consider the converse of Theorem 4.5: is it true that if
$\\{u,v\\}$ is globally linked in $G$ in $\mathbb{C}^{d}$ (or in
$\mathbb{R}^{d}$), then $\\{u,v\\}$ is ${d}$-stress-linked? We shall return to
this question in Section 6. We note that the answer is affirmative when every
pair of vertices is globally linked, that is, when $G$ is globally $d$-rigid.

######  Proposition 4.6.

If the graph $G$ is globally $d$-rigid, then $\\{u,v\\}$ is ${d}$-stress-
linked in $G$ for all pairs $u,v\in V(G)$.

###### Proof.

If $G$ has at most $d+1$ vertices, then it is complete and the statement is
vacuous. Otherwise it follows from Theorem 4.1 that for every pair of vertices
$u,v\in V(G)$ we have $d+1=k_{\text{sh}}(G,d)=k_{\text{sh}}(G+uv,d)$. Since
$G$ is globally $d$-rigid, it is also $d$-rigid, and hence every pair of
vertices is $\mathcal{R}_{d}$-linked in $G$. ∎

Our next result shows that deleting $\mathcal{R}_{d}$-bridges of a graph
preserves its ${d}$-stress-linked pairs, and adding an edge between a
${d}$-stress-linked vertex pair preserves its $\mathcal{R}_{d}$-bridges. This
result will be central to our applications in Section 5. We will need the
following easy observation.

######  Lemma 4.7.

Let $G$ be a graph and $u,v\in V(G)$ a pair of vertices. If $\\{u,v\\}$ is not
$\mathcal{R}_{d}$-linked in $G$, then
$k_{\text{sh}}(G,d)=k_{\text{sh}}(G+uv,d)$.

###### Proof.

Let $(G,p)$ be a generic realization in $\mathbb{C}^{d}$. The assumption on
$\\{u,v\\}$ means that $S(G+uv,p)$ only consists of stresses supported on $E$.
It follows that $K(G,p)=K(G+uv,p)$ and thus
$k_{\text{sh}}(G,d)=k_{\text{sh}}(G+uv,d)$. ∎

######  Theorem 4.8.

Let $G$ be a graph on $n$ vertices with $e\in E(G)$ and $u,v\in V(G)$. Suppose
that $e$ is an $\mathcal{R}_{d}$-bridge in $G$ and $\\{u,v\\}$ is
${d}$-stress-linked in $G$. Then $\\{u,v\\}$ is ${d}$-stress-linked in $G-e$.

###### Proof.

The assumptions on $e$ and $\\{u,v\\}$ combined with Lemma 4.7 imply that
$k_{\text{sh}}(G-e,d)=k_{\text{sh}}(G,d)=k_{\text{sh}}(G+uv,d)$, and since
$k_{\text{sh}}(G-e,d)\geq k_{\text{sh}}(G-e+uv,d)\geq k_{\text{sh}}(G+uv,d)$,
it follows that $k_{\text{sh}}(G-e,d)=k_{\text{sh}}(G-e+uv,d)$. For a
contradiction, suppose that $\\{u,v\\}$ is not $\mathcal{R}_{d}$-linked in
$G-e$. In this case $r_{d}(G)=r_{d}(G-e+uv)=r_{d}(G+uv)$, so neither $e$ nor
$uv$ is an $\mathcal{R}_{d}$-bridge in $G+uv$.

Let $G^{\prime}=G+uv$, let $(G,p)$ be a generic framework of $G$ in
$\mathbb{C}^{d}$ and let $\omega^{\prime}$ be a generic $d$-stress of
$(G^{\prime},p)$. We recall Theorem 3.14, which states that the algebraic
matroid $\mathcal{M}(L_{d,G^{\prime}}(\omega^{\prime}))$ of the contact locus
$L_{d,G^{\prime}}(\omega^{\prime})$ is the dual of the generic stress matroid
$\mathcal{S}_{d}(G^{\prime})$. Note that since neither $e$ nor $uv$ is an
$\mathcal{R}_{d}$-bridge in $G^{\prime}$, by Corollary 3.5 they are not loops
in $\mathcal{S}_{d}(G^{\prime})$. We shall show that $E-e$ is not spanning in
$\mathcal{M}(L_{d,G^{\prime}}(\omega^{\prime}))$, and hence by duality
$\\{e,uv\\}$ is dependent in $\mathcal{S}_{d}(G^{\prime})$, contradicting
Corollary 3.21.

Let $R_{p}\subseteq\mathbb{C}^{nd}$ denote the set of configurations $q$ for
which $(G-e,q)$ is equivalent to $(G-e,p)$. Theorem 2.16 and the fact that
$(G-e,p)$ is generic imply $R_{p}\subseteq K(G-e,p)$. On the other hand,
$k_{\text{sh}}(G-e,d)=k_{\text{sh}}(G^{\prime},d)$ implies that
$K(G-e,p)=K(G^{\prime},p)\subseteq K_{{d},{G^{\prime}}}(\omega^{\prime})$, so
$R_{p}\subseteq K_{{d},{G^{\prime}}}(\omega^{\prime})$. In particular, the
fiber $F$ of $\pi_{E-e}:L_{d,G^{\prime}}(\omega^{\prime})\rightarrow
M_{d,G-e}$ over $m_{d,G-e}(p)$ contains $m_{d,G^{\prime}}(R_{p})$. (See Figure
2.) Since $e$ is an $\mathcal{R}_{d}$-bridge in $G$, $m_{d,G^{\prime}}(R_{p})$
is an infinite set, and hence so is the fiber $F$. Since
$L_{d,G^{\prime}}(\omega^{\prime})$ is a linear space, Lemma 2.11 now implies
that $E-e$ is not spanning in
$\mathcal{M}(L_{d,G^{\prime}}(\omega^{\prime}))$, and thus $\\{e,uv\\}$ is a
circuit in $\mathcal{S}_{d}(G^{\prime})$, a contradiction. ∎

$K_{d,G^{\prime}}(\omega)$$R_{p}$$p$$L_{d,G^{\prime}}(\omega)$$m_{d,G^{\prime}}(p)$$m_{d,G^{\prime}}(R_{p})$$m_{d,G^{\prime}}$$m_{d,G-e}$$m_{d,G-e}(p)$$\pi_{E-e}$
Figure 2: An illustration of the proof of Theorem 4.8.

######  Corollary 4.9.

Let $G$ be a graph and $u,v\in V(G)$ a pair of vertices. If $\\{u,v\\}$ is
${d}$-stress-linked in $G$, then the set of $\mathcal{R}_{d}$-bridges is the
same in $G$ and $G+uv$.

###### Proof.

Let $e$ be an edge of $G$. Clearly, if $e$ is an $\mathcal{R}_{d}$-bridge in
$G+uv$, then it is an $\mathcal{R}_{d}$-bridge in $G$. Conversely, if $e$ is
an $\mathcal{R}_{d}$-bridge in $G$, then by Theorem 4.8 $\\{u,v\\}$ is
$\mathcal{R}_{d}$-linked in $G-e$. Thus we have
$r_{d}(G+uv)=r_{d}(G)>r_{d}(G-e)=r_{d}(G+uv-e)$, which shows that $e$ is a
bridge in $G+uv$. ∎

We note that Corollary 4.9 implies Hendrickson’s theorem [18], which says that
globally $d$-rigid graphs on at least $d+2$ vertices are redundantly
$d$-rigid, or in other words, they are $d$-rigid and do not contain
$\mathcal{R}_{d}$-bridges. Indeed, if $G$ is globally $d$-rigid, then by
Proposition 4.6 every pair of vertices is ${d}$-stress-linked in $G$, so by
Corollary 4.9 the set of $\mathcal{R}_{d}$-bridges of $G$ is the same as the
set of $\mathcal{R}_{d}$-bridges of the complete graph on $K(V)$, which is
easily seen to be bridgeless when $|V(G)|\geq d+2$. Although at first sight
this appears to be a novel proof of Hendrickson’s theorem, we implicitly used
Theorem 4.1 (through Proposition 4.6), which quickly implies Hendrickson’s
theorem by itself.

We will need the following characterization of graphs with large shared stress
nullity.

######  Lemma 4.10.

Let $G$ be a graph on $n$ vertices.

  1. (a)

We have $k_{\text{sh}}(G,d)=n$ if and only if $G$ is
$\mathcal{R}_{d}$-independent.

  2. (b)

We have $k_{\text{sh}}(G,d)=n-1$ if and only if $G$ consists of a copy of
$K_{d+2}$ as well as possibly some $\mathcal{R}_{d}$-bridges and isolated
vertices.

###### Proof.

(a) We have $k_{\text{sh}}(G,d)=n$ if and only if for any generic realization
$(G,p)$, $K_{1}(G,p)=\mathbb{C}^{n}$. If $G$ is $\mathcal{R}_{d}$-independent,
then $(G,p)$ only has the zero stress, so $K_{1}(G,p)=\mathbb{C}^{n}$ indeed
holds. Otherwise $(G,p)$ has a nonzero stress $\omega$ and we can find some
one-dimensional realization of $G$ that does not have $\omega$ as a stress by
perturbing the coordinates of $(G,p)$, so in this case
$K_{1}(G,p)\neq\mathbb{C}^{n}$.

(b) For $G=K_{d+2}$, it follows from Theorem 4.1 that
$k_{\text{sh}}(G,d)=d+1=n-1$. Sufficiency follows from the observation that
adding an isolated vertex increases $k_{\text{sh}}(G,d)$ by one, while adding
$\mathcal{R}_{d}$-bridges does not change it by Lemma 4.7.

For necessity, suppose that $k_{\text{sh}}(G,d)=n-1$; by part (a) this implies
that $G$ is not $\mathcal{R}_{d}$-independent. Let $(G,p)$ be a generic
realization of $G$ and let $\omega$ be a nonzero stress of $(G,p)$ that is
supported on some $\mathcal{R}_{d}$-circuit $C$ in $G$. We now have

$n-1=\dim(K_{1}(G,p))\leq\dim(K_{{1},{G}}(\omega))<n,$

which implies that $K_{1}(G,p)=K_{{1},{G}}(\omega)$. This means that the so-
called _stress matrix_ $\Omega$ of $\omega$ has an $(n-1)$-dimensional kernel,
and hence $\operatorname{rk}(\Omega)=1$. It is not difficult to see that in
this case $C$ must be complete graph, see [9, Lemma 3.6]. It follows that $C$
is a copy of $K_{d+2}$, since this is the only complete
$\mathcal{R}_{d}$-circuit.

If the support of $\omega$ is the only $\mathcal{R}_{d}$-circuit in $G$, then
we are done. Moreover, the previous argument shows that any
$\mathcal{R}_{d}$-circuit in $G$ must be a copy of $K_{d+2}$. Let us suppose
for a contradiction that there is another $\mathcal{R}_{d}$-circuit
$C^{\prime}$ in $G$. Note that $C$ and $C^{\prime}$ can share at most one
vertex, since otherwise by the circuit elimination axiom of matroids we could
find an $\mathcal{R}_{d}$-circuit in $G$ that is not a copy of $K_{d+2}$. Let
$\omega^{\prime}$ be a nonzero stress of $(G,p)$ supported on $C^{\prime}$.
The assumption that $k_{\text{sh}}(G,d)=n-1$ implies
$K_{{d},{G}}(\omega)=K(G,p)=K_{{d},{G}}(\omega^{\prime})$. But this is clearly
impossible: since $\omega$ is not supported on $V(C_{2})$, the projection of
$K_{{d},{G}}(\omega)$ to $\mathbb{C}^{|V(C_{2})|}$ is surjective, while the
projection of $K_{{d},{G}}(\omega^{\prime})$ consists of the affine images of
$\left.p\right|_{V(C_{2})}$ by Corollary 4.2. Since $|V(C_{2})|=d+2$, this is
a proper linear subspace of $\mathbb{C}^{|V(C_{2})|}$, a contradiction. ∎

As a simple corollary of Lemma 4.10(a), we show that in an
$\mathcal{R}_{d}$-independent graph, the only ${d}$-stress-linked vertex pairs
are the ones corresponding to edges of the graph. It is an open question
whether the analogous statement holds for globally linked pairs in
$\mathbb{R}^{d}$ (or in $\mathbb{C}^{d}$). It is known to be true in the
special case when $d=2$ and the graph is minimally $2$-rigid, see [20,
Corollary 2].

######  Corollary 4.11.

If $G$ is $\mathcal{R}_{d}$-independent, then a pair $\\{u,v\\}$ of vertices
is ${d}$-stress-linked in $G$ if and only if $uv\in E(G)$.

###### Proof.

If $uv\in E(G)$, then $\\{u,v\\}$ is clearly ${d}$-stress-linked in $G$.
Otherwise either $\\{u,v\\}$ is not $\mathcal{R}_{d}$-linked, or $G+uv$ is not
$\mathcal{R}_{d}$-independent. In the latter case we have
$k_{\text{sh}}(G+uv,d)<n=k_{\text{sh}}(G,d)$ by Lemma 4.10, so $\\{u,v\\}$ is
not ${d}$-stress-linked. ∎

We close this subsection by noting that being ${d}$-stress-linked is preserved
under taking supergraphs and under separation along a complete graph. The
(somewhat technical but not difficult) proofs can be found in the Appendix.

######  Lemma 4.12.

Let $G$ be a graph, $G_{0}$ a subgraph of $G$ and $u,v\in V(G_{0})$ a pair of
vertices. If $\\{u,v\\}$ is ${d}$-stress-linked in $G_{0}$, then $\\{u,v\\}$
is ${d}$-stress-linked in $G$.

######  Lemma 4.13.

Let $G=(V,E)$ the union of the graphs $G_{1}=(V_{1},E_{1})$ and
$G_{2}=(V_{2},E_{2})$ and suppose that $G_{1}\cap G_{2}$ is either empty or a
complete graph. Let $u,v\in V_{1}$ be a pair of vertices. Then $\\{u,v\\}$ is
${d}$-stress-linked in $G$ if and only if $\\{u,v\\}$ is ${d}$-stress-linked
in $G_{1}$.

###  4.2 Stress-linked pairs and small separators

The main goal of this subsection is the investigation of the following
conjecture of Jordán and the author.

######  Conjecture 4.14.

([10, Conjecture 5.6]) Let $G$ be the union of the graphs
$G_{1}=(V_{1},E_{1}),G_{2}=(V_{2},E_{2})$ with $|V_{1}\cap V_{2}|\leq d+1,$
and let $u,v\in V_{1}\cap V_{2}$ be a pair of vertices. If $\\{u,v\\}$ is
$\mathcal{R}_{d}$-linked in both $G_{1}$ and $G_{2}$, then $\\{u,v\\}$ is
globally linked in $G$ in $\mathbb{R}^{d}$.

We shall verify 4.14 in the case when each pair of common vertices $u,v\in
V_{1}\cap V_{2}$ is $\mathcal{R}_{d}$-linked in both $G_{1}$ and $G_{2}$. We
will in fact prove the stronger statement that in this case every pair of
common vertices is ${d}$-stress-linked in $G$.

######  Theorem 4.15.

Let $G$ be the union of the graphs $G_{1}=(V_{1},E_{1}),G_{2}=(V_{2},E_{2})$
with $|V_{1}\cap V_{2}|\leq d+1$ and suppose that for every pair of vertices
$u,v\in V_{1}\cap V_{2}$, $\\{u,v\\}$ is $\mathcal{R}_{d}$-linked in both
$G_{1}$ and $G_{2}$. Then for every pair of vertices $u,v\in V_{1}\cap V_{2}$,
$\\{u,v\\}$ is ${d}$-stress-linked in $G$.

The key ingredient of our proof of Theorem 4.15 is Corollary 3.18, but before
we can apply it we have analyze the space of stresses of $G_{1}\cup G_{2}$.
Before giving the proof, we illustrate the main ideas in the special case when
$d=3$ and $G$ is the double banana graph.

######  Example 4.16.

Consider the graph $G$ depicted in Figure 3. We can write $G$ as $G_{1}\cup
G_{2}$ where $G_{1}$ and $G_{2}$ are both copies of $K_{5}$ minus an edge.
Since $K_{5}$ is an $\mathcal{R}_{3}$-circuit, $\\{u,v\\}$ is
$\mathcal{R}_{3}$-linked in both $G_{1}$ and $G_{2}$. Lemma 2.13 implies the
well-known fact that $G$ is also an $\mathcal{R}_{3}$-circuit. Let $(G,p)$ be
a generic realization in $\mathbb{C}^{3}$ and let $\omega_{i}$ denote the
unique (up to scale) nonzero stress of $(G+uv,p)$ that is supported on
$G_{i}+uv$, for $i\in\\{1,2\\}$. It is easy to verify that
$\omega_{1}-\omega_{2}$ is the unique (up to scale) nonzero stress of $(G,p)$.

We claim that $\\{u,v\\}$ is ${3}$-stress-linked in $G$. To prove this, by
Proposition 4.3(d) it suffices to show that for every generic configuration
$q\in K(G,p)$, $\omega_{1}$ is a stress of $(G+uv,q)$. The main idea is that
since $(G,q)$ is also generic, its space of stresses also has the structure
described in the previous paragraph. In particular, $\omega_{1}-\omega_{2}\in
S(G,q)$, and hence by the previous paragraph we can write
$\omega_{1}-\omega_{2}=\omega_{1}^{q}-\omega_{2}^{q}$, where $\omega_{i}^{q}$
is a stress of $(G+uv,q)$ supported on $G_{i}+uv$, for $i\in\\{1,2\\}$. Note
that $\omega_{1}$ and $\omega_{1}^{q}$ are both almost generic $3$-stresses of
$G_{1}+uv$, and they are equal on the edges of $G_{1}$. Corollary 3.18 now
implies that $\omega_{1}$ and $\omega_{1}^{q}$ are also equal on $uv$, so
$\omega_{1}$ is indeed a stress of $(G+uv,q)$.

$u$$v$ Figure 3: The double banana graph with “hinge” vertices $u$ and $v$.

In the following proof we shall let $K_{V}$ denote the complete graph on
vertex set $V$.

###### Proof of Theorem 4.15.

Let $S=V_{1}\cap V_{2}$, $G^{\prime}=G+E(K_{S})$ and
$G_{i}^{\prime}=G_{i}+E(K_{S})$ for $i\in\\{1,2\\}$. We may suppose that
$G_{1}$ and $G_{2}$ are induced subgraphs, so that $G[S]=G_{1}[S]=G_{2}[S]$.
Let $(G,p)$ be a generic realization of $G$ in $\mathbb{R}^{d}$. We start by
describing the space of stresses of $(G,p)$. By a slight abuse of notation we
shall let $S(G_{i},p_{i})$ denote the subspace of $S(G,p)$ of stresses
supported on $E_{i},$ and similarly we let $S(G_{i}^{\prime},p_{i})$ be the
subspace of $S(G^{\prime},p)$ of stresses supported on $E_{i}\cup E(K_{S})$,
for $i\in\\{1,2\\}$. Let us fix a basis $\mathcal{B}_{i}$ of $S(G_{i},p_{i})$
for $i\in\\{1,2\\}$.

Consider $E_{0}=E(K_{S})-E(G[S])$ and for each $i\in\\{1,2\\}$ and each
$e=uv\in E_{0}$ let $\omega_{i,e}$ be a stress of $(G,p)$ supported on
$G_{i}+e$ and with $\omega_{i,e}(e)=1$. Such a stress exists because of our
assumption that $\\{u,v\\}$ is $\mathcal{R}_{d}$-linked in $G_{i}$. Now
$\mathcal{B}_{i}\cup\\{\omega_{i,e}:e\in E_{0}\\}$ is a basis of
$S(G_{i}^{\prime},p_{i})$, and since we have
$S(G^{\prime},p)=S(G_{1}^{\prime},p_{1})\oplus S(G_{2}^{\prime},p_{2})$ by
Lemma 2.17(b),

$\mathcal{B}^{\prime}=\mathcal{B}_{1}\cup\mathcal{B}_{2}\cup\\{\omega_{i,e}:i\in\\{1,2\\},e\in
E_{0}\\}$

is a basis of $S(G^{\prime},p)$. We claim that

$\mathcal{B}=\mathcal{B}_{1}\cup\mathcal{B}_{2}\cup\\{\omega_{1,e}-\omega_{2,e}:e\in
E_{0}\\}$

is a basis of $S(G,p)$. Indeed, this is a collection of
$|\mathcal{B}_{1}|+|\mathcal{B}_{2}|+|E_{0}|$ vectors that all lie in
$S(G,p)$, and since $\\{u,v\\}$ is $\mathcal{R}_{d}$-linked in $G$ for each
$uv\in E_{0}$ we have

$|\mathcal{B}_{1}|+|\mathcal{B}_{2}|+2|E_{0}|=|\mathcal{B}^{\prime}|=\dim(S(G^{\prime},p))=\dim(S(G,p))+|E_{0}|.$

Thus it is enough to show that the vectors in $\mathcal{B}$ are linearly
independent, which follows from the observation that
$\mathcal{B}\cup\\{\omega_{1,e}:e\in E_{0}\\}$ spans the vectors in
$\mathcal{B}^{\prime}$ and thus it is a basis of $S(G^{\prime},p)$.

Clearly, every pair of vertices $u,v\in V_{1}\cap V_{2}$ is
$\mathcal{R}_{d}$-linked in $G$. Our goal is to show that we also have
$k_{\text{sh}}(G^{\prime},d)=k_{\text{sh}}(G,d)$. By Proposition 4.3(d) it is
enough to show that for every generic configuration $q\in K(G,p)$, $q\in
K(G^{\prime},p)$ also holds. Let us thus fix a generic configuration $q\in
K(G,p)$. Note that since $(G,q)$ is generic, we have
$\dim(S(G,p))=\dim(S(G,q))$ and hence $S(G,p)=S(G,q)$. Again, for
$i\in\\{1,2\\}$ we let $S(G_{i},q_{i})$ and $S(G_{i}^{\prime},q_{i})$ denote
the subspaces of $S(G^{\prime},q)$ corresponding to $G_{i}$ and
$G^{\prime}_{i}$, respectively. Let us choose stresses $\omega_{i,e}^{q}$ for
$(G^{\prime},q)$ analogously to how we chose $\omega_{i,e}$ for $(G,q)$ for
each $i\in\\{1,2\\}$ and $e\in E_{0}$, and let us also define the basis
$\mathcal{B}^{q}$ of $S(G,q)$ by

$\mathcal{B}^{q}=\mathcal{B}_{1}\cup\mathcal{B}_{2}\cup\\{\omega_{1,e}^{q}-\omega_{2,e}^{q}:e\in
E_{0}\\}.$

Our aim is to show that $S(G^{\prime},q)\supseteq S(G^{\prime},p)$. By Lemma
2.17(b) we have $S(G^{\prime},q)=S(G_{1}^{\prime},q_{1})\oplus
S(G_{2}^{\prime},q_{2})$, so by symmetry it suffices to show that
$S(G_{1}^{\prime},q_{1})\supseteq S(G_{1}^{\prime},p_{1})$. It follows from
Lemma 2.4 that the generic stresses of $G_{1}^{\prime}$ are dense in
$S(G^{\prime}_{1},p_{1})\subseteq M_{d,{G_{1}^{\prime}}}^{*}$ and hence it
suffices to show that $\omega_{1}^{\prime}\in S(G_{1}^{\prime},q_{1})$ for
such stresses. Let us thus fix a generic stress $\omega_{1}^{\prime}\in
S(G_{1}^{\prime},p_{1})$ of the subframework $(G^{\prime}_{1},p_{1})$. Since
$\mathcal{B}_{1}^{\prime}$ is a basis of $S(G^{\prime}_{1},p_{1})$, we may
write $\omega_{1}^{\prime}$ as $\omega_{1}+\sum_{e\in
E_{0}}\alpha_{e}\omega_{1,e}$ for some $\omega_{1}\in S(G_{1},p_{1})$ and
$\alpha_{e}\in\mathbb{C},e\in E_{0}$.

Let us consider the stress $\omega$ of $(G,p)$ defined by
$\omega=\omega_{1}+\sum_{e\in E_{0}}\alpha_{e}(\omega_{1,e}-\omega_{2,e})$.
Since $S(G,p)=S(G,q)$, we can write $\omega$ in the basis $\mathcal{B}^{q}$ as

$\omega=\omega_{1}^{q}+\omega_{2}^{q}+\sum_{e\in
E_{0}}\beta_{e}(\omega_{1,e}^{q}-\omega_{2,e}^{q}),$

where $\omega_{i}^{q}\in S(G_{i},q_{i}),i\in\\{1,2\\}$ and
$\beta_{e}\in\mathbb{C},e\in E_{0}$. Hence
$(\omega_{1}^{q})^{\prime}=\omega_{1}^{q}+\sum_{e\in
E_{0}}\beta_{i}\omega_{1,e}^{q}$ is in $S(G_{1}^{\prime},q_{1})$, and moreover
it agrees with $\omega_{1}^{\prime}$ on edges not in $E(K_{S})$. Since $(G,q)$
is generic, $(\omega_{1}^{q})^{\prime}$ is an almost generic $d$-stress. By
applying Corollary 3.18 to $G_{1}^{\prime},\omega_{1}^{\prime}$ and
$(\omega_{1}^{q})^{\prime}$ we obtain that
$\omega_{1}^{\prime}=(\omega_{1}^{q})^{\prime}$. It follows that
$\omega_{1}^{\prime}\in S(G_{1}^{\prime},q_{1})$, which is what we needed to
show. ∎

Combining Theorems 4.5 and 4.15 we obtain the following partial answer to
4.14. We note that the case when $d=2$ and $|V_{1}\cap V_{2}|=2$ follows from
[21, Corollary 5.5].

######  Corollary 4.17.

Let $G$ be the union of the graphs $G_{1}=(V_{1},E_{1}),G_{2}=(V_{2},E_{2})$
with $|V_{1}\cap V_{2}|\leq d+1$ and suppose that for every pair of vertices
$u,v\in V_{1}\cap V_{2}$, $\\{u,v\\}$ is $\mathcal{R}_{d}$-linked both in
$G_{1}$ and $G_{2}$. Then for every pair of vertices $u,v\in V_{1}\cap V_{2}$,
$\\{u,v\\}$ is globally linked in $G$ in $\mathbb{C}^{d}$ (and hence in
$\mathbb{R}^{d}$).

We close this subsection by considering the converse question: supposing that
for some vertices $u,v\in V(G_{1})$ the pair $\\{u,v\\}$ is ${d}$-stress-
linked in $G_{1}\cup G_{2}$, when can we deduce that it is also ${d}$-stress-
linked in $G_{1}$? Lemma 4.13 shows that this is the case when $G_{1}\cap
G_{2}$ is a complete graph. Now we consider the case when $V_{1}\cap V_{2}$
has size two, and show that if the vertex pair in the intersection is not
$\mathcal{R}_{d}$-linked in at least one of $G_{1}$ and $G_{2}$, then
$\\{u,v\\}$ is also ${d}$-stress-linked in $G_{1}$.

It is interesting to consider the analogous question for globally linked
pairs. If $V_{1}\cap V_{2}=\\{x,y\\}$ and $\\{x,y\\}$ is not
$\mathcal{R}_{d}$-linked in $G_{2}$, then it is not difficult to see that
$\\{u,v\\}$ is globally linked in $G_{1}$ in $\mathbb{C}^{d}$ if and only if
it is globally linked in $G_{1}\cup G_{2}$ in $\mathbb{C}^{d}$. If we replace
$\mathbb{C}^{d}$ by $\mathbb{R}^{d}$ then it is unclear whether the statement
remains true; we posed a special case as a conjecture in [10, Conjecture 5.7].
The case when $\\{x,y\\}$ is not $\mathcal{R}_{d}$-linked in $G_{1}$ seems
unclear even in the complex case.

######  Theorem 4.18.

Let $G$ the union of the induced subgraphs $G_{1}=(V_{1},E_{1})$ and
$G_{2}=(V_{2},E_{2})$ with $V_{1}\cap V_{2}=\\{x,y\\}$, and let $u,v\in V_{1}$
be a pair of vertices. Suppose that at least one of the following holds:

  1. (a)

$\\{x,y\\}$ is not $\mathcal{R}_{d}$-linked in $G_{2}$, or

  2. (b)

$\\{u,v\\}\neq\\{x,y\\}$ and $\\{x,y\\}$ is not $\mathcal{R}_{d}$-linked in
$G_{1}$.

Then the pair $\\{u,v\\}$ is ${d}$-stress-linked in $G$ if and only if
$\\{u,v\\}$ is ${d}$-stress-linked in $G_{1}$.

###### Proof.

We start by noting that under our assumption there is no
$\mathcal{R}_{d}$-circuit in $G$ that intersects both $G_{1}-G_{2}$ and
$G_{2}-G_{1}$. To the contrary, if there is such an $\mathcal{R}_{d}$-circuit
$C$, then by Lemma 2.13 we have $\\{x,y\\}\subseteq V(C)$. But then Lemma 2.14
implies that $\\{x,y\\}$ is contained in an $\mathcal{R}_{d}$-circuit of
$G_{i}+xy$, so the pair is $\mathcal{R}_{d}$-linked in $G_{i}$, for both
$i\in\\{1,2\\}$, contradicting our assumption.

Now let us prove the statement. If $u$ and $v$ are adjacent in $G$, then the
statement is trivial, so let us assume that $u$ and $v$ are nonadjacent. If
$\\{u,v\\}$ is ${d}$-stress-linked in $G_{1}$, then it is also ${d}$-stress-
linked in $G$ by Lemma 4.12. Let us thus assume that $\\{u,v\\}$ is
${d}$-stress-linked in $G$. In particular, $\\{u,v\\}$ is
$\mathcal{R}_{d}$-linked in $G$, so there is an $\mathcal{R}_{d}$-circuit $C$
in $G+uv$ that contains $uv$. By the discussion in the first paragraph we must
have $V(C)\subseteq V(G_{1})$. (Otherwise $V(C)\subseteq V(G_{2})$, which
would mean that $\\{u,v\\}=\\{x,y\\}$ and $\\{x,y\\}$ is
$\mathcal{R}_{d}$-linked in $G_{2}$, contradicting our assumption.) It follows
that $\\{u,v\\}$ is $\mathcal{R}_{d}$-linked in $G_{1}$.

Let $(G,p)$ be a generic realization in $\mathbb{C}^{d}$ and let
$(G_{i},p_{i})$ be the subframework corresponding to $G_{i}$, for
$i\in\\{1,2\\}$. By Lemma 2.17(c) we have $S(G,p)=S(G_{1},p_{1})\oplus
S(G_{2},p_{2})$, where by a slight abuse of notation we use $S(G_{i},p_{i})$
to denote the stresses of $(G,p)$ supported on $E(G_{i})$, for
$i\in\\{1,2\\}$. Let $\omega$ be a stress of $(G_{1}+uv,p_{1})$ that is
supported on the edges of $C$. By Proposition 4.3(d) it suffices to show that
$\omega$ is also a stress of $(G_{1}+uv,q_{1})$ for every generic
configuration $q_{1}\in K(G_{1},p_{1})$. Since $(G_{1},q_{1})$ is generic, we
have $S(G_{1},p_{1})=S(G_{1},q_{1})$. Let $(G,q)$ be the realization obtained
from $(G_{1},q_{1})$ by gluing a suitably scaled and rotated copy of
$(G_{2},p_{2})$ along $\\{u,v\\}$. Then by Lemma 2.17(c) again we have

$S(G,q)=S(G_{1},q_{1})\oplus S(G_{2},p_{2})=S(G_{1},p_{1})\oplus
S(G_{2},p_{2})=S(G,p),$

and hence $q\in K(G,p)$. Since $\\{u,v\\}$ is ${d}$-stress-linked in $G$, it
follows that $\omega$ is a stress of $(G+uv,q)$. But since $\omega$ is
supported on the edges of $C$ and $E(C)\subseteq E(G_{1})$, this implies that
$\omega$ is also a stress of $(G_{1}+uv,q_{1})$, as desired. ∎

###  4.3 Stress-linked pairs in low dimensions

In this subsection we give a combinatorial characterization of ${d}$-stress-
linked vertex pairs in the $d=1$ and $d=2$ cases. Both characterizations
involve the notion of _local connectivity_. Given a graph $G$ and a pair of
nonadjacent vertices $u,v\in V(G)$, let $\kappa_{G}(u,v)$ denote the maximum
number of pairwise internally disjoint $u,v$-paths in $G$. By Menger’s theorem
this is the same as the minimum size of a vertex set $S$ such that $u$ and $v$
are disconnected in $G-S$.

The following (easy) theorem characterizes ${1}$-stress-linked pairs.

######  Theorem 4.19.

Let $G$ be a graph and $u,v\in V(G)$ a nonadjacent pair of vertices. The
following are equivalent.

  1. (a)

$\\{u,v\\}$ is contained in a globally $1$-rigid subgraph of $G$.

  2. (b)

$\\{u,v\\}$ is ${1}$-stress-linked in $G$.

  3. (c)

$\\{u,v\\}$ is globally linked in $G$ in $\mathbb{C}^{1}$.

  4. (d)

$\\{u,v\\}$ is globally linked in $G$ in $\mathbb{R}^{1}$.

  5. (e)

$\kappa_{G}(u,v)\geq 2$.

###### Proof.

The first implication follows from Propositions 4.6 and 4.12, and the second
from Theorem 4.5. The third and four implications are immediate. Finally, if
$\kappa_{G}(u,v)\geq 2$, then there are two internally disjoint $u,v$-paths
$P_{1}$ and $P_{2}$ in $G$. Now $P_{1}\cup P_{2}$ is a $2$-connected (and
hence globally $1$-rigid) subgraph that contains $u$ and $v$. ∎

Theorem 4.20 below characterizes ${2}$-stress-linked vertex pairs. As we noted
in the Introduction, Jackson, Jordán and Szabadka conjectured in [21,
Conjecture 5.9] that the same condition characterizes globally linked pairs in
$\mathbb{R}^{2}$, and in [23, Conjecture 5.4], Jackson and Owen conjectured
the same for globally linked pairs in $\mathbb{C}^{2}$.

######  Theorem 4.20.

Let $G=(V,E)$ be a graph and let $u,v\in V$ be a pair of vertices. The pair
$\\{u,v\\}$ is ${2}$-stress-linked if and only if either $uv\in E$ or there is
some $\mathcal{R}_{2}$-connected subgraph $H$ of $G$ with $u,v\in V(H)$ and
$\kappa_{H}(u,v)\geq 3$.

###### Proof.

We first prove sufficiency by induction on $|V|$. Our proof is essentially the
same as that of [21, Theorem 5.7] (which is the analogous statement for
globally linked pairs in $\mathbb{R}^{2}$). The $|V|=2$ case is vacuous and
the case when $uv\in E$ is trivial, so let us suppose that $|V|\geq 3$ and $u$
and $v$ are nonadjacent in $G$. We need to show that $\\{u,v\\}$ is
${2}$-stress-linked in $G$. By Lemma 4.12 it suffices to show that $\\{u,v\\}$
is ${2}$-stress-linked in $H$, so we may suppose that $H=G$. If $G$ is
globally $2$-rigid, then we are done by Proposition 4.6. Hence let us assume
that this is not the case; since $G$ is $\mathcal{R}_{2}$-connected, Theorem
2.19(b) now implies that $G$ is not $3$-connected. On the other hand, it can
be deduced from Lemma 2.13 that $G$ is $2$-connected. It follows that there is
a separating vertex pair $\\{x,y\\}$ in $G$. We now have two cases: either
$\\{x,y\\}=\\{u,v\\}$, or $\\{x,y\\}\neq\\{u,v\\}$.

Let us first consider the case when $\\{x,y\\}=\\{u,v\\}$. Let $uw_{1}$ and
$vw_{2}$ be edges of $G$ such that $w_{1}$ and $w_{2}$ are in different
components of $G-\\{u,v\\}$. Since $G$ is $\mathcal{R}_{2}$-connected, there
is an $\mathcal{R}_{2}$-circuit $C$ in $G$ that contains both $uw_{1}$ and
$vw_{2}$. In particular, $\\{u,v\\}$ is a separating vertex pair of $C$. Let
$C_{1},C_{2}$ be obtained by a $2$-separation of $C$ along $\\{u,v\\}$. Lemma
2.14 implies that $C_{i}$ is an $\mathcal{R}_{2}$-circuit, and thus
$\\{u,v\\}$ is $\mathcal{R}_{2}$-linked in $C_{i}-uv$, for $i\in\\{1,2\\}$. It
follows from Theorem 4.15 that $\\{u,v\\}$ is ${2}$-stress-linked in $C$, and
consequently in $G$ as well.

Now let us consider the case when $\\{x,y\\}\neq\\{u,v\\}$. By the previous
reasoning we still get that $\\{x,y\\}$ is ${2}$-stress-linked in $G$, so we
may assume that $xy\in E$. Let $G_{1},G_{2}$ be obtained by a $2$-separation
of $G-xy$ along $\\{x,y\\}$ with $\\{u,v\\}\subseteq V(G_{1})$. Lemma 2.14
implies that $G_{1}$ is also $\mathcal{R}_{2}$-connected, and since $xy\in
E(G_{1})$ we also have $\kappa_{G_{1}}(u,v)\geq 3$. Thus by induction
$\\{u,v\\}$ is ${2}$-stress-linked in $G_{1}$, and hence by Lemma 4.12 it is
also ${2}$-stress-linked in $G$.

Next, we prove necessity by induction on $|E|$. The case when $|E|=1$ or
$uv\in E$ is immediate, and by Theorem 2.19 so is the case when $G$ is
globally $2$-rigid. Note that since $\\{u,v\\}$ is ${2}$-stress-linked, it is
also globally linked in $\mathbb{R}^{2}$ by Theorem 4.5, which implies that
$\kappa_{G}(u,v)\geq 3$. If there is an $\mathcal{R}_{2}$-bridge $e$ in $G$,
then $\\{u,v\\}$ is also ${2}$-stress-linked in $G-e$ by Theorem 4.8, and thus
we are done by induction. Hence we may assume that $G$ is not globally
$2$-rigid and that is does not contain $\mathcal{R}_{2}$-bridges. From Theorem
2.19(c) it follows that $G$ is not $3$-connected. If $G$ is not $2$-connected
or $G$ has an adjacent separating pair of vertices, then we can use Lemma 4.13
and induction. Thus we may assume that there is a separating pair of vertices
$\\{x,y\\}$ in $G$ such that $xy\notin E$. Let $G_{1}$ and $G_{2}$ be induced
subgraphs of $G$ such that $G=G_{1}\cup G_{2}$, $V(G_{1})\cap
V(G_{2})=\\{x,y\\}$ and $u,v\in V(G_{1})$.

If $\\{x,y\\}$ is not $\mathcal{R}_{d}$-linked in some of $G_{1}$ or $G_{2}$,
then by Theorem 4.18, $\\{u,v\\}$ is ${2}$-stress-linked in either $G_{1}$ or
$G_{2}$, so we are done by induction. Hence we may assume that $\\{x,y\\}$ is
$\mathcal{R}_{d}$-linked in both $G_{1}$ and $G_{2}$. If
$\\{u,v\\}=\\{x,y\\}$, then we can take an $\mathcal{R}_{2}$-circuit $C_{i}$
in $G_{i}+uv$ containing $uv$ such that $V(C_{i})\subseteq V(G_{i})$, for each
$i\in\\{1,2\\}$. By Lemma 2.14 $C_{1}\cup C_{2}-uv$ is an
$\mathcal{R}_{2}$-circuit with $\kappa_{C}(u,v)\geq 3$.444The observation that
$\kappa_{C}(u,v)\geq 3$ follows from the well-known fact that
$\mathcal{R}_{2}$-circuits are redundantly $2$-rigid, and in particular
redundantly $2$-connected. This implies that $\kappa_{C_{i}-uv}(u,v)\geq 2$
and hence $\kappa_{C}(u,v)\geq 4$.

Finally, suppose that $\\{u,v\\}\neq\\{x,y\\}$. Since $\\{u,v\\}$ is also
${2}$-stress-linked in $G+xy$, it is ${2}$-stress-linked in $G_{1}+xy$ by
Lemma 4.13. By induction, there is an $\mathcal{R}_{2}$-connected subgraph $H$
of $G_{1}+xy$ with $u,v\in V(H)$ and $\kappa_{H}(u,v)\geq 3$. If $xy\notin
E(H)$, then $H$ is also a subgraph of $G$ and we are done. Otherwise we can
take an $\mathcal{R}_{2}$-circuit $C_{2}$ of $G_{2}+xy$ and consider the graph
$H^{\prime}=H\cup C-xy$. By Lemma 2.14, $H^{\prime}$ is also
$\mathcal{R}_{2}$-connected and clearly $\kappa_{H^{\prime}}(u,v)\geq 3$ also
holds. ∎

##  5 Applications

In this section we show how the results of Section 4 can be applied to various
problems in rigidity theory. We start by significantly strengthening the main
result of [9]. A graph $G$ is _minimally globally $d$-rigid_ if it is globally
$d$-rigid but $G-e$ is not globally $d$-rigid for every edge $e\in E(G)$. In
[9] Jordán and the author proved that a minimally globally $d$-rigid graph on
at least $n\geq d+2$ vertices has at most $n(d+1)-\binom{d+2}{2}$ edges, and
that the inequality is strict unless $G$ is the complete graph on $d+2$
vertices. We shall now prove that such a sparsity bound holds for every
induced subgraph of $G$ on at least $d+2$ vertices. We will need the following
result about the rigidity matroid of globally $d$-rigid graphs.

######  Theorem 5.1.

[8, Theorem 3.5] If $G$ is a globally $d$-rigid graph on at least $d+2$
vertices, then it is $\mathcal{R}_{d}$-connected.

######  Theorem 5.2.

Let $G=(V,E)$ be a graph on $n\geq d+2$ vertices and suppose that for every
edge $uv\in E$, $\\{u,v\\}$ is not ${d}$-stress-linked in $G-uv$. Then
$|E|\leq r_{d}(G)+n-d-1$, with equality if and only if $G=K_{d+2}$.

###### Proof.

Let $G_{0}=(V,E_{0})$ be a maximal $\mathcal{R}_{d}$-independent spanning
subgraph of $G$, let $E-E_{0}=\\{e_{1},\ldots,e_{k}\\}$ and let us define
$G_{i}=G_{0}+\\{e_{1},\ldots,e_{i}\\}$ for each $i\in\\{1,\ldots,k\\}$. The
maximal choice of $G_{0}$ and the assumption on $G$ imply that the pair of end
vertices $\\{u_{i},v_{i}\\}$ of $e_{i}$ is $\mathcal{R}_{d}$-linked, but not
${d}$-stress-linked in $G_{i-1}$, for each $i\in\\{1,\ldots,k\\}$. Hence we
have

$d+1\leq
k_{\text{sh}}(G,d)=k_{\text{sh}}(G_{k},d)<k_{\text{sh}}(G_{k-1},d)<\ldots<k_{\text{sh}}(G_{1},d)<k_{\text{sh}}(G_{0},d)\leq
n.$

It follows that $k\leq n-d-1$ and

$|E|=|E_{0}|+k\leq r_{d}(G)+n-d-1.$

It only remains to characterize the cases of equality. Let us thus assume that
$|E|=r_{d}(G)+n-d-1$. The argument in the first paragraph now gives
$k_{\text{sh}}(G,d)=d+1$, so by Theorem 4.1, $G$ is globally $d$-rigid. We
first claim that every $\mathcal{R}_{d}$-circuit in $G$ is a copy of
$K_{d+2}$. Suppose for a contradiction that this is not the case and let $C$
be an $\mathcal{R}_{d}$-circuit in $G$ that is not isomorphic to $K_{d+2}$.
Let $e\in E(C)$ be an arbitrary edge of $C$. Now $C-e$ is
$\mathcal{R}_{d}$-independent, and hence we may extend it to a maximal
$\mathcal{R}_{d}$-independent subgraph $G_{0}^{\prime}=(V,E_{0}^{\prime})$.
Note that $G_{1}^{\prime}=G_{0}^{\prime}+e$ contains the circuit $C$, so by
Lemma 4.10 we have $k_{\text{sh}}(G_{1},d)\leq n-2$. We can now repeat the
argument of the first paragraph with $G_{0}^{\prime}$ and starting with the
edge $e_{1}=e$ to deduce that $|E-E_{0}|\leq n-d-2$ and thus
$|E|<r_{d}(G)+n-d-1$, contradicting our choice of $G$.

The rest of the proof follows that of [9, Theorem 3.7]. By Theorem 5.1, $G$ is
$\mathcal{R}_{d}$-connected, and thus every pair of edges in $G$ is contained
in an $\mathcal{R}_{d}$-circuit. Since every $\mathcal{R}_{d}$-circuit of $G$
is complete, this means that every pair of edges in $G$ is contained in a
complete subgraph. But a graph with this property and without isolated
vertices must be necessarily complete: if $u$ and $v$ are arbitrary vertices
and $e$ and $f$ are edges incident to $u$ and $v$, respectively, then the fact
that $e$ and $f$ are contained in a complete subgraph shows that $u$ and $v$
must be adjacent in $G$.

Thus $G$ is a complete graph on at least $d+2$ vertices. It is well-known that
if $n\geq d+3$, then $G-uv$ is globally $d$-rigid for any edge $uv$, and thus
by Proposition 4.6, $\\{u,v\\}$ is ${d}$-stress-linked in $G-uv$,
contradicting our assumption on $G$. It follows that $G=K_{d+2}$, as claimed.
∎

######  Corollary 5.3.

If $G$ is minimally globally $d$-rigid, then for each subset $X\subseteq V(G)$
of vertices with $|X|\geq d+2$ we have

$|E(X)|\leq r_{d}(G[X])+|X|-d-1\leq(d+1)|X|-\binom{d+2}{2}.$

The first inequality is strict unless $G[X]=K_{d+2}$.

###### Proof.

Let us fix $X\subseteq V(G)$. If $|X|=d+2$, then it is easy to see that the
first inequality is satisfied and that it holds with equality if and only if
$G[X]=K_{d+2}$. Thus let us suppose that $|X|\geq d+3$ and let us consider a
pair of vertices $u,v\in X$ with $uv\in E(G)$. Since $G$ is minimally globally
$d$-rigid, $\\{u,v\\}$ is not globally linked in $G-uv$ in $\mathbb{C}^{d}$,
and hence it is not globally linked in $G[X]-uv$ in $\mathbb{C}^{d}$. By
Theorem 4.5 it follows that $\\{u,v\\}$ is not ${d}$-stress-linked in
$G[X]-uv$. Thus Theorem 5.2 applies and gives $|E(X)|<r_{d}(G[X])+|X|-d-1$.
The second inequality follows from the bound $r_{d}(G[X])\leq
d|X|-\binom{d+1}{2}$ by a straightforward calculation. ∎

Corollary 4.9 and Theorem 4.15 let us prove two conjectures that are unrelated
to the notion of globally linked pairs or global rigidity. In [3], Connelly