# Super Stable Tensegrities and Colin de Verdière Number $\nu$

Ryoshun Oba and Shin-ichi Tanigawa Department of Mathematical Informatics,
Graduate School of Information Science and Technology, University of Tokyo,
7-3-1 Hongo, Bunkyo-ku, 113-8656, Tokyo Japan. email:
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

A super stable tensegrity introduced by Connelly in 1982 is a globally rigid
discrete structure made from stiff bars or struts connected by cables with
tension. In this paper we show an exact relation between the maximum dimension
that a multigraph can be realized as a super stable tensegrity and Colin de
Verdière number $\nu$ from spectral graph theory. As a corollary we obtain a
combinatorial characterization of multigraphs that can be realized as
3-dimensional super stable tensegrities.

Keywords: graph rigidity, tensegrities, super stability, Colin de Verdière
number $\nu$, minor monotonicity

##  1 Introduction

A tensegrity is a stable discrete structure made from stiff bars or struts111A
strut is a rod-shaped material which can stretch but cannot shrink. connected
by cables with tension. See Figure 1. Since its invention by American sculptor
Kenneth Snelson, a tensegrity has attracted wide attention not only in
structural engineering but also in mathematics, see, e.g., [9]. One of the
challenges in the study of tensegrities is to understand the impact of the
combinatorics underlying stable tensegrities. The aim of this paper is to
relate such a combinatorial question in the tensegrity analysis to a topic in
spectral graph theory and derive combinatorial characterizations of the graphs
of stable tensegrities.

(a)

(b)

Figure 1: (a) Prism tensegrity and (b) dihedral star tensegrity. They are
tensegrity realizations of $K_{2,2,2}$ and $Q_{3}$, respectively.

Mathematically, a tensegrity in $\mathbb{R}^{d}$ is just a triple
$(G,\sigma,p)$, where $G$ is a multigraph222Throughout the paper, a multigraph
is an undirected graph which may contain parallel edges but no loop. with a
finite vertex set $V(G)$ and an edge set $E(G)$,
$\sigma:E(G)\rightarrow\\{+,-\\}$ is a sign function, and
$p:V(G)\rightarrow\mathbb{R}^{d}$ is a point configuration in the
$d$-dimensional Euclidean space $\mathbb{R}^{d}$. Such a tensegrity
$(G,\sigma,p)$ models a physical structure by regarding each edge $e$ with
$\sigma(e)=+$ as a cable and each edge $e$ with $\sigma(e)=-$ as a strut.
Thus, a deformation of a tensegrity $(G,\sigma,p)$ is defined as another
tensegrity $(G,\sigma,q)$ with the same underlying signed graph $(G,\sigma)$
and

$\begin{array}[]{cc}\|p(i)-p(j)\|\geq\|q(i)-q(j)\|&\text{if $\sigma(ij)=+$}\\\
\|p(i)-p(j)\|\leq\|q(i)-q(j)\|&\text{if $\sigma(ij)=-$},\end{array}$

for every edge $ij\in E(G)$, where $\|\cdot\|$ denotes the Euclidean norm. A
deformation represents a possible deformed tensegrity of the given tensegrity
$(G,\sigma,p)$ under the cable and strut constraints of $(G,\sigma,p)$.

It should be remarked that the notation defined above is slightly different
from the standard [7, 9, 22]. In [7, 9, 22], the underlying graph of a
tensegrity is always a simple graph and a sign function $\sigma$ allows to
take value $0$ to represent a bar (which cannot stretch or shrink). In our
modeling, a bar can be represented by parallel edges with opposite signs, and
hence ours is essentially identical to the standard model in [7, 9, 22].
However, our unconventional notation using multigraphs turns out to be crucial
in the development of a new combinatorial theory.

Once we have defined deformations, the rigidity of tensegrities can be
naturally defined as follows. Two point configurations $p,q$ in
$\mathbb{R}^{d}$ are said to be congruent if one is the image of an Euclidean
isometry of the other, and two tensegrities $(G,\sigma,p)$ and $(G,\sigma,q)$
are congruent if $p$ and $q$ are congruent. A tensegrity $(G,\sigma,p)$ in
$\mathbb{R}^{d}$ is globally rigid if any deformation of $(G,\sigma,p)$ in
$\mathbb{R}^{d}$ is congruent to $(G,\sigma,p)$. It is called a locally rigid
if there is an open neighborhood $N$ of $p$ in the space of point
configurations such that any deformation $(G,\sigma,q)$ of $(G,\sigma,p)$ with
$q\in N$ is congruent to $(G,\sigma,p)$.

Testing local/global rigidity is known to be a hard problem even if a
tensegrity is a bar-joint framework. The situation is even worse for
tensegrities since a generic assumption for point configurations does not seem
as powerful as the ordinary bar-joint case, see, e.g. [16, 14]. Hence, the
standard approach in practice is to check a sufficient condition. Commonly
used sufficient conditions for rigidity are infinitesimal rigidity [22],
prestress stability [10], and super stability [7].

In this paper, we focus on super stability. This concept was introduced by
Connelly [7] in 1982 and it is currently the only general sufficient condition
for global rigidity of tensegrities. Roughly speaking, a tensegrity becomes
super stable if the point configuration is the unique minimizer of a convex
harmonic potential function, and hence it has an advantage of being robust
with respect to perturbations. Such an advantage has been well appreciated and
used in the design of new tensegrities in structural engineering, see,
e.g.,[9, 23]. However, unlike the recent rapid development of the global
rigidity theory of bar-joint frameworks (see, e.g., [19]), little mathematical
progress has been made for the combinatorics of tensegrities.

A tensegrity is said to be $d$-dimensional333Throughout the paper, we
distinguish a tensegrity in $\mathbb{R}^{d}$ and a $d$-dimensional tensegrity.
A tensegrity in $\mathbb{R}^{d}$ just means a tensegrity each of whose point
is in $\mathbb{R}^{d}$ and the affine span of the points may not be
$d$-dimensional. if the affine span of its point configuration is equal to
$d$. In this paper, we study the class of multigraphs which can be realized as
$d$-dimensional super stable tensegrities for a given positive integer $d$. We
show that (the complement of) this multigraph class admits a characterization
in terms of forbidden minors, and give a complete list of minors in the case
when $d\leq 3$. Specifically, we obtain the following.

######  Theorem 1.1.

Let $G$ be a multigraph. Then $G$ has a three-dimensional super stable
tensegrity realization if and only if it contains a multigraph in Figure 2 as
a minor.

The proof even shows that, if $G$ has a 3-dimensional super stable
realization, then such a realization of $G$ can be obtained from a super
stable realization of a graph in Figure 2 by a sequence of edge addition and
vertex splitting (that is, the inverse of edge contraction). In this sense,
super stable realizations of the graphs in Figure 2 is the bases of the
construction. Moreover, any graph in Figure 2 except $K_{5}$ can be
constructed from the cube graph $Q_{3}$ (the second left graph in the top row
of Figure 2) by a sequence of Y-$\Delta$ operations. Since a Y-$\Delta$
operation preserves the super stability, we may even consider that $K_{5}$ and
$Q_{3}$ are the bases of the underlying multigraphs of $3$-dimensional super
stable tensegrities. Interestingly, a super stable realization of $Q_{3}$ has
been well investigated as a dihedral star-shaped tensegrity in the engineering
context [24], see Figure 1(b).

$K_{5}$

$Q_{3}$

$K_{2,2,2}$

$\nabla K_{4}$

$K_{4}^{=}$

Figure 2: List of minors in the characterization of Theorem 1.1.

The proof of our characterization is actually a corollary of van der Holst’s
theorem [13] on the characterization of multigraphs with bounded Colin de
Verdière number $\nu$. We will establish an exact relation between the super
stability of tensegrities and the Colin de Verdière number $\nu$, a spectral-
based graph parameter introduced by Colin de Verdière [6] in 1998.

We should also remark that realizations in Theorem 1.1 are not guaranteed to
be injective, and some cables or struts may have zero length in the
realizations. However, the technique for constructing super stable
realizations with respect to minor operations can be further extended, and we
are able to derive sufficient combinatorial conditions for injective
realizability. Below we give an example of our sufficient conditions.

######  Theorem 1.2.

Suppose a 2-connected multigraph $G$ contains $K_{d+2}$ as a minor. Then $G$
has a $d$-dimensional injective super stable tensegrity realization.

The dihedral star tensegrity in Figure 1(b) has attracted attention since the
underlying graph is 3-regular and is much sparser than generic rigid
tensegrities. Since there is an infinite family of 3-regular graphs that
contains $K_{d+2}$ as a minor, Theorem 1.2 implies that there is an infinite
number of such examples in any dimension.

######  Corollary 1.3.

For any fixed $d$, there is an infinite family of 3-regular graphs that can be
realized as $d$-dimensional injective super stable tensegrities.

As a dual concept of super stable realizability, we also introduce the
realizable dimension of multigraphs, which is a tensegrity extension of the
realizable dimension of graphs given by Belk and Connelly [4]. We give a
forbidden-minor characterization of multigraphs with realizable dimension at
most one.

The paper is organized as follows. In Section 2 we review Connelly’s super
stability theorem and give the definition of super stable tensegrities. We
then introduce new multigraph parameters, super stability number $\lambda$ and
realizable dimension ${\rm rd}$, which are the main objects of this study. In
Section 3 we show how to build super stable tensegrities based on simple graph
operations. As a corollary, we prove the minor monotonicity of the super
stability number $\lambda$. We will also discuss how to construct injective
tensegrity realizations. A relation between super stability and the Colin de
Verdière number $\nu$ is discussed in Section 4. In Section 5 we give
relations among $\lambda$, ${\rm rd}$, and other basic graph parameters. In
Section 6 we discuss the characterization problem of multigraphs with bounded
realizable dimension.

Throughout the paper we use the following basic terminology from graph theory.
For a multigraph $G$, $V(G)$ and $E(G)$ denote the vertex set and the edge set
of $G$, respectively. $N_{G}(v)$ denotes the set of vertices adjacent to $v$
in $G$ and $E_{G}(v)$ denotes the set of edges incident to $v$ in $G$. We
sometimes denote an edge $e$ by $e=uv$ when the endvertices of an edge $e$ are
$u$ and $v$.

A vertex subset $X$ is called a clique if the subgraph induced by $X$ is
complete. A maximal clique is a clique which is not a proper subset of a
clique in $G$. For a multigraph $G$, $\omega(G)$ denotes the clique number
(i.e., the size of a maximum clique). Also, let $\kappa(G)$ be the maximum
connectivity over all minors of $G$ and let ${\rm tw}(G)$ be the treewidth of
$G$. (See Section 6 for the definition.)

The simplified graph ${\rm si}(G)$ of a multigraph $G$ is obtained from $G$ by
replacing each parallel edges with a single edge. Conversely, for a multigraph
$G$, let $G^{=}$ be the multigraph obtained from $G$ by making each simple
edge in parallel.

In this paper a bar-joint framework is defined as a tensegrity
$(G^{=},\sigma,p)$ such that each parallel edge classes has both positive and
negative edges (so that the interpoint distance between $p(u)$ and $p(v)$ is
fixed for each edge $uv$ in $G$). We sometimes abbreviate it to $(G,p)$.

##  2 Super Stability Number and Realizable Dimension

In this section, we give a formal definition of super stability of
tensegrities, and then introduce new multigraph parameters, super stability
number and realizable dimension.

###  2.1 Super Stability of Tensegrities

We follow a modern exposition of super stability in terms of semidefinite
programming, see, e.g.,[15].

Let $V=\\{1,2,\dots,n\\}$ be a finite set. We identify a point configuration
$p:V\rightarrow\mathbb{R}^{d}$ with a matrix $P\in\mathbb{R}^{d\times n}$
whose $i$th column vector is $p(i)$ for all $i\in V$. For a configuration
$p:V\rightarrow\mathbb{R}^{d}$, the Gram matrix of $p$, denoted by
$\operatorname{Gram}(p)$, is a $n\times n$ matrix whose $ij$-th entry is
$p(i)^{\top}p(j)$. Equivalently, $\operatorname{Gram}(p)=P^{\top}P$. Since the
properties of tensegrities we are interested in are invariant by translation,
we may always assume that the center of gravity of $\\{p(i):i\in V\\}$ is at
the origin, that is, $P\mathbf{1}_{n}=0$, where $\mathbf{1}_{n}$ denotes the
all-one vector in $\mathbb{R}^{n}$.

Given a multigraph $G=(V,E)$ with an edge weight
$\omega:E\rightarrow\mathbb{R}$, its weighted Laplacian $L_{G,\omega}$ is
defined by

$L_{G,\omega}:=\sum_{e=ij\in E}\omega(ij)F_{ij},$

where

$F_{ij}:=(\bm{e}_{i}-\bm{e}_{j})(\bm{e}_{i}-\bm{e}_{j})^{\top}$

and $\bm{e}_{i}$ is the $n$-dimensional vector whose $i$-th coordinate is one
and the remaining entries are zero. Let $\mathcal{L}^{n}$ be the set of all
Laplacian matrices over all multigraphs with $n$ vertices. Then
$\mathcal{L}^{n}$ is a linear subspace of the space $\mathcal{S}^{n}$ of
symmetric matrices of size $n$ given by

$\mathcal{L}^{n}={\rm span}\\{F_{ij}:i,j\in V,i\neq j\\}.$

The set of positive semidefinite Laplacian matrices is denoted by
$\mathcal{L}_{+}^{n}$.

Given a tensegrity $(G,\sigma,p)$, consider the following semidefinite
programming problem $\text{P}_{(G,\sigma,p)}$:

$\begin{array}[]{lllr}\text{($\text{P}_{(G,\sigma,p)}$)}&\text{maximize}&0\\\
&\text{subject to }&\langle X,F_{ij}\rangle\leq\|p(i)-p(j)\|^{2}&\quad(ij\in
E\text{ with }\sigma(ij)=+1)\\\ &&\langle
X,F_{ij}\rangle\geq\|p(i)-p(j)\|^{2}&\quad(ij\in E\text{ with
}\sigma(ij)=-1)\\\ &&X\succeq 0\\\ &&X\in\mathcal{L}^{n},\end{array}$

where $\langle\cdot,\cdot\rangle$ denotes the Frobenius inner product and
$X\succeq 0$ means that $X$ is positive semidefinite. The feasible region of
$\text{P}_{(G,\sigma,p)}$ describes deformations of $(G,\sigma,p)$ in the
sense that $(G,\sigma,q)$ is a deformation of $(G,\sigma,p)$ if
$X=\operatorname{Gram}(q)$ is feasible in $\text{P}_{(G,\sigma,p)}$. Hence, if
$\text{P}_{(G,\sigma,p)}$ has the unique solution (which must be
$X=\operatorname{Gram}(p)$), then $(G,\sigma,p)$ is globally rigid. A
tensegrity $(G,\sigma,p)$ having the property that $\text{P}_{(G,\sigma,p)}$
has the unique solution is called _universally rigid_ , and the property has
been extensively studied, see, e.g.,[2, 15].

Connelly’s super stability theorem given below guarantees the universal
rigidity in terms of the existence of a certain equilibrium stress. A map
$\omega:E\rightarrow\mathbb{R}$ is called an _equilibrium stress_ of a
tensegrity $(G,\sigma,p)$ if

$\displaystyle\sum_{j\in
N_{G}(i)}\omega(ij)\left(p(j)-p(i)\right)=0\qquad(i\in V)$ (1)

holds, and it is called _proper_ if $\sigma(ij)\omega(ij)\geq 0$ for each
$ij\in E(G)$. It is _strictly proper_ if $\sigma(ij)\omega(ij)>0$ for each
$ij\in E(G)$.

######  Theorem 2.1 (Connelly’s super stability theorem [7]).

A $d$-dimensional tensegrity $(G,\sigma,p)$ is universally rigid (and hence
globally rigid) if the following two conditions are satisfied.

(i) Stress Condition:

There exists a strictly proper equilibrium stress
$\omega:E(G)\rightarrow\mathbb{R}$ such that $L_{G,\omega}\succeq 0$ and
$\dim\ker L_{G,\omega}=d+1$.

(ii) Conic Condition:

The edge directions of $(G,p)$ do not lie on a conic at infinity, i.e., there
exists no nonzero matrix $S\in\mathcal{S}^{d}$ such that

$\left(p(j)-p(i)\right)^{\top}S\left(p(j)-p(i)\right)=0\quad\forall ij\in
E(G).$

A $d$-dimensional tensegrity $(G,\sigma,p)$ is said to be super stable if it
satisfies the stress condition and the conic condition in Theorem 2.1.

###  2.2 Super Stability Number

A tensegrity $(G,\sigma,p)$ is called a tensegrity realization of a multigraph
$G$. Based on the concept of super stability, we now introduce a new graph
parameter, the super stability number, as follows. For a connected multigraph
$G$, the super stability number of $G$ is defined by

$\lambda(G):=\max\\{d\in\mathbb{Z}:\text{$G$ has a $d$-dimensional super
stable tensegrity realization}\\}.$

For a general graph $G$, the super stability number is defined by

$\lambda(G):=\max\\{\lambda(H):\text{$H$ is a connected component of $G$}\\}.$

Example 1 (Tree). Suppose $G$ is a single-edge graph, that is,
$V(G)=\\{u,v\\}$ and $E(G)=\\{uv\\}$. If a tensegrity realization
$(G,\sigma,p)$ of $G$ is 1-dimensional, then there is no nonzero edge weight
$\omega:E(G)\rightarrow\mathbb{R}$ satisfying the equilibrium condition (1).
Hence, $\lambda(G)<1$. On the other hand, if $(G,\sigma,p)$ is a 0-dimensional
tensegrity realization such that $\sigma(uv)=+$, then the edge weight $\omega$
with $\omega(uv)=1$ satisfies the equilibrium condition (1). Then,
$L_{G,\omega}=\begin{pmatrix}1&-1\\\ -1&1\end{pmatrix}$, which is a rank-one
positive semidefinite matrix. Thus, $(G,\sigma,p)$ satisfies the stress
condition for super stability. In this case, the conic condition is null, and
hence $(G,\sigma,p)$ is super stable, and $\lambda(G)=0$.

This argument can be adapted to a general tree to show that $\lambda(G)=0$ if
$G$ is a tree.

Example 2 (Cycle). Suppose $G$ is a cycle $C_{n}$ with
$V(C_{n})=\\{v_{1},\dots,v_{n}\\}$ and
$E(C_{n})=\\{v_{1}v_{2},\dots,v_{n-1}v_{n},v_{n}v_{1}\\}$. If a tensegrity
realization $(C_{n},\sigma,p)$ of $G$ is 2-dimensional, then there is a vertex
$v_{i}$ such that $p(v_{i-1})-p(v_{i})$ and $p(v_{i+1})-p(v_{i})$ are not
colinear, or $p(v_{i-1})=p(v_{i})$ and $p(v_{i+1})\neq p(v_{i})$ (or
$p(v_{i-1})\neq p(v_{i})$ and $p(v_{i+1})=p(v_{i})$). In either case, the
equilibrium condition cannot hold for any edge weight $\omega$. So
$\lambda(C_{n})<2$ follows.

On the other hand, consider a 1-dimensional tensegrity realization
$(C_{n},\sigma,p)$ such that $p(v_{1}),p(v_{2}),\dots,p(v_{n})$ are placed
even spaced apart in this ordering on the line. Then, an edge weight $\omega$
given by $\omega(v_{n}v_{1})=-1$ and $\omega(v_{i}v_{i+1})=n-1$ for
$i=1,\dots,n$ satisfies the equilibrium condition. One can check that
$L_{C_{n},\omega}$ is positive semidefinite with $\dim\ker
L_{C_{n},\omega}=2$, and $\lambda(C_{n})=1$ follows.

Example 3 (Complete graph). Consider $K_{4}$ drawn in the plane such that the
four points form the vertices of the unit square. If the outer cycle is the
cable and the inner diagonal two edges are struts, it admits a strictly proper
equilibrium stress $\omega$ for $\omega(e)=1$ for each edge in the outer cycle
and $\omega(e)=-1$ for each diagonal. Then,
$L_{K_{4},\omega}=\begin{pmatrix}1&-1&1&-1\end{pmatrix}^{\top}\begin{pmatrix}1&-1&1&-1\end{pmatrix}$,
which is a rank-one positive semidefinite matrix. Since it also satisfies the
conic condition, $\lambda(K_{4})\geq 2$ follows.

More generally, consider the complete graph $K_{n}$ with $n$ vertices and
$p:[n]\rightarrow\mathbb{R}^{n-2}$ in general position. Since there are $n$
points in $\mathbb{R}^{n-2}$, they are affinely dependent, i.e., $\sum_{v\in
V}a_{v}p(v)=0$ for some nonzero $a_{v}$ with $\sum_{v\in V}a_{v}=0$. Define
$\omega:E(K_{n})\rightarrow\mathbb{R}$ by $\omega(uv)=a_{u}a_{v}$ and
$\sigma:E(K_{n})\rightarrow\\{-,+\\}$ by $\sigma(uv)={\rm sign}(\omega(uv))$.
Then, $\omega$ is a strictly proper equilibrium stress of $(K_{n},\sigma,p)$.
Moreover,
$L_{K_{n},\omega}=\begin{pmatrix}a_{1}&\dots&a_{n}\end{pmatrix}^{\top}\begin{pmatrix}a_{1}&\dots&a_{n}\end{pmatrix}$,
which is a rank-one positive semidefinite matrix. Since $(K_{n},\sigma,p)$
also satisfies the conic condition, we have $\lambda(K_{n})\geq n-2$.

We indeed have $\lambda(K_{n})=n-2$ since no $(n-1)$-dimensional tensegrity
realization of $K_{n}$ has a strictly proper equilibrium stress.

Example 4 (Complete multigraphs). Let $K_{n}^{=}$ be the graph obtained from
$K_{n}$ by duplicating each edge in parallel. The resulting graph is called
the complete multigraph with $n$ vertices. Consider a tensegrity realization
$(K_{n}^{=},\sigma,p)$ of $K_{n}^{=}$ such $p:[n]\rightarrow\mathbb{R}^{n-1}$
is in general position and $\sigma(e_{1})=-\sigma(e_{2})$ for each parallel
pair of edges $e_{1},e_{2}$. Then $(K_{n}^{=},\sigma,p)$ satisfies the conic
condition. To see the stress condition, consider an edge weight $\omega$ by
setting $\omega(e_{1})=-\omega(e_{2})\neq 0$ for each parallel pair of edges
$e_{1},e_{2}$. Then, $\omega$ is strictly proper equilibrium stress (since the
net stress between two points is zero) and the resulting
$L_{K_{n}^{=},\omega}$ is the zero matrix (which has nullity $n$). Hence,
$(K_{n}^{=},\sigma,p)$ is super stable and $\lambda(K_{n}^{=})=n-1$ follows.

The discussion in Example 4 is worth emphasized. Even in a strictly proper
stress of a tensegrity realization, the net stress between two vertices $u$
and $v$ can be zero if there are parallel edges between $u$ and $v$. This is
consistent with the conventional bar-joint case, where the value of a stress
can be zero along a bar in Connelly’s super stability theorem. (Recall that
parallel edges represent a bar constraint in our tensegrity modeling.)

###  2.3 Spectral view of super stability

We now explain how the super stability number can be understood from the view
of spectral graph theory. The key is an analogy between the conic condition
and the Strong Arnold property from the Colin de Verdière number. Such an
analogy (or a connection) has been already observed in e.g.,[21, 8, 18] and we
will exploit it in this paper.

For a symmetric $n\times n$ matrix $S$, a kernel matrix $P$ of $S$ is a matrix
whose row vectors form an orthogonal basis of $\ker A$. Each kernel matrix $P$
defines a corresponding configuration of $n$ points by regarding each column
as a point in a Euclidean space. The corresponding point configuration is
called a kernel representation. If $A$ is a weighted Laplacian of $G$ with
$\dim\ker A=d+1$, then we can take a kernel matrix $P$ such that the last row
of a kernel matrix $P$ is the all-one vector. Let $P^{\prime}$ be the matrix
obtained from $P$ by ignoring the last row. $P^{\prime}$ defines a point
configuration in $\mathbb{R}^{d}$ by regarding each column as a point, which
is called a reduced kernel representation with respect to $A$.

Reduced kernel representations enable us to reduce the problem of finding a
super stable realization of a given graph $G$ to a problem of finding a
Laplacian matrix supported by $G$ with a certain spectral property. To see
this, we first define the space of Laplacian matrices supported by $G$ by

$\displaystyle{\cal L}^{*}(G):$
$\displaystyle=\left\\{L_{G,\omega}\mid\omega:E(G)\rightarrow\mathbb{R}\setminus\\{0\\}\right\\}.$

Note that

$\displaystyle{\cal L}^{*}(G)=\left\\{L\in{\cal
L}^{n}\mid\begin{array}[]{ll}L[i,j]=0&\text{if $G$ has no edge between $i$ and
$j$}\\\ L[i,j]\neq 0&\text{if $G$ has a single edge between $i$ and $j$}\\\
L[i,j]\in\mathbb{R}&\text{if $G$ has parallel edges between $i$ and
$j$}\end{array}\right\\}.$

The (Euclidean) closure of ${\cal L}^{*}(G)$ is

$\displaystyle{\cal L}(G):=\left\\{L\in{\cal
L}^{n}\mid\begin{array}[]{ll}L[i,j]=0&\text{if $G$ has no edge between $i$ and
$j$}\\\ L[i,j]\in\mathbb{R}&\text{if $G$ has an edge between $i$ and
$j$}\end{array}\right\\},$

which is a linear subspace of ${\cal L}^{n}$. Let ${\cal L}_{k}^{n}$ be the
subset of ${\cal L}^{n}$ consisting of matrices of rank $k$ and ${\cal
L}_{+,k}^{n}$ be the subset of ${\cal L}_{k}^{n}$ consisting of positive
semidefinite matrices.

The following proposition is fundamental and has been already used in several
places before.

######  Proposition 2.2.

Let $G$ be a multigraph, $L\in{\cal L}^{*}(G)\cap{\cal L}_{+,n-(d+1)}^{n}$,
and $p$ be a reduced kernel representation of $L$. From $L$, construct444There
are choices for the weight on parallel edges, and we may choose arbitrary so
that the weight is nonzero on each edge. an edge weight
$\omega:E(G)\rightarrow\mathbb{R}\setminus\\{0\\}$ and a sign function
$\sigma:E(G)\rightarrow\\{-,+\\}$ such that $L_{G,\omega}=L$ and
$\sigma(e)={\rm sign}(\omega(e))$ for every edge $e$. Then $\omega$ is a
strictly proper equilibrium stress of a tensegrity realization $(G,\sigma,p)$
of $G$ such that $L_{G,\omega}\succeq 0$ and $\dim\ker L_{G,\omega}=d+1$.

###### Proof.

Since $p$ is a reduced kernel representation of $L$, we have
$PL_{G,\omega}=PL=0$, which is equivalent to the equilibrium condition (1).
Hence, $\omega$ is an equilibrium stress of $(G,\sigma,p)$. The remaining
properties directly follow from $L\in{\cal L}_{+,n-(d+1)}^{n}$. ∎

Hence, the tensegrity realization obtained by the construction of Proposition
2.2 always satisfies the stress condition for super stability; thus, finding a
$d$-dimensional realization satisfying the stress condition reduces to
deciding whether ${\cal L}^{*}(G)\cap{\cal L}_{+,n-(d+1)}^{n}\neq\emptyset$.

The next question is whether the conic condition for super stability can be
also understood in terms of Laplacian matrices. This is indeed possible by
exploiting an analogy with the strong Arnold property. The strong Arnold
property introduced by Colin de Veridere is a non-degeneracy condition for
symmetric matrices (see Section 6 for the definition), and it admits several
equivalent characterizations [12, 20]. By interpreting such characterizations
in the space of Laplacian matrices, we have the following. (See [18] for a
proof.)

######  Proposition 2.3.

Let $G$ be a graph with $n$ vertices. The followings are equivalent for
$L\in{\cal L}^{*}(G)\cap{\cal L}^{n}_{n-(d+1)}$:

(i)

${\cal L}(G)$ and ${\cal L}^{n}_{n-(d+1)}$ intersect transversally555Two
smooth manifolds $N,N^{\prime}$ in $\mathbb{R}^{m}$ intersect transversally at
$x\in N\cap N^{\prime}$ if $T_{x}N+T_{x}N^{\prime}=\mathbb{R}^{m}$, where
$T_{x}N$ denotes the tangent space of $N$ at $x$. at $L$ in the space ${\cal
L}^{n}$ of Laplacian matrices.

(ii)

There is no nonzero $X\in{\cal L}^{n}$ satisfying $XL=0$ and $\langle
X,(e_{i}-e_{j})(e_{i}-e_{j})^{\top}\rangle=0$ for every $ij\in E(G)$.

(iii)

Let $p:V(G)\rightarrow\mathbb{R}^{d}$ be a reduced kernel representation of
$L$. Then the edge directions of $(G,p)$ do not lie on a conic at infinity.

The equivalence between Conditions (ii) and (iii) in Proposition 2.3 gives a
translation of the conic condition in the language of Laplacian matrices. We
say that $L$ satisfies _the Euclidean SAP_ if it satisfies Condition (ii) in
Proposition 2.3.

Combining Proposition 2.2 and Proposition 2.3, we have the following
characterization of super stability number.

######  Proposition 2.4.

For a connected multigraph $G$,

$\lambda(G)=\max\left\\{\dim\ker L-1:\begin{array}[]{l}L\in{\cal L}^{*}(G)\\\
L\succeq 0\\\ \text{$L$ satisfies the Euclidean SAP}\end{array}\right\\}.$ (2)

###  2.4 Realizable dimension

Belk and Connelly [4] introduced the concept of realizable dimension of graphs
as the foldability of any bar-joint realizations. A natural tensegrity
extension can be defined as follows. A multigraph $G$ is $d$-realizable if any
tensegrity realization of $G$ has a $d^{\prime}$-dimensional deformation for
some $d^{\prime}\leq d$. The realizable dimension ${\rm rd}(G)$ of $G$ is
defined by

${\rm rd}(G)=\min\\{d\in\mathbb{Z}_{\geq 0}:\text{$G$ is $d$-realizable}\\}.$

As explained above, a bar-joint framework of a simple graph $G$ can be
captured as a tensegrity realization of $G^{=}$. Thus, the $d$-realizability
of $G^{=}$ coincides with the bar-joint case of $d$-realizability due to Belk
and Connelly [4].

Observe that, for a tensegrity realization $(G,\sigma,p)$ of $G$,
$(G,\sigma,p)$ has a $d^{\prime}$-dimensional deformation with $d^{\prime}\leq
d$ if and only if $\text{P}_{(G,\sigma,p)}$ has a feasible solution $X$ with
$\operatorname{rank}X\leq d$. Hence, if $G$ has a $d$-dimensional universally
rigid tensegrity realization $(G,\sigma,p)$, then $\text{P}_{(G,\sigma,p)}$
has a unique solution of rank $d$, implying ${\rm rd}(G)\geq d$. Since any
super stable tensegrity is universally rigid by Theorem 2.1, we have the
following relation between $\operatorname{rd}$ and $\lambda$.

######  Proposition 2.5.

For any multigraph $G$, $\lambda(G)\leq\operatorname{rd}(G)$.

It is not difficult to check the minor monotonicity of realizable dimension.
(Note that a tensegrity may have an edge of length zero.)

######  Proposition 2.6.

Let $G$ and $H$ be multigraphs. If $H$ is a minor of $G$,
$\operatorname{rd}(H)\leq\operatorname{rd}(G)$.

##  3 Constructing Super Stable Tensegrities

In this section we shall show super stable tensegrities can be constructed
inductively by basic graph operations. The results in particular implies the
minor monotonicity of super stability number, but our goal is to prove an even
stronger statement for constructing injective realizations. We say that a
tensegrity $(G,\sigma,p)$ is injective if $p$ is injective. In the context of
rigidity, we are often asked to consider only injective realizations.

This section goes as follows. In Subsection 3.1 we first show that the
(injective) realizability as a super stable tensegrity is preserved by edge
addition. This is a non-trivial fact because a super stable realization
requires a strictly proper stress according to our definition. In Subsection
3.2 we study the corresponding question for vertex splitting. This is the
technically most difficult part in this paper. The strategy follows an
argument in [18], which exploited a technique from [12] for the minor
monotonicity of the Colin de Verdière number. In Subsection 3.3, we give a
list of corollaries including the minor monotonicity of $\lambda$.

Before moving to the main content, we collect some auxiliary propositions. The
first proposition is useful when checking the conic condition.

######  Proposition 3.1.

Suppose there is a $d$-dimensional framework $(G,p_{0})$ satisfying the conic
condition. Then

$\\{q\in(\mathbb{R}^{d})^{n}:\text{$(G,q)$ satisfies the conic condition}\\}$

is an open dense subset of $(\mathbb{R}^{d})^{n}$, where
$(\mathbb{R}^{d})^{n}$ denotes the set of all maps from $V(G)$ to
$\mathbb{R}^{d}$

###### Proof.

Recall that $(G,p)$ does not satisfy the conic condition if and only if there
is a nonzero $S\in\mathbb{S}^{d}$ such that $(p(i)-p(j))^{\top}S(p(i)-p(j)=0$
for any edge $ij\in E(G)$. The latter condition asks whether there is a
nonzero solution in a linear system in the entries of $S$. This holds if and
only if every $d\times d$ minor in the matrix representing the linear system
is vanishing. Since each $d\times d$ minor is written as a polynomial in the
entries of $p$ and at least one $d\times d$ minor is not vanishing (as the
conic condition holds for $(G,p)$), the statement follows. ∎

For a square matrix $A=\begin{bmatrix}r&s^{\top}\\\ s&T\end{bmatrix}$ with
$r\neq 0$, the Schur complment at the top left corner is defined by
$T-r^{-1}ss^{\top}$. We denote it by $A/1$. The proof of the following
proposition is easy and can be found in [18].

######  Proposition 3.2.

Let $A=\begin{bmatrix}r&s^{\top}\\\ s&T\end{bmatrix}$ be an $n\times n$
symmetric matrix with corank $d$ and $r\neq 0$. Let
$p^{\prime}:\\{2,\dots,n\\}\rightarrow\mathbb{R}^{d}$ be a kernel
representation of $A/1$, and define an extension
$p:\\{1,\dots,n\\}\rightarrow\mathbb{R}^{d}$ of $p^{\prime}$ by

$p(1)=-\frac{1}{r}s^{\top}P^{\prime\top}$

where $P^{\prime}$ denotes the kernel matrix of $A/1$ corresponding to
$p^{\prime}$. Then $p$ is a kernel representation of $A$. Moreover, if
$(\Omega/1){\bf 1}_{n-1}=0$ and $r+s^{\top}{\bf 1}_{n-1}=0$, then $\Omega{\bf
1}_{n}=0$.

We also need the following simple corollary of the inverse function theorem.
See, e.g., [18] for a proof.

######  Proposition 3.3.

Let $X,Y,Z$ be smooth manifolds in $\mathbb{R}^{m}$. Suppose that $X$ is an
embedded submanifold of $Y$ of codimension at least one, and $X$ and $Z$
intersect transversally at $p\in X\cap Z$. Then there is a smooth path
$\gamma:[0,1]\rightarrow Y\cap Z$ such that $\gamma(0)=p$ and $\gamma(t)\in
Y\setminus X$ for $t\in(0,1]$.

###  3.1 Edge removal

######  Lemma 3.4.

Let $G$ be a connected multigraph and $e$ be an edge of $G$. Suppose $G-e$ has
a $d$-dimensional super stable tensegrity realization. Then $G$ has a
$d$-dimensional super stable tensegrity realization.

Moreover, if the realization of $G-e$ is injective, then the realization of
$G$ can be injective.

###### Proof.

Let $e=uv$, $(G-e,\sigma^{\prime},p^{\prime})$ be a $d$-dimensional super
stable tensegrity realization of $G-e$, and $L_{G-e}$ be a weighted Laplacian
matrix of $G-e$ that certificates the super stability of
$(G-e,\sigma^{\prime},p^{\prime})$. We may suppose that $p^{\prime}$ is a
reduced kernel representation of $L_{G-e}$.

If $G-e$ contains an edge $e^{\prime}$ parallel to $e$, then $L_{G-e}$ also
serves as a certificate of super stability of $(G,\sigma,p^{\prime})$ by
extending $\sigma^{\prime}$ to $\sigma$ by
$\sigma(e^{\prime})=-\sigma^{\prime}(e)$. Hence we we assume that $G-e$ has no
edge parallel to $e$.

By Proposition 2.3, ${\cal L}(G-e)$ and ${\cal L}^{n}_{n-(d+1)}$ intersect
transversally at $L_{G-e}$ in ${\cal L}^{n}$. Note that ${\cal L}(G)$ can be
written by

${\cal L}(G):=\left\\{L+\varepsilon(e_{u}-e_{v})(e_{u}-e_{v})^{\top}:L\in{\cal
L}(G-e),\varepsilon\in\mathbb{R}\right\\}.$

Since $G-e$ has no edge parallel to $e$, ${\cal L}(G-e)$ is a linear subspace
of ${\cal L}(G)$ of codimension one. Hence, by Proposition 3.3, there is a
positive number $\overline{\varepsilon}$ and a smooth function
$\gamma:[-\overline{\varepsilon},\overline{\varepsilon}]\rightarrow\mathcal{L}^{n}$
such that $\gamma(0)=L_{G-e}$ and $\gamma(\varepsilon)\in({\cal
L}(G)\setminus{\cal L}(G-e))\cap{\cal L}_{n-(d+1)}^{n}$ for
$\varepsilon\in[-\overline{\varepsilon},\overline{\varepsilon}]\setminus\\{0\\}$.
Let $L_{\varepsilon}:=\gamma(\varepsilon)$. Then by $L_{\varepsilon}\in{\cal
L}(G)\setminus{\cal L}(G-e)$ we have $L_{\varepsilon}\in{\cal
L}^{*}(G)\cap{\cal L}_{n-(d+1)}^{n}$ and $L_{\varepsilon}\succeq 0$ if
$\varepsilon$ is a sufficiently small nonzero number.

Since the entries of $L_{\varepsilon}$ continuously change with respect to
$\varepsilon$, we can take a smooth function
$[-\overline{\varepsilon},\overline{\varepsilon}]\ni\varepsilon\mapsto
p_{\varepsilon}\in(\mathbb{R}^{d})^{n}$ such that $p_{0}=p^{\prime}$ and
$p_{\varepsilon}$ is a reduced kernel representation with respect to
$L_{\varepsilon}$. Then $L_{\varepsilon}$ certificates that
$(G,\sigma,p_{\varepsilon})$ satisfies the stress condition for super
stability (after extending $\sigma^{\prime}$ to $\sigma$ such that
$\sigma(e)={\rm sign}\ L_{\varepsilon}[u,v]$). Moreover, if $\varepsilon$ is
small, $(G,\sigma,p_{\varepsilon})$ also satisfy the conic condition by
Proposition 3.1. Thus, $(G,\sigma,p_{\varepsilon})$ is super stable.

Since the coordinates of $p_{\varepsilon}$ continuously change in
$\varepsilon$, $p_{\varepsilon}$ is injective if $p^{\prime}=p_{0}$ is
injective and $\varepsilon$ is small. ∎

For a multigraph $G$, an (open) ear is a path $P$ of length at least one such
that the endvertices of $P$ are distinct vertices of $G$ and the internal
vertices are disjoint from $G$. Note that a single-edge path between two
vertices of $G$ is also an ear. Ears appear when constructing 2-connected
multigraphs: it is an elementary fact from graph theory that any 2-connected
multigraph can be constructed from any 2-connected subgraph by attaching ears
sequentially keeping 2-connectivity.

The following lemma gives a slightly stronger statement than Lemma 3.4.

######  Lemma 3.5.

Let $G,H$ be connected multigraphs and suppose that $G$ is obtained from $H$
by attaching an ear $P$. If $H$ has a $d$-dimensional super stable (injective)
tensegrity realization, then so does $G$.

###### Proof.

If $P$ has length one, then attaching $P$ is equivalent to adding an edge, so
Lemma 3.4 can be applied. We impose an extra property in the resulting
tensegrity realization such that the new edge is realized as a cable. This is
possible because in the proof of Lemma 3.4 the sign of the new edge in
$(G,\sigma,p_{\varepsilon})$ is controllable and can be forced to be positive
(by taking a small positive $\varepsilon$).

Suppose the length of $P$ is more than one. Then attaching the ear $P$ is
equivalent to adding a new edge and subdividing the new edge by new vertices.
It is well-known that, in a super stable tensegrity, the subdivision of a
cable by inserting a new mid-point preserves super stability. Hence, a super
stable (injective) realization of $G$ can be obtained from that of $H$ by
first adding an edge as a cable and subdividing the new cable. ∎

###  3.2 Edge contraction

The next goal is to derive the counterpart of Lemma 3.4 for edge contraction.
However, for edge contraction, the injectivity may not be guaranteed in
general. To see this, consider for example a multigraph $C_{4}^{=}-e$ obtained
from $C_{4}^{=}$ by removing an edge $e$, and let $e^{\prime}$ be the edge
parallel to $e$ in $C_{4}^{=}$. It is not difficult to check that any
injective 2-dimensional realization of $C_{4}^{=}-e$ is not super stable
whereas $(C_{4}^{=}-e)/e^{\prime}$ admits an injective 2-dimensional super
stable realization since $(C_{4}^{=}-e)/e^{\prime}$ is isomorphic to
$K_{3}^{=}$.

It seems difficult to characterize the property of having an injective super
stable realization completely, so our focus here is to give a sufficient
condition. A key property is the following new concept of stress
splittability, which is inspired by stress non-degeneracy in [18].

Let $(G,\sigma,p)$ be a tensegrity. An equilibrium stress
$\omega:E(G)\rightarrow\mathbb{R}$ is said to be splittable at a vertex $v\in
V(G)$ if there is a proper nonempty subset $F\subsetneq E_{G}(v)$ such that

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

$\omega$ is said to be non-splittable if it is not splittable at any $v\in
V(G)$. We first remark the following easy observation.

######  Lemma 3.6.

Suppose a $d$-dimensional super stable tensegrity $(G,\sigma,p)$ has a non-
splittable equilibrium stress. Then it has an equilibrium stress $\omega$ such
that $\omega$ is non-splittable and $L_{G,\omega}$ is positive semidefinite
with nullity $d+1$.

###### Proof.

Since the tensegrity is super stable, by the stress condition for super
stability, it has an equilibrium stress $\omega_{1}$ such that
$L_{G,\omega_{1}}$ is positive semidefinite with nullity $d+1$. Let
$\omega_{2}$ be a non-splittable equilibrium stress, and let
$\omega=\omega_{1}+\varepsilon\omega_{2}$. If $\varepsilon$ is a sufficiently
small generic number, then $\omega$ has the desired property by
$L_{G,\omega}=L_{G,\omega_{1}}+\varepsilon L_{G,\omega_{2}}$ and $\ker
L_{G,\omega_{1}}\subseteq\ker L_{G,\omega_{2}}$. ∎

We are now ready to prove our main technical lemma. A vertex of a connected
multigraph is said to be pendant if it is adjacent to exactly one vertex.

######  Lemma 3.7.

Let $G$ be a connected multigraph and $e$ be an edge of $G$. Suppose $G/e$ has
a $d$-dimensional super stable tensegrity realization. Then $G$ has a
$d$-dimensional super stable tensegrity realization.

Moreover, if no endvertex of $e$ is a pendant and the realization of $G/e$ is
injective and has a non-splittable equilibrium stress, then the realization of
$G$ can be injective and has a non-splittable equilibrium stress.

###### Proof.

We first consider the case when there is a parallel edge $e^{\prime}$ to $e$
in $G$ and show that this case can be reduced to the case when there is no
parallel edge to $e$. Suppose $e$ and $e^{\prime}$ are parallel. Then
$(G-e^{\prime})/e=G/e$. So $G-e^{\prime}$ also satisfies the condition of the
lemma, and by induction on the number of edges the conclusion of the lemma
holds for $G-e^{\prime}$. Then the statement follows for $G$ since a desired
stress for $G$ can be constructed from a stress $\omega$ of $G-e^{\prime}$ by
distributing $\omega(e)$ generically to $e$ and $e^{\prime}$.

Thus we may assume that there is no parallel edge to $e$ in $G$. Let
$n=|V(G)|$. Also, let $e=v_{0}v_{1}$, $X=N_{G}(v_{0})\setminus\\{v_{1}\\}$,
$Y=V\setminus(X\cup\\{v_{0},v_{1}\\})$, and $E_{0}=E_{G}(v_{0})$ for
simplicity of description. We simply denote by $v_{1}$ the vertex in $G/e$
after the contraction of $e=v_{0}v_{1}$. Each edge $f\in
E_{0}\setminus\\{e\\}$ in $G$ remains in $G/e$ after the contraction and we
keep using the same notation $f$ to denote the edge after the contraction. By
this convention, we have $E(G/e)=E(G)\setminus\\{e\\}$.

The proof strategy goes as follows. By the lemma assumption, we know that
there is a Laplacian matrix $L_{G/e}$ of $G/e$ that certificates the super
stability of a realization of $G/e$, and our goal is to construct a
certificate for $G$ from $L_{G/e}$. Let $G^{\prime}$ be the graph obtained
from $G/e$ by adding all edges between vertices of $X$. A Laplacian matrix of
$G^{\prime}$ can be constructed from that of $G$ by taking the Schur
complement at the diagonal entry indexed by $v_{0}$. Since the Schur
complement is known to preserve the positive semideiniteness and the nullity
as long as the diagonal has a positive entry, our task can be reduced to
constructing an appropriate Laplacian matrx of $G^{\prime}$. Namely, since
$G/e$ is a subgraph of $G^{\prime}$, the idea is to construct a Laplacian
matrix $L_{G^{\prime}}$ of $G^{\prime}$ by a perturbation of $L_{G/e}$ and
then recover a Laplacian of $G$ from $L_{G^{\prime}}$ by reversing the process
of taking the Schur complement. Not all Laplacian matrices of $G^{\prime}$ are
the Schur complement of Laplacian matrices of $G$, so we need to understand
which Laplacian matrix of $G^{\prime}$ can be the Schur complement of a
Laplacian of $G$.

To see this, consider any edge weight $w:E(G)\rightarrow\mathbb{R}$ and
$L_{G,\omega}\in{\cal L}(G)$ such that the diagonal entry indexed by $v_{0}$
is nonzero. For simplicity of description, for each subgraph $H$, we use
$L_{H,\omega}$ to denote $L_{H,\omega_{|H}}$, where $\omega_{|H}$ is the
restriction of $\omega$ to $E(H)$. We first split $L_{G,\omega}$ into two
matrices such that all the nonzero entries supported by edges incident to
$v_{0}$ are given in the second matrix as follows:

$\displaystyle L_{G,\omega}$
$\displaystyle=L_{G-E_{0},\omega}+L_{E_{0},\omega}.$ (3)

(Recall that $E_{0}$ denotes the set of edges incident to $v_{0}$ in $G$.) We
then introduce notation for entries of the second matrix $L_{E_{0},\omega}$ as
follows:

$\displaystyle L_{G,\omega}$
$\displaystyle=L_{G-E_{0},\omega}+\hbox{}\vbox{\kern 0.86108pt\hbox{$\kern
0.0pt\kern 2.5pt\kern-5.0pt\left[\kern
0.0pt\kern-2.5pt\kern-5.55557pt\vbox{\kern-0.86108pt\vbox{\vbox{
\halign{\kern\arraycolsep\hfil\@arstrut$\kbcolstyle#$\hfil\kern\arraycolsep&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep&&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep\cr
5.0pt\hfil\@arstrut$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
v_{0}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle v_{1}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle X$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
Y\\\v_{0}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle\varepsilon^{-1}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-\varepsilon^{-1}-s$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\omega_{X}^{\top}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\\\v_{1}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-\varepsilon^{-1}-s$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\varepsilon^{-1}+s$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0\\\X$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle\omega_{X}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle-{\rm
diag}(\omega_{X})$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0\\\Y$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern 5.0pt\crcr}}}}\right]$}},$ (5)

where $\varepsilon^{-1}$ denotes $L_{G,\omega}[v_{0},v_{0}]$,
$\omega_{X}\in\mathbb{R}^{X}$ is the vector obtained by aligning the edge
weight between $u$ and $v_{0}$ over $u\in X$, and $s=\sum_{u\in
X}\omega_{X}(u)$. (Here $s$ is defined to be $\sum_{u\in X}\omega_{X}(u)$
since the sum of the entries of the first column (or the first row) in the
second matrix must be zero.)

If we take the Shur complement of (5) at the left-top corner, then the
resulting matrix $L_{G,\omega}/v_{0}$ becomes

$L_{G,\omega}/v_{0}=L_{G-v_{0},\omega}+\hbox{}\vbox{\kern
0.86108pt\hbox{$\kern 0.0pt\kern 2.5pt\kern-5.0pt\left[\kern
0.0pt\kern-2.5pt\kern-5.55557pt\vbox{\kern-0.86108pt\vbox{\vbox{
\halign{\kern\arraycolsep\hfil\@arstrut$\kbcolstyle#$\hfil\kern\arraycolsep&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep&&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep\cr
5.0pt\hfil\@arstrut$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
v_{1}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle X$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle Y\\\v_{1}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-s-\varepsilon s^{2}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\omega_{X}^{\top}+\varepsilon
s\omega_{X}^{\top}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0\\\X$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\omega_{X}+\varepsilon s\omega_{X}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-{\rm
diag}(\omega_{X})-\varepsilon\omega_{X}\omega_{X}^{\top}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\\\Y$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern 5.0pt\crcr}}}}\right]$}}$ (6)

where $L_{G-v_{0},\omega}\in{\cal L}(G-v_{0})$ is obtained from
$L_{G-E_{0},\omega}$ by removing the top zero row and the left zero column.
This can be further written as

$\displaystyle L_{G,\omega}/v_{0}$
$\displaystyle=L_{G-v_{0},\omega}+\hbox{}\vbox{\kern 0.86108pt\hbox{$\kern
0.0pt\kern 2.5pt\kern-5.0pt\left[\kern
0.0pt\kern-2.5pt\kern-5.55557pt\vbox{\kern-0.86108pt\vbox{\vbox{
\halign{\kern\arraycolsep\hfil\@arstrut$\kbcolstyle#$\hfil\kern\arraycolsep&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep&&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep\cr
5.0pt\hfil\@arstrut$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
v_{1}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle X$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle Y\\\v_{1}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-s$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\omega_{X}^{\top}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\\\X$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\omega_{X}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-{\rm diag}(\omega_{X})$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\\\Y$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt\crcr}}}}\right]$}}+\varepsilon\left(\hbox{}\vbox{\kern
0.86108pt\hbox{$\kern 0.0pt\kern 2.5pt\kern-5.0pt\left[\kern
0.0pt\kern-2.5pt\kern-5.55557pt\vbox{\kern-0.86108pt\vbox{\vbox{
\halign{\kern\arraycolsep\hfil\@arstrut$\kbcolstyle#$\hfil\kern\arraycolsep&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep&&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep\cr
5.0pt\hfil\@arstrut$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
v_{1}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle X$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle Y\\\v_{1}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-s^{2}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
s\omega_{X}^{\top}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0\\\X$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle s\omega_{X}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-\omega_{X}\omega_{X}^{\top}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\\\Y$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern 5.0pt\crcr}}}}\right]$}}\right)\\\$
$\displaystyle=L_{G/e,\omega}+\varepsilon\left(\hbox{}\vbox{\kern
0.86108pt\hbox{$\kern 0.0pt\kern 2.5pt\kern-5.0pt\left[\kern
0.0pt\kern-2.5pt\kern-5.55557pt\vbox{\kern-0.86108pt\vbox{\vbox{
\halign{\kern\arraycolsep\hfil\@arstrut$\kbcolstyle#$\hfil\kern\arraycolsep&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep&&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep\cr
5.0pt\hfil\@arstrut$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
v_{1}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle X$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle Y\\\v_{1}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-s^{2}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
s\omega_{X}^{\top}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0\\\X$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle s\omega_{X}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-\omega_{X}\omega_{X}^{\top}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\\\Y$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern 5.0pt\crcr}}}}\right]$}}\right),$
(10)

where $L_{G/e,\omega}$ is the Laplacian of $G/e$ weighted by
$\omega_{|G-v_{0}v_{1}}$. (Recall our convention that
$E(G/e)=E(G)\setminus\\{v_{0}v_{1}\\}$). Note that $L_{G,\omega}/v_{0}\in{\cal
L}(G^{\prime})$ and (10) is exactly the form we are looking at.

With this relation in mind, we consider the following set in
$\mathcal{L}^{n}\times\mathbb{R}$.

${\cal M}:=\left\\{\left(L_{G/e,\omega}+\varepsilon\left(\hbox{}\vbox{\kern
0.86108pt\hbox{$\kern 0.0pt\kern 2.5pt\kern-5.0pt\left[\kern
0.0pt\kern-2.5pt\kern-5.55557pt\vbox{\kern-0.86108pt\vbox{\vbox{
\halign{\kern\arraycolsep\hfil\@arstrut$\kbcolstyle#$\hfil\kern\arraycolsep&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep&&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep\cr
5.0pt\hfil\@arstrut$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
v_{1}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle X$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle Y\\\v_{1}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-s^{2}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
s\omega_{X}^{\top}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0\\\X$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle s\omega_{X}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-\omega_{X}\omega_{X}^{\top}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\\\Y$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt\crcr}}}}\right]$}}\right),\varepsilon\right):\begin{array}[]{l}\omega:E(G)\setminus\\{v_{0}v_{1}\\}\rightarrow\mathbb{R}\\\
\varepsilon\in\mathbb{R}\end{array}\right\\}$

and let ${\cal M}_{0}$ be the subset of ${\cal M}$ consisting of elements with
$\varepsilon=0$. Observe that the first argument in any element in ${\cal M}$
is of the form (10).

Let $(G/e,\sigma,p)$ be a $d$-dimensional super stable tensegrity realization,
and let $L_{G/e,\omega^{*}}$ be a weighted Laplacian matrix of $G/e$ that
certificates the super stability of $(G/e,\sigma,p)$. We may suppose that $p$
is a reduced kernel representation of $L_{G/e,\omega^{*}}$. Then,
$(L_{G/e,\omega^{*}},0)\in{\cal M}_{0}$. Observe also that, for any
$(L,0)\in{\cal M}_{0}$, $T_{(L,0)}{\cal M}_{0}=T_{L}{\cal
L}(G/e)\times\\{0\\}$ holds for the tangent space. Hence, by Proposition 2.3,
the Euclidean SAP of $L_{G/e,\omega^{*}}$ implies that ${\cal M}_{0}$ and
${\cal L}_{(n-1)-(d+1)}^{n-1}\times\mathbb{R}$ intersect transversally at
$(L_{G/e,\omega^{*}},0)$. By Proposition 3.3, there is a positive number
$\overline{\varepsilon}$ and a smooth function
$\gamma:[-\overline{\varepsilon},\overline{\varepsilon}]\rightarrow\mathcal{L}^{n-1}\times\mathbb{R}$
such that $\gamma(0)=(L_{G/e,\omega^{*}},0)$ and $\gamma(\varepsilon)\in{\cal
M}\cap({\cal L}_{(n-1)-(d+1)}^{n-1}\times\mathbb{R})$ for
$\varepsilon\in[-\overline{\varepsilon},\overline{\varepsilon}]$. Denote
$\gamma(\varepsilon)=(L_{\varepsilon},\varepsilon)$. Since the entries of
$L_{\varepsilon}$ continuously change with respect to $\varepsilon$, we have
$L_{\varepsilon}\in{\cal L}_{(n-1)-(d+1)}^{n-1}$ and $L_{\varepsilon}\succeq
0$ if $\varepsilon$ is sufficiently small.

By the definition of $\cal M$, there is an edge weight
$\omega_{\varepsilon}:E(G)\setminus\\{v_{0}v_{1}\\}\rightarrow\mathbb{R}$ such
that $L_{\varepsilon}$ is given in the form of (10) with respect to
$\omega_{\varepsilon}$ and $\varepsilon$. By the continuity of
$L_{\varepsilon}$ with respect to $\varepsilon$ and
$L_{0}=L_{G/e,\omega^{*}}$, we can take $\omega_{\varepsilon}$ continuously
with respect to $\varepsilon$ such that $\omega_{0}=\omega^{*}$.

For $\varepsilon>0$, we extend $\omega_{\varepsilon}$, which is defined over
$E(G)\setminus\\{v_{0}v_{1}\\}$, to an edge weight
$\omega_{\varepsilon}^{\prime}$ of $E(G)$ by setting

$\omega_{\varepsilon}^{\prime}(v_{0}v_{1})=\varepsilon^{-1}+s_{\varepsilon},$
(11)

where $s_{\varepsilon}=\sum_{u\in X}\omega_{\varepsilon,X}(u)$. Since
$L_{\varepsilon}$ is of the form (10) with respect to $\omega_{\varepsilon}$,
$L_{G,\omega_{\varepsilon}^{\prime}}$ is the Laplacian matrix of $G$ obtained
from $L_{\varepsilon}$ by reversing the above process, i.e.,
$L_{G,\omega_{\varepsilon}^{\prime}}/v_{0}=L_{\varepsilon}$. (The definition
(11) is coming from the $v_{0}v_{1}$-th entry of the matrix in (5).)

By $\varepsilon>0$ and $L_{\varepsilon}\succeq 0$, the Haynsworth inertia
additivity formula implies that $L_{G,\omega_{\varepsilon}^{\prime}}$ is
positive semidefinite and its nullity is equal to that of $L_{\varepsilon}$.
Therefore, $L_{G,\omega_{\varepsilon}^{\prime}}\in{\cal L}^{*}(G)\cap{\cal
L}_{n-(d+1)}^{n}$ and $L_{G,\omega_{\varepsilon}^{\prime}}\succeq 0$ if
$\varepsilon$ is a sufficiently small nonzero number.

We now construct a realization of $G$. Since the entries of $L_{\varepsilon}$
continuously change with respect to $\varepsilon$, we can take a smooth
function
$[-\overline{\varepsilon},\overline{\varepsilon}]\ni\varepsilon\mapsto
p_{\varepsilon}\in(\mathbb{R}^{d})^{n-1}$ such that $p_{0}=p$ and
$p_{\varepsilon}$ is a reduced kernel representation of $L_{\varepsilon}$. For
$\varepsilon>0$, we can apply Proposition 3.2 to $p_{\varepsilon}$ to get an
extension $p_{\varepsilon}^{\prime}$ of $p_{\varepsilon}$ such that
$p_{\varepsilon}^{\prime}$ is a reduced kernel representation of
$L_{G,\omega_{\varepsilon}^{\prime}}$. Specifically, by using the formula of
Proposition 3.2 and $s_{\varepsilon}=\sum_{u\in X}\omega_{\varepsilon,X}(u)$,
we have

$\displaystyle p_{\varepsilon}^{\prime}(v_{0})$
$\displaystyle=p_{\varepsilon}(v_{1})-\varepsilon\left(\sum_{f=v_{0}u\in
E_{0}}\omega_{\varepsilon}(f)(p_{\varepsilon}(u)-p_{\varepsilon}(v_{1}))\right).$
(12)

Since $p_{\varepsilon}^{\prime}$ is a reduced kernel representation of
$L_{G,\omega_{\varepsilon}^{\prime}}$, $L_{G,\omega_{\varepsilon}^{\prime}}$
certifies the stress condition for super stability of tensegrity
$(G,\sigma^{\prime},p_{\varepsilon}^{\prime})$ (by taking an appropriate sign
function $\sigma^{\prime}$).

We check the conic condition of
$(G,\sigma^{\prime},p_{\varepsilon}^{\prime})$. Since
$p_{\varepsilon}^{\prime}$ is an extension of $p_{\varepsilon}$ and
$p_{\varepsilon}^{\prime}(v_{0})$ is given by (12), $p_{0}^{\prime}$ is well-
defined by letting $\varepsilon\rightarrow 0$, and we have

$\displaystyle p_{0}^{\prime}(u)$ $\displaystyle=p_{0}(u)=p(u)\qquad(u\in
V(G)\setminus\\{v_{0}\\})$ $\displaystyle p_{0}^{\prime}(v_{0})$
$\displaystyle=p_{0}(v_{1})=p(v_{1}).$

Therefore, since $(G/e,p)$ satisfies the conic condition (as $(G/e,\sigma,p)$
is super stable), $(G,p_{0}^{\prime})$ satisfies the conic condition. By
continuity of $p_{\varepsilon}^{\prime}$ and Proposition 3.1,
$(G,p_{\varepsilon}^{\prime})$ also satisfies the conic condition if
$\varepsilon$ is sufficiently small.

In total, $(G,\sigma^{\prime},p_{\varepsilon}^{\prime})$ is a $d$-dimensional
super stable tensegrity realization of $G$.

Finally we check that $(G,\sigma^{\prime},p_{\varepsilon}^{\prime})$ is
injective and admits a non-splittable stress if so does $(G/e,\sigma,p)$. By
Lemma 3.6, we may suppose that the initial stress
$\omega^{*}:E(G/e)\rightarrow\mathbb{R}$ of $(G/e,\sigma,p)$ is non-
splittable. If $(G,\sigma^{\prime},p_{\varepsilon}^{\prime})$ is not injective
for any small $\varepsilon$, then
$p_{\varepsilon}^{\prime}(v_{0})=p_{\varepsilon}^{\prime}(v_{1})$ by the
injectivity of $(G/e,\sigma,p)$. By (12), we get
$\displaystyle\sum_{f=v_{0}u\in
E_{0}}\omega_{\varepsilon}(f)(p_{\varepsilon}(u)-p_{\varepsilon}(v_{1}))=0$.
By continuity, this in turn implies $\displaystyle\sum_{f=v_{0}u\in
E_{0}}\omega_{0}(f)(p_{0}(u)-p_{0}(v_{1}))=0$, and equivalently

$\sum_{f=v_{0}u\in E_{0}}\omega^{*}(f)(p(u)-p(v_{1}))=0$ (13)

by $\omega_{0}=\omega^{*}$ and $p_{0}=p$. However, since $e=v_{0}v_{1}$ is not
incident to a degree-one vertex, $E_{0}$ is a nonempty proper subset of
$E_{G/e}(v_{1})$, and (13) implies that $\omega^{*}$ is splittable at $v_{1}$
in $G/e$, a contradiction. Thus,
$(G,\sigma^{\prime},p_{\varepsilon}^{\prime})$ is injective.

Finally, we prove that the resulting stress $\omega_{\varepsilon}^{\prime}$ of
$(G,\sigma^{\prime},p_{\varepsilon}^{\prime})$ is non-splittable. Suppose for
a contradiction that $\omega_{\varepsilon}^{\prime}$ is splittable for any
small $\varepsilon$. The non-splittability of $\omega^{*}$ and
$\omega_{0}=\omega^{*}$ imply that $\omega_{\varepsilon}$ is non-splittable in
$G/e$ if $\varepsilon$ is sufficiently small. Since
$\omega_{\varepsilon}^{\prime}$ is an extension of $\omega_{\varepsilon}$,
$\omega_{\varepsilon}^{\prime}$ must be splittable at $v_{i}$ for some
$i\in\\{0,1\\}$. So

$\sum_{f=uv_{i}\in
F}\omega_{\varepsilon}^{\prime}(f)(p_{\varepsilon}^{\prime}(u)-p_{\varepsilon}^{\prime}(v_{i}))=0$
(14)

for some nonempty $F\subsetneq E_{G}(v_{i})$. Since
$\omega_{\varepsilon}^{\prime}$ is an equilibrium stress of
$(G,\sigma^{\prime},p_{\varepsilon}^{\prime})$, (14) still holds by replacing
$F$ with $E_{G}(v_{i})\setminus F$. Thus, we may always suppose that
$v_{0}v_{1}\notin F$. Then, by letting $\varepsilon\rightarrow 0$ in (14), we
obtain

$0=\sum_{f=uv_{i}\in
F}\omega_{0}^{\prime}(f)(p_{0}^{\prime}(u)-p_{0}^{\prime}(v_{i}))=\sum_{f=uv_{1}\in
F}\omega^{*}(f)(p(u)-p(v_{1})).$

Since $F\subsetneq E_{G/e}(v_{1})$, this implies that $\omega^{*}$ is
splittable at $v_{1}$ in $G/e$, a contradiction. This contradiction completes
the proof that $\omega_{\varepsilon}^{\prime}$ is non-splittable. ∎

###  3.3 Minor Monotonicity

The super stability enjoys a minor monotone property in the following sense.

######  Theorem 3.8.

Let $G$ be a connected multigraph and $H$ be a minor of $G$. If $H$ admits a
$d$-dimensional super stable tensegrity realization, then $G$ admits a
$d$-dimensional super stable tensegrity realization.

###### Proof.

We may suppose that $H$ is connected. Since $G$ is connected and $H$ is a
minor of $G$, $H$ can be obtained from $G$ by contracting edges and removing
non-bridge edges. Hence the statement follows from Lemmas 3.4 and 3.7. ∎

######  Corollary 3.9.

Let $G$ and $H$ be multigraphs. If $H$ is a minor of $G$,
$\lambda(H)\leq\lambda(G)$.

As remarked above, the analogous statement for injective realizations dose not
hold, and the following is what we can currently achieve by Lemmas 3.5 and
3.7.

######  Theorem 3.10.

Let $G$ be a 2-connected multigraph and $H$ be a 2-connected minor of $G$. If
$H$ admits a $d$-dimensional injective super stable tensegrity realization
which has a non-splittable equilibrium stress, then $G$ admits a
$d$-dimensional injective super stable tensegrity realization.

###### Proof.

Since $G$ and $H$ are both 2-connected, $H$ can be obtained from $G$ by first
deleting ears and then contracting edges. Thus the statement follows from
Lemmas 3.5 and 3.7. ∎

Theorem 1.2 given in the introduction is an example of Theorem 3.10.

###### Proof of Theorem 1.2.

An equilibrium stress of the tensegrity realization of $K_{d+2}$ in Example 3
is non-splittable. So the statement follows from Theorem 3.10 by setting
$H=K_{d+2}$. ∎

##  4 Characterizing Multigraphs of Super Stable Tensegrities

In this section we shall give a characterization of multigraphs which can be
realized as 3-dimensional super stable tensegrities. This can be done by
establishing an exact relation between $\lambda$ and the Colin de Verdière
number $\nu$.

This section is organized as follows. In Subsection 4.1 we give a formal
definition of the Colin de Verdière number $\nu$. In Subsection 4.2 we
introduce coning operation, which is the basic tool for bridging $\lambda$ and
$\nu$. In Subsection 4.3 we explain the slicing and sliding theorem by
Connelly, Gortler and Theran, which is the key ingredient for the exact
relation between $\lambda$ and $\nu$. In Subsection 4.4, we put all together
and derive the combinatorial characterization as a corollary.

###  4.1 Colin de Verdière number $\nu$

Roughly speaking, the Colin de Verdière number $\nu$ can be defined by
replacing Laplacian matrices with adjacency matrices in (2). For a formal
definition, we need some notation. For a multigraph $G$, let

$\displaystyle{\cal A}^{*}(G)=\left\\{A\in{\cal
S}^{n}\mid\begin{array}[]{ll}A[i,j]=0&\text{if $G$ has no edge between $i$ and
$j$ with $i\neq j$}\\\ A[i,j]\neq 0&\text{if $G$ has a single edge between $i$
and $j$}\\\ A[i,j]\in\mathbb{R}&\text{if $G$ has parallel edges between $i$
and $j$ or $i=j$}\end{array}\right\\},$

where ${\cal S}^{n}$ denotes the set of $n\times n$ symmetric matrices. The
set of $n\times n$ symmetric matrices of rank $k$ is denoted by ${\cal
S}^{n}_{k}$.

We say that a matrix $A\in{\cal A}^{*}(G)$ satisfies the strong Arnold
property (SAP) if there is no nonzero $X\in{\cal S}^{n}$ satisfying $XA=0$ and
$\langle X,\bm{e}_{i}\bm{e}_{j}^{\top}\rangle=0$ for every $i,j$ with $i=j$ or
$ij\in E(G)$. Observe the similarity between the SAP and the Euclidean SAP
introduced in Proposition 2.3.

For a multigraph $G$, the Colin de Verdière number $\nu$ is defined by

$\nu(G)=\max\left\\{\dim\ker A:\begin{array}[]{l}A\in{\cal A}^{*}(G)\\\
A\succeq 0\\\ \text{$A$ satisfies the SAP}\end{array}\right\\}.$ (15)

This graph parameter was first introduced by Coin de Verdière [6] for
connected simple graphs and extended to multigraphs by van der Holst [12, 13].
Our idea of using multigraphs to investigate the combinatorics of tensegrities
was inspired by the work of van der Holst. The Colin de Verdière number $\nu$
is also refereed to as the algebraic width in [20].

###  4.2 Coning: bridging $\lambda$ and $\nu$

A key tool to bridge between $\lambda$ and $\nu$ is the so-called coning
operation. A connection between $\lambda$ and $\nu$ through coning was
implicit in the work by Laurent and Varvitsiotis [21], and we will make it
explicit in this subsection.

Let $G$ be a multigraph. The multigraph obtained from $G$ by adding a new
vertex $v_{0}$ and new parallel edges between $v_{0}$ and each vertex in $G$
is called the coning of $G$, and denoted it by $\nabla G$. The new vertex
$v_{0}$ is called the coned vertex.

The following lemma relates $\lambda$ with $\nu$. A slightly weaker statement
can be found in [21, Lemma 4.11].

######  Lemma 4.1.

For any multigraph $G$, $\lambda(\nabla G)=\nu(G)$.

###### Proof.

Let $d=\lambda(\nabla G)$, and let $L$ be a maximizer of (2) for $\nabla G$.
Then $\dim\ker L=d+1$ and $L\succeq 0$. Let $A$ be the principal submatrix of
$L$ indexed by $V(G)$. Then $A\succeq 0$ and $A\in{\cal A}(G)$. We show that
$A$ certifies $\nu(G)\geq d$. To see this, take a reduced kernel
representation $p$ of $L$. We may assume $p(v_{0})=0$, where $v_{0}$ is the
coned vertex of $\nabla G$. Then $p_{|V(G)}$ is a kernel representation of
$A$, and $\dim\ker A=d$ follows. Also, the SAP of $A$ follows by observing
that the SAP of $A$ is equivalent to the Euclidean SAP of $L$ due to the
existence of the parallel edges between $v_{0}$ and each vertex in $V(G)$.
Thus, $A$ satisfies the SAP, and $\nu(G)\geq d$ follows.

Conversely, let $d=\nu(G)$, and let $A$ be a maximizer of (15) for $\nabla G$.
Then $\dim\ker A=d$ and $A\succeq 0$. Let

$L=\begin{pmatrix}\mathbf{1}^{\top}A\mathbf{1}&-\mathbf{1}^{\top}A\\\
-A\mathbf{1}&A\end{pmatrix}.$

Then $L\in{\cal L}(\nabla G)$. Moreover, we have
$L=\begin{pmatrix}\mathbf{1}&-I_{n}\end{pmatrix}^{\top}A\begin{pmatrix}\mathbf{1}&-I_{n}\end{pmatrix}$,
implying that $L\succeq 0$ and $\dim\ker L=d+1$. The Euclidean SAP of $L$ can
be checked by the same reason as the first case. Thus, $\lambda(\nabla G)\geq
d$ follows. ∎

In view of Lemma 4.1, the next question is to understand a relation between
$\lambda(G)$ and $\lambda(\nabla G)$. The following relation is not difficult
to check.

######  Lemma 4.2.

For any multigraph $G$, $\lambda(\nabla G)\geq\lambda(G)+1$.

###### Proof.

This follows from the fact that the coning preserves the super stability [8,
Theorem 4.6]. Alternatively, one can directly check that, for a maximizer $L$
of (2) for $G$ with $d=\dim\ker L$, the matrix $\begin{pmatrix}0&0\\\
0&L\end{pmatrix}$ certifies $\lambda(\nabla G)\geq d+1$. ∎

###  4.3 Slicing and Sliding

By Lemmas 4.1 and 4.2, it follows that $\lambda(G)\leq\lambda(\nabla
G)-1=\nu(G)-1$. The key ingredient to prove the converse relation is an
observation by Connelly, Gortler, and Theran [8] that the super stability is
preserved by sliding and slicing operations of coned bar-joint frameworks.

Since we are interested in the existence of a proper stress in a tensegrity
realization, we shall explain the construction of Connelly, Gortler, and
Theran for completeness. Given a coned tensegrity $(\nabla G,\sigma,p)$ with
the coned vertex at the origin and suppose that

no point of $(\nabla G,\sigma,p)$ except the coned vertex lies at the origin.
(16)

A sliding of $(\nabla G,\sigma,p)$ is a framework $(\nabla
G,\sigma^{\prime},q)$ such that

  * •

$q(v)=s_{v}p(v)$ for some non-zero scaler $s_{v}$ for each $v\in V(G)$ (and
the coned vertex remains at the origin), and

  * •

$\sigma^{\prime}(uv)={\rm sign}(s_{u})\cdot{\rm sign}(s_{v})\cdot\sigma(uv)$
for every $e=uv\in E(G)$.

Suppose $(\nabla G,\sigma^{\prime},q)$ is obtained from $(\nabla G,\sigma,p)$
by $q(v)=s_{v}p(v)$ for $v\in V(G)$, and suppose $L$ is a Laplacian matrix of
$\nabla G$ which certifies the super stability of $(\nabla G,\sigma,p)$. Then,
consider

$L^{\prime}:=\begin{pmatrix}1&0&0&\dots&0\\\
1-\frac{1}{s_{1}}&\frac{1}{s_{1}}&0&\dots&0\\\ \vdots&0&\ddots&&\vdots\\\
\vdots&\vdots&&\ddots&0\\\
1-\frac{1}{s_{n}}&0&\vdots&0&\frac{1}{s_{n}}\end{pmatrix}^{\top}L\begin{pmatrix}1&0&0&\dots&0\\\
1-\frac{1}{s_{1}}&\frac{1}{s_{1}}&0&\dots&0\\\ \vdots&0&\ddots&&\vdots\\\
\vdots&\vdots&&\ddots&0\\\
1-\frac{1}{s_{n}}&0&\vdots&0&\frac{1}{s_{n}}\end{pmatrix},$ (17)

where we assumed that the first low and the first column of $L$ is indexed by
the coned vertex $v_{0}$. Then, by Sylvester’s law of inertia, $L^{\prime}$
certifies the stress condition of $(\nabla G,\sigma^{\prime},q)$. A nontrivial
observation due to Connelly, Gortler, and Theran [8] is that $(\nabla
G,\sigma^{\prime},q)$ also satisfies the conic condition, and thus $(\nabla
G,\sigma^{\prime},q)$ is super stable.

Let $(\nabla G,\sigma,p)$ be a $(d+1)$-dimensional coned tensegrity satisfying
(16) and $H$ be a hyperplane in $\mathbb{R}^{d+1}$ not through the origin.
Then by a sliding operation we can convert $(\nabla G,\sigma,p)$ to a
framework $(\nabla G,\sigma^{\prime},q)$ such that all the points except the
coned point lie on the hyperplane $H$. By identifying $H$ with
$\mathbb{R}^{d}$, the sub-tensegrity $(G,q)$ obtained by removing the coned
vertex can be regarded as a tensegrity in $\mathbb{R}^{d}$. The resulting
framework $(G,q)$ is called a slicing of $(\nabla G,\sigma,p)$. Since all the
non-coned point lie on $H$ in $(\nabla G,\sigma^{\prime},q)$, the stress
$\omega^{\prime}$ of $(\nabla G,\sigma^{\prime},q)$ obtained in the
construction (17) is zero along each coned edge. This implies that the
restriction of $\omega^{\prime}$ to $E(G)$ is also an equilibrium stress of
$(G,\sigma^{\prime},q)$. Connelly, Gortler, and Theran showed that the
resulting stress certifies the super stability of $(G,\sigma^{\prime},q)$.
Rephrasing the results explained so far in our terminology we have the
following.

######  Theorem 4.3 (Connelly, Gortler, and Theran (adapted)).

Let $G$ be a multigraph. Suppose $\nabla G$ has a $(d+1)$-dimensional super
stable tensegrity realization such that the coned vertex do not coincide with
other points in the realization. Then $G$ has a $d$-dimensional super stable
tensegrity realization.

The condition on the realization of $\nabla G$ in the statement of Theorem 4.3
is due to the assumption (16). We now discuss how to deal with this
assumption.

######  Lemma 4.4.

Let $(\nabla G,\sigma,p)$ be a $(d+1)$-dimensional super stable tensegrity
with the coned vertex $v_{0}$, and let $X=\\{v\in V(G):p(v)=p(v_{0})\\}$. Then
the tensegrity obtained from $(\nabla G,\sigma,p)$ by removing $X$ is super
stable.

###### Proof.

Let $v\in X$. We first show that $(\nabla G-v,\sigma,p)$ is super stable. Let
$L$ be a stress matrix of $(\nabla G,\sigma,p)$ that certifies the super
stability of $(\nabla G,\sigma,p)$. If the $v$-th diagonal entry of $\Omega$
is zero, then the $v$-th row and column are zero by the positive
semidefiniteness of $L$. Then the kernel of $L$ contains the characteristic
vector of $v$, implying that $p(v)$ is not at the origin, a contradiction.

Hence, the $v$-th diagonal entry of $L$ is positive. Suppose $L$ is written as
$\begin{pmatrix}a&b^{\top}\\\ b&L^{\prime}\end{pmatrix}$, where we assume the
first row/column is indexed by $v$. Then $a>0$. We consider the Schur
complement $L/v$ at the $v$-th diagonal, which is
$L/v=L^{\prime}-\frac{1}{a}bb^{\top}$. Since $L$ is positive semidefinite, so
is $L/v$ and $\operatorname{rank}L/v=\operatorname{rank}L-1$. It is also not
difficult to check that the all-one vector is in the kernel of $L/v$.

Let $v_{0}$ be the coned vertex, $\chi_{v_{0}}$ be the characteristic vector
of $v_{0}$, and

$L_{v}:=L/v+\frac{1}{a}(b+a\chi_{v_{0}})(b+a\chi_{v_{0}})^{\top}.$

Then $L_{v}\in{\cal L}^{*}(\nabla(G-v))$, and moreover it is the Laplacian of
$\nabla(G-v)$ weighted by an equilibrium stress of $(\nabla G-v,\sigma,p)$.
Since $L/v$ is positive semidefinite and $\dim\ker L/v=\dim\ker L$, $L_{v}$ is
positive semidefinite with $\dim\ker L_{v}=\dim\ker L/v=\dim\ker L$. The conic
condition clearly holds in $(\nabla G-v,p)$ since the set of edge directions
does not change. Thus, $(\nabla G-v,\sigma,p)$ is super stable.

We can apply the same argument in the resulting tensegrity until we remove all
the vertices in $X$. We finally obtain a Laplacian matrix that certifies the
super stability of $(\nabla G-X,\sigma,p)$. ∎

Combining Theorem 4.3 and Lemma 4.4, we obtain the following.

######  Lemma 4.5.

Let $G$ be a multigraph. Then $G$ has an induced subgraph $H$ such that
$\lambda(H)\geq\lambda(\nabla G)-1$.

###### Proof.

Let $d=\lambda(\nabla G)-1$, and let $(\nabla G,\sigma,p)$ be a
$(d+1)$-dimensional super stable tensegrity realization. Let $H$ be a subgraph
of $G$ obtained by removing all the vertices in $X=\\{v\in
V(G):p(v)=p(v_{0})\\}$. By Lemma 4.4, $(\nabla H,\sigma,p)$ is super stable.
By Theorem 4.3, $H$ has a $d$-dimensional super stable tensegrity realization,
implying $\lambda(H)\geq d$. ∎

###  4.4 Characterizing Multigraphs Having Super Stable Tensegrity
Realizations

The following theorem is our main observation in this section.

######  Theorem 4.6.

For a multigraph $G$, $\lambda(G)=\nu(G)-1$.

###### Proof.

By Lemmas 4.1 and 4.2, $\lambda(G)\leq\lambda(\nabla G)-1=\nu(G)-1$.
Conversely, by Lemma 4.5 and Theorem 3.8, $G$ has a subgraph $H$ such that
$\lambda(G)\geq\lambda(H)\geq\lambda(\nabla G)-1$. Thus, $\lambda(G)=\nu(G)-1$
follows. ∎

Theorem 1.1 stated in the introduction is an immediate corollary of Theorem
4.6.

###### Proof of Theorem 1.1.

In view of Theorem 3.8, a multigraph $G$ does not admit a 3-dimensional super
stable tensegrity realization if and only if $\lambda(G)\leq 2$. By Theorem
4.6, the latter condition is equivalent to $\nu(G)\leq 3$. van der Holst [13]
has shown that $\nu(G)\leq 3$ if and only if $G$ has no multigraph in the list
of Figure 2 as a minor. Thus, the statement follows. ∎

The 2-dimensional counterpart of Theorem 1.1 also follows by using the
characterization of multigraphs with $\nu(G)\leq 2$ due to van der Holst [13].
We will discuss a stronger statement in Section 6.

In rigidity applications, it is more important to restrict our attention to
injective realizations. Currently we have the following sufficient condition.

######  Theorem 4.7.

Let $G$ be a multigraph. Suppose $G$ contains $K_{5},Q_{8}$ or $K_{2,2,2}$ as
a minor. Then $G$ has a three-dimensional injective super stable tensegrity
realization.

###### Proof.

For $K_{5},Q_{8},K_{2,2,2}$, there are well known 3-dimensional super stable
tensegrity realizations. Those realizations are injective and admits non-
splittable equilibrium stresses. Hence, the statement follows from Theorem
3.10. ∎

Establishing a complete characterization remains open. We pose it as an open
problem.

######  Problem 1.

Characterize a class of multigraphs which can be realized as a 3-dimensional
injective super stable tensegrity.

A question of a similar kind is to characterize graphs which can be realized
as a $d$-dimensional super stable tensegrity in general position. This
question has been answered by Alfakih [3].

The corresponding questions for rigidity or global rigidity are also not
understood. The questions in generic tensegrity realizations are studied in
[16, 17, 14].

##  5 Relation Among Graph Parameters

$\nu(G)$ and ${\rm rd}(G^{=})$ have been studied extensively and relations to
other combinatorial graph parameters are known. The following statement
summarizes the current status.

######  Corollary 5.1.

For a multigraph $G$,

$\omega(G)-2\leq\kappa(G)-1\leq\nu(G)-1=\lambda(G)\leq{\rm rd}(G)\leq{\rm
rd}(G^{=})\leq{\rm tw}(G).$

###### Proof.

By definition, $\omega(G)-1\leq\kappa(G)$. van der Holst [13] has shown that
$\kappa(G)\leq\nu(G)$. By Theorem 4.6, $\lambda(G)=\nu(G)-1$.
$\lambda(G)\leq{\rm rd}(G)$ has been shown in Proposition 2.5. ${\rm
rd}(G)\leq{\rm rd}(G^{=})$ follows from the definition. ${\rm
rd}(G^{=})\leq{\rm tw}(G)$ has been observed by Belk and Connelly [4]. ∎

The inequality between ${\rm rd}(G^{=})$ and ${\rm tw}(G)$ can be strict as
observed by Belk and Connelly [4]. The inequality between ${\rm rd}(G)$ and
${\rm rd}(G^{=})$ can be strict since ${\rm rd}(K_{n})=n-2$ and ${\rm
rd}(K_{n}^{=})=n-1$. It is also known that $\nu(G)$ is lower bounded by some
monotone function of ${\rm tw}(G)$, see, e.g., [20]. This follows from the
fact that the triangular lattice $\Delta_{r}$ of width $r$ satisfies
$\nu(\Delta_{r})=r$ and any graph with large treewidth contains a triangular
lattice of large width as a minor. The triangular lattice also gives an
example of graphs $G$ with small connectivity and $\nu(G)-1=\lambda(G)={\rm
rd}(G)={\rm rd}(G^{=})={\rm tw}(G)$.

Currently there is no example that separates $\lambda(G)$ and ${\rm rd}(G)$,
and we conjecture that they are actually equal.

######  Conjecture 2.

For a multigraph $G$, $\nu(G)-1=\lambda(G)={\rm rd}(G)$.

The conjecture has an important implication in the context of rigidity since
the following property holds for multigraphs with $\lambda(G)={\rm rd}(G)$.

######  Lemma 5.2.

Suppose $d=\lambda(G)={\rm rd}(G)$ for a connected multigraph $G$. Then $d$ is
the maximum dimension in which $G$ admits a globally rigid/super
stable/universally rigid tensegrity realization.

###### Proof.

Denote by ${\rm gr}(G)$ and ${\rm ur}(G)$ the maximum dimensions in which $G$
admits a globally and universally tensegrity realization, respectively. Then,
by definition, ${\rm gr}(G)\geq{\rm ur}(G)\geq\lambda(G)$. We also have ${\rm
rd}(G)\geq{\rm gr}(G)$ since any realization of $G$ in higher dimension space
than ${\rm rd}(G)$ has a deformation into a lower dimension space. We thus
obtain $d={\rm rd}(G)\geq{\rm gr}(G)\geq{\rm ur}(G)\geq\lambda(G)=d$, and the
equality holds in each inequality. ∎

We may even pose a stronger conjecture as follows.

######  Conjecture 3.

For a connected multigraph $G$, ${\rm rd}(G)$ is the maximum dimension in
which $G$ admits a rigid/globally rigid/super stable/universally rigid
tensegrity realization.

We have already pointed out that ${\rm rd}(G)<{\rm rd}(G^{=})$ may hold since
${\rm rd}(K_{n})=n-2$ and ${\rm rd}(K_{n}^{=})=n-1$. Currently we have no
example for which the difference of those two parameters is more than one.
Hence we pose the following conjecture.

######  Conjecture 4.

For a multigraph $G$, ${\rm rd}(G^{=})-1\leq{\rm rd}(G)\leq{\rm rd}(G^{=})$.

Belk and Connelly gave a characterization of simple graphs $G$ with ${\rm
rd}(G^{=})\leq k$ for $k\in\\{1,2,3\\}$. In view of this, the following
problem is natural for understanding ${\rm rd}$.

######  Problem 5.

Characterize a class of multigraphs $G$ satisfying ${\rm rd}(G)={\rm
rd}(G^{=})$.

##  6 Characterizing Multigraphs with Bounded Realizable Dimension

In this section we confirm the conjectures in Section 5 for several special
classes of multigraphs by computing the value of ${\rm rd}(G)$ explicitly.

Since $\lambda(G)\leq{\rm rd}(G)$, giving a lower bound of ${\rm rd}(G)$ can
be accomplished by constructing super stable realizations of multigraphs. The
difficult direction is to give an upper bound of ${\rm rd}(G)$. Namely, we
need to show how to fold each tensegrity realization of $G$ down to a lower
dimensional space. (In this paper, folding is any procedure that finds a lower
dimensional deformation of a given tensegrity.) Our general folding strategy
is to use a special type of tree decompositions, which we shall explain in the
next subsection. We then show how to apply this strategy in several classes of
multigraphs.

We first review basic terminology on tree decompositions. A tree decomposition
of a graph $G=(V,E)$ is a pair $(T,{\cal W})$, where ${\cal W}$ is a
collection of vertex subsets of $V$ and $T$ is a tree on ${\cal W}$ satisfying
the follows three conditions: (i) each vertex $v\in V$ belongs to at least one
set in ${\cal W}$, (ii) for each edge $e\in E$, there is at least one set in
${\cal W}$ that contains both endvertices of $e$, and (iii) for each $v\in V$,
the subcollection ${\cal W}_{v}=\\{W\in{\cal W}:v\in W\\}$ induces a subtree
$T_{v}$ in $T$. A subset $W\in{\cal W}$ is call a bag, the width of the tree
decomposition is $\max\\{|W|-1:W\in{\cal W}\\}$, and the treewidth ${\rm
tw}(G)$ of $G$ is the minimum width over all tree decompositions of $G$. A
tree decomposition whose width attains the minimum width is called optimal.

There always exists an optimal tree decomposition $(T,{\cal W})$ such that
$W_{i}\not\subseteq W_{j}$ for any distinct bags $W_{i},W_{j}$. Hence,
throughout the paper, we include this property in the definition of tree
decompositions and assume that a tree decomposition always satisfies this
property.

###  6.1 Realizable Dimension and Tree Decomposition

To demonstrate our idea, let us first look at a multigraph $G$ with ${\rm
si}(G)=K_{n}$. If $G=K_{n}^{=}$, then a realization is a bar-joint framework
of the complete graph with $n$ vertices, which cannot be folded to a lower-
dimensional space, i.e., ${\rm rd}(G)=n-1$. (This can be also seen from ${\rm
rd}(G)\geq\lambda(G)=\lambda(K_{n}^{=})=n-1$.

We claim that ${\rm rd}(G)\leq n-2$ if $G\neq K_{n}^{=}$. To see this, take a
pair $u,v$ of vertices which are not linked by parallel edges. Then, for any
$(n-1)$-dimensional tensegrity realization $(G,\sigma,p)$ of $G$, one can fold
it to a $(n-2)$-dimensional space by rotating $p(u)$ about a
$(n-3)$-dimensional axis that contains the remaining $(n-2)$ points of
$(G,\sigma,p)$ in such a way that only the distance between $p(u)$ and $p(v)$
changes. (And the distance between $p(u)$ and $p(v)$ monotonically increases
or decreases depending on the direction of rotation.) This implies ${\rm
rd}(G)\leq n-2$. When ${\rm si}(G)=K_{n}$, the equality also follows by ${\rm
rd}(G)\geq\lambda(G)\geq\lambda(K_{n})=n-2$.

This elementary geometric observation turns out to be a nontrivial tool if we
combine it with tree decompositions. Let $G$ be a multigraph and $(T,{\cal
W})$ be a tree decomposition of $G$. We say that a bag $W$ is lacking if
either $|W|-1$ is strictly smaller than the width of $(T,{\cal W})$ or there
is a pair $u,v\in W$ such that $u$ and $v$ are not linked by parallel edges
and $u$ and $v$ are not contained in any other bag. We say that $(T,{\cal W})$
is lacking if every bag is lacking.

######  Lemma 6.1.

Let $G$ be a multigraph. Suppose that an optimal tree decomposition of $G$ is
lacking. Then ${\rm rd}(G)\leq{\rm tw}(G)-1$.

###### Proof.

Let $d={\rm tw}(G)-1$, and let $(G,\sigma,p)$ be a tensegrity realization of
$G$ in dimension greater than $d$. Our goal is to fold the tensegrity into a
$d$-dimensional space.

Let $(T,{\cal W})$ be an optimal lacking tree decomposition of $G$. We say
that a bag $W$ is flat if the affine span of $p(W)$ is $d$-dimensional. We
first show how to fold $(G,\sigma,p)$ so that each bag becomes flat. Suppose
$W^{*}\in{\cal W}$ is a bag which is not flat. Since $(T,{\cal W})$ is
lacking, there is a pair $u,v\in W^{*}$ such that $u$ and $v$ are not linked
by parallel edges and $u$ and $v$ are not contained in any other bag. Consider
removing the node $W^{*}$ from $T$, and let $T_{1},\dots,T_{k}$ be the
connected components in the resulting forest. Let $X_{i}$ be the set of
vertices of $G$ which are contained in a bag in $T_{i}$, i.e.,
$X_{i}=\bigcup_{W\in T_{i}}W$, for each $i=1,\dots,k$. Then, since $W^{*}$ is
the only bag that contains $u$ and $v$, the third property of the tree
decomposition implies

$\\{u,v\\}\not\subset X_{i}$ (18)

for each $i=1.\dots,k$.

Let $A=(W^{*}-u)\cup\bigcup_{X_{i}:v\in X_{i}}X_{i}$ and
$B=(W^{*}-v)\cup\bigcup_{X_{i}:v\notin X_{i}}X_{i}$. By (18) and the third
property of tree decompositions, we have that $u\notin A$, $A\cap
B=W^{*}-u-v$, and there is no edge between $A\setminus W^{*}$ and $B\setminus
W^{*}$. Let $G_{A}$ and $G_{B}$ be the subgraphs of $G$ induced by $A$ and
$B$, respectively. Then, $|V(G_{A})\cap V(G_{B})|=|W^{*}-u-v|=d$ and there is
at most one edge between $V(G_{A})\setminus V(G_{B})$ and $V(G_{A})\setminus
V(G_{B})$, which is a single edge between $u$ and $v$ if exists. Hence, one
can rotate the sub-tensegrity of $G_{A}$ about a $(d-1)$-dimensional axis
containing $p(V(G_{A})\cap V(G_{B}))$ in such a way that $W^{*}$ becomes flat
in the resulting tensegrity. Since this procedure does not affect the flatness
of other bags, we can apply the argument in each bag independently.

Thus we may suppose that each bag is flat in $(G,\sigma,p)$. Pick any bag $W$
in $T$ and assume that $T$ is a tree rooted at $W$. Let $H$ be a
$d$-dimensional subspace that contains $p(W)$. We inductively rotate a sub-
tensegrity of $(G,\sigma,p)$ so that the points of each bag are contained in
$H$. Let $T^{\prime}$ be a sub-tree rooted at $W$, and assume that each bag in
$T^{\prime}$ is contained in $H$ in the current realization. We consider a bag
$W_{i}$ not contained in $T^{\prime}$ and hanging on $T^{\prime}$. Let $W_{j}$
be the parent of $W_{i}$ in $T$. Then $W_{j}$ is in $T^{\prime}$ and hence
$p(W_{j})$ is contained in $H$.

By the definition of tree decompositions, we have $W_{i}\cap W_{j}\leq{\rm
tw}(G)=d+1$. If the affine span of $p(W_{i}\cap W_{j})$ is $d$-dimensional,
then $p(W_{i})$ is already contained in $H$ since $p(W_{i})$ is flat and hence
$p(W_{i}\cap W_{j})$ affinely spans all points in $p(W_{i})$. If the dimension
of the affine span of $p(W_{i}\cap W_{j})$ is less than $d$, then we consider
the sub-tree $T_{i}$ of $T$ rooted at $W_{i}$ and not containing $W_{j}$.
Then, since $W_{i}$ is flat, we can rotation the sub-tensegrity induced by the
bags in $T_{i}$ about the affine span of $p(W_{i}\cap W_{j})$ so that all
points of $W_{i}$ are contained in $H$. Thus, the final tensegrity is
contained in a $d$-dimensional space $H$ as required. ∎

###  6.2 Realizable Dimension of Chordal Graphs

As an application, we shall give a characterization of ${\rm rd}(G)$ for
chordal graphs $G$.

A graph is said to be chordal if $G$ has no induced cycle of length more than
three. There are several equivalent characterizations of chordal graphs. One
of well-known characterizations is in terms of the intersection graphs of
subtrees. Let $V$ be a finite set, $T$ be a tree on a finite set ${\cal W}$,
and $\\{T_{v}:v\in V\\}$ be a collection of subtrees in $T$, each $T_{v}$ of
which is labeled by $v\in V$. The intersection graph is defined as a graph on
$V$ such that $u$ and $v$ are connected by an edge if and only if
$V(T_{u})\cap V(T_{v})\neq\emptyset$. It is known that the resulting graph is
chordal and moreover any chordal graph can be represented as the intersection
graph of a collection of subtrees. This representation of a chordal graph $G$
gives us an optimal tree decomposition such that the collection of the bags
enumerates the maximal cliques of $G$.

Fallat and Mitchell [11] showed that $\nu(G)\in\\{{\rm tw}(G),{\rm
tw}(G)+1\\}$ and $\nu(G)={\rm tw}(G)+1$ holds if and only if there is a
maximum clique in which each pair of vertices is either linked by parallel
edges or is contained in other maximal clique. The following statement
complements to their result from the rigidity theory viewpoint.

######  Theorem 6.2.

Let $G$ be a chordal multigraph. Then $\lambda(G)=\nu(G)-1={\rm
rd}(G)\in\\{{\rm tw}(G)-1,{\rm tw}(G)\\}$. Moreover, ${\rm rd}(G)={\rm tw}(G)$
holds if and only if there is a maximum clique in which each pair of vertices
is either linked by parallel edges or is contained in other maximal clique.

###### Proof.

Let $t={\rm tw}(G)+1$, and consider an optimal tree decomposition $(T,{\cal
W})$ that represents $G$ as the intersection graph of subtrees. Then $W$ is a
largest bag in ${\cal W}$ if and only if it forms a maximum clique in $G$.
Hence, it suffices to show that ${\rm rd}(G)={\rm tw}(G)-1$ holds if and only
if $(T,{\cal W})$ is lacking.

If $(T,{\cal W})$ is lacking, then ${\rm rd}(G)\leq{\rm tw}(G)-1$ by Lemma
6.1. Since a maximum clique of $G$ has size $t$, the minor monotonicity of
$\lambda$ implies ${\rm tw}(G)-1=t-2=\lambda(K_{t})\leq\lambda(G)\leq{\rm
rd}(G)\leq{\rm tw}(G)-1$, and the equality holds in each inequality.

Suppose $(T,{\cal W})$ is not lacking. Fallat and Mitchell [11] have shown
that $\nu(G)={\rm tw}(G)+1$ in this case. Hence, the minor monotonicity and
Corollary 5.1 imply ${\rm tw}(G)=\nu(G)-1\leq{\rm rd}(G)\leq{\rm tw}(G)$, and
the equality holds throughout the inequalities. ∎

It is not difficult to show that ${\rm rd}(G^{=})={\rm tw}(G)$ for chordal
graphs $G$. Hence Theorem 6.2 gives an answer to Problem 5 for chordal graphs.

###  6.3 Realizable Dimension at Most One

In this section we give a characterization of graphs whose realizable
dimension is at most one.

######  Theorem 6.3.

The following are equivalent for a multigraph $G$.

(i)

${\rm rd}(G)\leq 1$.

(ii)

$\lambda(G)\leq 1$.

(iii)

$G$ has no minor isomorphic to $K_{4}$ or $K_{3}^{=}$.

###### Proof.

We have already shown ${\rm rd}(G)\geq\lambda(G)$ and
$\lambda(K_{4})=\lambda(K_{3}^{=})=2$. So, by the minor monotonicity of ${\rm
rd}(G)$, it suffices to show that (iii) implies (i).

Suppose $G$ has no minor isomorphic to $K_{4}$ or $K_{3}^{=}$. We show ${\rm
rd}(G)\leq 1$ by induction on $V(G)$.

We may assume that $G$ is 2-connected since otherwise we can decompose $G$
into $G_{1}$ and $G_{2}$ such that $|V(G_{1})\cap V(G_{2})|=1$ and a
1-dimensional deformation of any tensegrity realization of $G$ can be
constructed from those of $G_{1}$ and $G_{2}$ obtained by induction.

A basic fact from graph theory says that, for a simple graph $H$, ${\rm
tw}(H)\leq 2$ if and only if $H$ has no $K_{4}$ minor. Since $G$ has no
$K_{4}$ minor, $G$ admits a tree decomposition $(T,{\cal W})$ of width at most
two. We take an optimal tree decomposition $(T,{\cal W})$ such that the number
of non-lacking bags is as small as possible.

If the tree decomposition is lacking, then we can apply Lemma 6.1 to have
${\rm rd}(G)\leq{\rm tw}(G)-1=1$ and we are done. So we may assume that there
is at least one bag $W^{*}$ which is not lacking.

Since $G$ is 2-connected, the size of each bag is exactly three. Denote
$W^{*}=\\{v_{1},v_{2},v_{3}\\}$, and let $G_{1,2}$ be the subgraph of $G$
defined as the union of all paths between $v_{1}$ and $v_{2}$ internally
disjoint from $v_{3}$. Similarly, $G_{1,3}$ and $G_{2,3}$ are defined.

Suppose $G_{1,2}$ is a path $P$ between $v_{1}$ and $v_{2}$. See Figure 3 for
an illustration. We denote the sequence of the vertices of the path $G_{1}$ by
$v_{1}=u_{1},u_{2},\dots,u_{m}=v_{2}$. Then, in the tree decomposition $T$
there is a sub-path $P$ hanging at $W^{*}$ whose bags induce $G_{1}$. Then, we
can obtain a new optimal tree decomposition $(T^{\prime},{\cal W}^{\prime})$
from $(T,{\cal W})$ by deleting the sub-path $P$ and then splitting $W^{*}$
into the new path of bags
$\\{v_{3},u_{1},u_{2}\\},\\{v_{3},u_{2},u_{3}\\},\dots,\\{v_{3},u_{m-1},v_{m}\\}$.
See Figure 3. In the resulting tree decomposition, each new bag is lacking, so
the number of non-lacking bags decreases at least by one. This contradicts the
choice of $(T,{\cal W})$.

(a) $G$

(b) $T$

(c) $T^{\prime}$

Figure 3: Proof of Theorem 6.3. For a given graph $G$ in Figure (a), Figure
(b) is a tree decomposition $(T,{\cal W})$, where the bag
$W^{*}=\\{v_{1},v_{2},v_{3}\\}$ is not lacking. $G_{1,2}$ is the path
$u_{1},u_{2},u_{3},u_{4},u_{5}$ in Figure (a), and $P$ is the path
$\\{v_{1},v_{2},u_{2}\\},\\{v_{2},u_{2},u_{4}\\},\\{u_{2},u_{3},u_{4}\\}$ in
Figure (b). One can construct a new optimal tree decomposition as in Figure
(c) without creating a non-lacking bag.

Therefore, $G_{1,2}$ is not a path. Also $G_{1,2}$ is connected by the
2-connectivity of $G$. Symmetrically, $G_{i,j}$ is connected but not a path
for any distinct $i,j$ with $i,j\in\\{1,2,3\\}$. Then, in each $G_{i,j}$,
there are at least two distinct paths between $v_{i}$ and $v_{j}$, which
certificate a $K_{2}^{=}$ minor rooted at $v_{i}$ and $v_{j}$. The union of
such a $K_{2}^{=}$ minor rooted at $v_{i}$ and $v_{j}$ over all distinct $i,j$
with $i,j\in\\{1,2,3\\}$ gives a $K_{3}^{=}$ minor in $G$. This contradicts
that $G$ has no $K_{3}^{=}$ minor. ∎

Characterizing multigraphs with realizable dimension at most two is an
important open problem. We formulate it as a conjecture.

######  Conjecture 6.

The following are equivalent for a multigraph $G$.

(i)

${\rm rd}(G)\leq 2$.

(ii)

$\lambda(G)\leq 2$.

(iii)

$G$ has no minor isomorphic to a graph in Figure 2.

The proof of Theorem 6.3 shows that any multigraph having no $K_{4}$ or
$K_{3}^{=}$ minor has a lacking optimal tree decomposition, and hence any
realization can be folded to be 1-dimensional by Lemma 6.1. Such an argument
is not enough for Conjecture 6. For example, the Wagner graph $M_{8}$ (with
some parallel edges) satisfies the third condition in Conjecture 6, but we do
not know how to bound the realizable dimension by two.

#### Acknowledgement

The work was supported by JST PRESTO Grant Number JPMJPR2126 JST ERATO Grant
Number JPMJER1903, and JSPS KAKENHI Grant Number 18K11155.

## References

  * [1] A. Y. Alfakih, On dimensional rigidity of bar-and-joint frameworks. Discret. Appl. Math., 155, 1244–1253, 2007.
  * [2] A. Y. Alfakih, On bar frameworks, stress matrices and semidefinite programming. Math. Program. 129, 113–128, 2011.
  * [3] A. Y. Alfakih, Graph connectivity and universal rigidity of bar frameworks. Discret. Appl. Math., 217, 707–710, 2017.
  * [4] M. Belk and R. Connelly. Realizability of graphs. Disc. Comput. Geom. 37:125–137, 2007.
  * [5] Y. Colin de Verdière, Sur un nouvel invariant des graphes et un critère de planarité J. Combin. Theory Ser. B, 50, 11–21, 1990.
  * [6] Y. Colin de Verdière, Multiplicities of eigenvalues and tree-width of graphs, J. Combin. Theory Ser. B, 74, 121–146, 1998.
  * [7] R. Connelly, Rigidity and energy, Invent. Math., 66, 11-33, 1982.
  * [8] R. Connelly, S. J. Gortler, and L. Theran Affine rigidity and conics at infinity, Int. Math. Res. Not., Vol. 2018, No. 13, pp. 4084–4102
  * [9] R. Connelly and S. D. Guest, Frameworks, Tensegrities, and Symmetry, Cambridge University Press, 2022.
  * [10] R. Connelly and W. Whiteley, Second-order rigidity and prestress stability for tensegrity frameworks, SIAM J. Disc. Math., 9, 453–491, 1996.
  * [11] S. Fallat and L. Mitchell, Colin de Verdière parameters of chordal graphs. Electronic Journal of Linear Algebra, 26, 49–62, 2013.
  * [12] H. van der Holst, Topological and Spectral Graph Characterizations, Ph.D. thesis, University of Amsterdam, 1996.
  * [13] H. van der Holst, Graphs with magnetic Schrödinger operators of low corank. J. Combin. Theory Ser. B, 84, 311–339, 2002.
  * [14] D. Garamvölgyi, On the global rigidity of tensegrity graphs, Discrete Appl. Math., 302, 114–122, 2021.
  * [15] S. Gortler and D. Thurston, Characterizing the universal rigidity of generic frameworks. Discrete Comput. Geom., 51, 1017–1036, 2014.
  * [16] B. Jackson, T. Jordán, and C. Király, Strongly rigid tensegrity graphs on the line, Discrete Appl. Math., 161, 1147–1149, 2013.
  * [17] T. Jordán, A. Recski, and Z. Szabadka. Rigid tensegrity labelings of graphs. European Journal of Combinatorics, 30, 1887–1895, 2009.
  * [18] T. Jordán and S. Tanigawa, Global rigidity of triangulations with braces, J. Combin. Theory Ser. B, 136, 249–288, 2019.
  * [19] T. Jordan and W. Whiteley, Global rigidity, in: Handbook of Discrete and Computational Geometry, Third Edition, CRC Press, 1661–1694, 2017.
  * [20] L. Lovász, Graphs and Geometry, AMS, 2019.
  * [21] M. Laurent and A. Varvitsiotis, Positive semidefinite matrix completion, universal rigidity and the Strong Arnold Property, Linear Algebra Appl., 452, 292–317, 2014.
  * [22] B. Roth and W. Whiteley, Tensegrity frameworks, Trans. Amer. Math. Soc., 265, 419–446, 1981.
  * [23] J. Y. Zhang and M. Ohsaki, Tensegrity Structures: Form, Stability, and Symmetry. Springer, Berlin, 2015.
  * [24] J. Y. Zhang, S. D. Guest, R. Connelly, and M. Ohsaki, Dihedral ‘star’ tensegrity structures, International Journal of Solids and Structures, 47, 1–9, 2010.