# On the $d$-dimensional algebraic connectivity of graphs

Alan Lew<EMAIL_ADDRESS>Alan Lew was partially supported by the
Israel Science Foundation grant ISF-2480/20. Einstein Institute of
Mathematics, Hebrew University, Jerusalem 91904, Israel  Eran Nevo
<EMAIL_ADDRESS>Eran Nevo was partially supported by the Israel Science
Foundation grant ISF-2480/20. Einstein Institute of Mathematics, Hebrew
University, Jerusalem 91904, Israel  Yuval Peled<EMAIL_ADDRESS>Einstein Institute of Mathematics, Hebrew University, Jerusalem 91904, Israel
Orit E. Raz<EMAIL_ADDRESS>Einstein Institute of Mathematics, Hebrew
University, Jerusalem 91904, Israel

###### Abstract

The $d$-dimensional algebraic connectivity $a_{d}(G)$ of a graph $G=(V,E)$,
introduced by Jordán and Tanigawa, is a quantitative measure of the
$d$-dimensional rigidity of $G$ that is defined in terms of the eigenvalues of
stiffness matrices (which are analogues of the graph Laplacian) associated to
mappings of the vertex set $V$ into ${\mathbb{R}}^{d}$.

Here, we analyze the $d$-dimensional algebraic connectivity of complete
graphs. In particular, we show that, for $d\geq 3$, $a_{d}(K_{d+1})=1$, and
for $n\geq 2d$,

$\left\lceil\frac{n}{2d}\right\rceil-2d+1\leq
a_{d}(K_{n})\leq\frac{2n}{3(d-1)}+\frac{1}{3}.$

##  1 Introduction

A _$d$ -dimensional framework_ is a pair $(G,p)$ consisting of a graph
$G=(V,E)$ and a mapping of its vertices $p:V\to{\mathbb{R}}^{d}$. A framework
$(G,p)$ is called _rigid_ if every continuous motion of the vertices that
preserves the lengths of all the edges of $G$, preserves in fact the distance
between every two vertices of $G$.

In [2], Asimov and Roth introduced the stricter notion of _infinitesimal
rigidity_ : For two distinct vertices $u,v\in V$, let
$d_{uv}\in{\mathbb{R}}^{d}$ be defined by

$d_{uv}=\begin{cases}\frac{p(u)-p(v)}{\|p(u)-p(v)\|}&\text{ if }p(u)\neq
p(v),\\\ 0&\text{ otherwise,}\end{cases}$

and let $\mathbf{v}_{u,v}\in{\mathbb{R}}^{d|V|}$ be defined by

$\mathbf{v}_{u,v}^{t}=\hbox{}\vbox{\kern 0.86108pt\hbox{$\kern 0.0pt\kern
2.5pt\kern-5.0pt\left(\kern
0.0pt\kern-2.5pt\kern-6.66669pt\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$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
u$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
v$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\\\$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle\ldots$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
d_{uv}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\ldots$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle d_{vu}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\ldots$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt\crcr}}}}\right)$}}.$

Equivalently, $\mathbf{v}_{u,v}=(1_{u}-1_{v})\otimes d_{uv},$ where
$\\{1_{u}\\}_{u\in V}$ is the standard basis of ${\mathbb{R}}^{|V|}$ and
$\otimes$ denotes the Kronecker product.

The _normalized rigidity matrix_ of $(G,p)$, denoted by $R(G,p)$, is the
$d|V|\times|E|$ matrix whose columns are the vectors $\mathbf{v}_{u,v}$ for
all $\\{u,v\\}\in E$.

Assume that $|V|>d$. It is known (see [2]) that the rank of $R(G,p)$ is at
most $d|V|-\binom{d+1}{2}$. The framework $(G,p)$ is called _infinitesimally
rigid_ 111The usual definition of infinitesimal rigidity is in terms of the
unnormalized rigidity matrix, but both definitions are equivalent as scaling
of the columns of a matrix does not change its rank. if the rank of the
$R(G,p)$ is exactly $d|V|-\binom{d+1}{2}$.

Infinitesimal rigidity is in general stronger than rigidity, but it is known
that both notions coincide for “generic” embeddings (see [2]). Note that for
$d=1$, and assuming that $p$ is injective, both notions of rigidity coincide
with the notion of graph connectivity.

Recently Jordán and Tanigawa [7] (building on Zhu and Hu [10, 11] who
considered the $2$-dimensional case) introduced the following quantitative
measure of rigidity:

The _stiffness matrix_ $L(G,p)$ is defined by

$L(G,p)=R(G,p)R(G,p)^{t}\in{\mathbb{R}}^{d|V|\times d|V|}.$

It is easy to check that the rank of $L(G,p)$ equals the rank of $R(G,p)$.
Therefore, the kernel of $L(G,p)$ is of dimension at least $\binom{d+1}{2}$,
and equality occurs if and only if the framework $(G,p)$ is infinitesimally
rigid.

Let $\lambda_{i}(L(G,p))$ be the $i$-th smallest eigenvalue of $L(G,p)$. The
_spectral gap_ of $L(G,p)$ is its minimal non-trivial eigenvalue
$\lambda_{\binom{d+1}{2}+1}(L(G,p))$. The _$d$ -dimensional algebraic
connectivity of $G$_ is defined by

$a_{d}(G)=\sup\left\\{\lambda_{\binom{d+1}{2}+1}(L(G,p))\middle|\,p:V\to{\mathbb{R}}^{d}\right\\}.$

For $d=1$, $a_{1}(G)$ is the usual algebraic connectivity (a.k.a. spectral
gap) of $G$, introduced by Fiedler in [5]. For general $d$, we always have
$a_{d}(G)\geq 0$ (since $L(G,p)$ is positive semi-definite) and $a_{d}(G)>0$
if and only if a generic embedding of $G$ in ${\mathbb{R}}^{d}$ forms a rigid
framework.

Let $K_{n}$ be the complete graph on $n$ vertices. In [7], a lower bound on
$a_{d}(K_{n})$ was used to deduce an improved constant in a threshold result
for $d$-rigidity [8]: there exists a constant $C_{d}$ such that if
$pn>C_{d}\log n$ then a graph $G\in G(n,p)$, the Erdős-Rényi $n$-vertex random
graph with edge probability $p$, is asymptotically almost surely $d$-rigid.
(For a sharp threshold for $d$-rigidity see our recent [9].) Their estimate on
$C_{d}$ depended on the value of the spectral gap of the stiffness matrix of
the regular $d$-simplex graph $K_{d+1}$, denoted $s_{d}$, which was
conjectured to equal $1$ for $d\geq 3$.

Motivated by these results, we study in this paper the $d$-dimensional
algebraic connectivity of complete graphs. It is well known and easy to check
that $a_{1}(K_{n})=n$. For $d=2$, it was shown by Jordán and Tanigawa [7,
Theorem 4.4], based on a result by Zhu [10], that $a_{2}(K_{n})=n/2$ for all
$n\geq 3$ (see also Proposition 4.4). For $d\geq 3$ the situation is more
complicated, and the only previously known result is the lower bound
$a_{d}(K_{n})\geq s_{d}dn/(2(d+1)^{2})-d$, proved by Jordán and Tanigawa in
[7, Thm. 5.2]222The bound as stated in [7] is incorrect, the bound stated here
is obtained after fixing a typo in [7, Lemma 5.4]..

Here, we first focus on the case $n=d+1$. Let
$p^{\triangle}:V(K_{d+1})\to{\mathbb{R}}^{d}$ denote the regular simplex
embedding (that is, the vertices of $K_{d+1}$ are mapped bijectively to the
vertices of a regular simplex in ${\mathbb{R}}^{d}$), and denote

$s_{d}=\lambda_{\binom{d+1}{2}+1}(L(K_{d+1},p^{\triangle})).$

We prove the following.

######  Theorem 1.1.

The spectrum of $L(K_{d+1},p^{\triangle})$ is

$\left\\{0^{(d(d+1)/2)},1^{((d+1)(d-2)/2)},\frac{d+1}{2}^{(d)},d+1^{(1)}\right\\}.$

(The superscript $(m)$ indicates multiplicity $m$ of the corresponding
eigenvalue, here and throughout the paper.)

This settles a conjecture of Jordán and Tanigawa [7, Conj. 1]. In particular,
we obtain $s_{d}=1$ for $d\geq 3$. (Note that $s_{2}=3/2$.) Further, we show
that this is the largest possible spectral gap for a framework $(K_{d+1},p)$.
That is,

######  Theorem 1.2.

For $d\geq 3$, $a_{d}(K_{d+1})=1$.

However, for $d\geq 3$, $p^{\triangle}$ is not the only embedding that
achieves the maximum value $a_{d}(K_{d+1})=1$, see Proposition 3.1.

Next we consider (balanced) Turán graphs: Let $r,n$ be positive integers such
that $r$ divides $n$. Let $V_{1},\ldots,V_{r}$ be pairwise disjoint sets such
that $|V_{i}|=n/r$ for all $i\in[r]$. Let $V=V_{1}\cup\cdots\cup V_{r}$ and
$E=\cup_{i\neq j\in[r]}\\{\\{u,v\\}:\,u\in V_{i},v\in V_{j}\\}$. The graph
$T(n,r)=(V,E)$ is called a Turán graph, or the complete balanced $r$-partite
graph on $n$ vertices.

For $r=d+1$ let $q^{\triangle}:V\to{\mathbb{R}}^{d}$ denote the mapping into
the vertices of a regular $d$-simplex, such that the preimage of each vertex
of the simplex equals $V_{i}$ for a different $i\in[d+1]$. We compute the
spectrum of $L(T(n,d+1),q^{\triangle})$:

######  Theorem 1.3.

Let $d\geq 2$ and $n\geq d+1$ such that $n$ is divisible by $d+1$. Then, the
spectrum of $L(T(n,d+1),q^{\triangle})$ is

$\left\\{0^{(d(d+1)/2)},\frac{n}{2(d+1)}^{((n-d-1)(d-1))},\frac{n}{d+1}^{((d-2)(d+1)/2)},\frac{n}{2}^{(n-1)},n^{(1)}\right\\}.$

In particular, its spectral gap for $n\geq 2(d+1)$ is:

$\lambda_{\binom{d+1}{2}+1}(L(T(n,d+1),q^{\triangle}))=\frac{n}{2(d+1)}.$

This improves upon the lower bound
$\lambda_{\binom{d+1}{2}+1}(L(T(n,d+1),q^{\triangle}))\geq\frac{dn}{2(d+1)^{2}}$
obtained in [7] (after fixing a typo and plugging $s_{d}=1$).

Similarly, for $r=2d$ let $q^{\diamond}:V\to{\mathbb{R}}^{d}$ denote the
mapping into the vertices of a regular $d$-crosspolytope, such that the
preimage of each vertex of the crosspolytope equals $V_{i}$ for a different
$i\in[2d]$ (recall that the regular $d$-crosspolytope is defined as the convex
hull of the set $\\{\pm e_{1},\ldots,\pm e_{d}\\}$, where
$\\{e_{1},\ldots,e_{d}\\}$ is the standard basis of ${\mathbb{R}}^{d}$). We
compute the spectrum of $L(T(n,2d),q^{\diamond})$:

######  Theorem 1.4.

Let $d\geq 2$ and $n\geq 2d$ such that $n$ is divisible by $2d$. Then, the
spectrum of $L(T(n,2d),q^{\diamond})$ is

$\left\\{0^{(d(d+1)/2)},\frac{n}{2d}^{(n(d-1)-d^{2})},\frac{n}{d}^{(d(d-1)/2)},\frac{n}{2}^{(n-1)},n^{(1)}\right\\}.$

In particular, its spectral gap is:

$\lambda_{\binom{d+1}{2}+1}(L(T(n,2d),q^{\diamond}))=\frac{n}{2d}.$

The proofs of Theorems 1.3 and 1.4 follow by computing the eigenbases the
corresponding stiffness matrices. As a corollary of Theorem 1.4, we obtain the
following lower bound on $a_{d}(K_{n})$:

######  Theorem 1.5.

Let $d\geq 3$ and $n\geq 2d$. If $n$ is divisible by $2d$, then

$a_{d}(K_{n})\geq\frac{n}{2d}.$

For general $n\geq 2d$, we have
$a_{d}(K_{n})\geq\left\lceil\frac{n}{2d}\right\rceil-2d+1.$

This improves the previously known lower bound. Finally, we prove an upper
bound on the $d$-dimensional algebraic connectivity of the complete graph:

######  Theorem 1.6.

Let $d\geq 3$ and $n\geq d+1$. Then,

$a_{d}(K_{n})\leq\frac{2n}{3(d-1)}+\frac{1}{3}\,.$

This follows by proving a lower bound on the sum of the $n$ largest
eigenvalues of $L(K_{n},p)$ for every embedding $p$ into ${\mathbb{R}}^{d}$
(see Lemma 5.1).

Most of our results rely on analyzing the _lower stiffness matrix_ of the
framework $(G,p)$, defined by

$L^{-}(G,p)=R(G,p)^{t}R(G,p)\in{\mathbb{R}}^{|E|\times|E|}.$

It is easy to check that
$\operatorname{\text{rank}}(L(G,p))=\operatorname{\text{rank}}(L^{-}(G,p))=\operatorname{\text{rank}}(R(G,p))$,
and that the non-zero eigenvalues of $L(G,p)$ are the same as those of
$L^{-}(G,p)$, namely also with same multiplicities.

Outline: In Section 2 we describe $L^{-}(G,p)$ explicitly and apply Cauchy’s
Interlacing Theorem to relate the spectra of $L(G,p)$ and $L(G\setminus{e},p)$
where $e$ is an edge in $G$. In Section 3 we compute the spectrum of
$L(K_{d+1},p^{\triangle})$ and determine the value of $a_{d}(K_{d+1})$. In
Section 4 we find the spectrum and eigenbasis of $L(T(n,d+1),q^{\triangle})$,
improving on the estimate in [7] for its spectral gap, and similarly we find
the spectrum and eigenbasis of $L(T(n,2d),q^{\diamond})$, concluding a lower
bound on $a_{d}(K_{n})$. In Section 5 we lower bound the sum of the largest
$n$ eigenvalues of $L(K_{n},p)$ for every embedding $p$, and use it to prove
an upper bound on $a_{d}(K_{n})$. We conclude in Section 6 with open problems
and conjectures on $a_{d}(G)$ for graphs of interest.

##  2 The lower stiffness matrix

We start with the following explicit description of $L^{-}(G,p)$:

######  Lemma 2.1.

Let $G=(V,E)$ be a graph and let $p:V\to{\mathbb{R}}^{d}$. Let $e_{1},e_{2}\in
E$. Then,

$L^{-}(G,p)(e_{1},e_{2})=\begin{cases}2&\text{ if }e_{1}=e_{2}=\\{i,j\\}\text{
and }p(i)\neq p(j),\\\ \cos(\theta(e_{1},e_{2}))&\text{ if }|e_{1}\cap
e_{2}|=1,\\\ 0&\text{ otherwise,}\end{cases}$

where, for $e_{1}=\\{i,j\\}$ and $e_{2}=\\{i,k\\}$, $\theta(e_{1},e_{2})$ is
the angle between $d_{ij}$ and $d_{ik}$; that is,
$\cos(\theta(e_{1},e_{2}))=d_{ij}\cdot d_{ik}$ (note that, by convention, if
$d_{ij}=0$ or $d_{ik}=0$, then $\cos(\theta(e_{1},e_{2}))=0$).

###### Proof.

For convenience, we identify the vertex set of $G$ with the set $[n]$. Let
$e_{1}=\\{i,j\\}$ and $e_{2}=\\{k,l\\}$, where $i<j$ and $k<l$. Let
$\\{1_{i}\\}_{i\in V}$ be the standard basis for ${\mathbb{R}}^{|V|}$, and
$\\{1_{e}\\}_{e\in E}$ be the standard basis for ${\mathbb{R}}^{|E|}$. Then,

$R(G,p)1_{e_{1}}=(1_{i}-1_{j})\otimes d_{ij},$

and similarly

$R(G,p)1_{e_{2}}=(1_{k}-1_{l})\otimes d_{kl}.$

Note that

$L^{-}(G,p)(e_{1},e_{2})=(R(G,p)1_{e_{1}})^{t}(R(G,p)1_{e_{2}})=((1_{i}-1_{j})\cdot(1_{k}-1_{l}))(d_{ij}\cdot
d_{kl}).$

If $e_{1}=e_{2}$, we obtain

$L^{-}(G,p)(e_{1},e_{2})=\|1_{i}-1_{j}\|^{2}\cdot\|d_{ij}\|^{2}=\begin{cases}2&\text{
if }p(i)\neq p(j),\\\ 0&\text{ otherwise.}\end{cases}$

If $e_{1}\cap e_{2}=\emptyset$, then

$L^{-}(G,p)(e_{1},e_{2})=((1_{i}-1_{j})\cdot(1_{k}-1_{l}))(d_{ij}\cdot
d_{kl})=0\cdot(d_{ij}\cdot d_{kl})=0.$

Finally, assume $|e_{1}\cap e_{2}|=1$. Then, either $i=k$, or $i=l$, or $j=k$
or $j=l$. If $i=k$, then

$L^{-}(G,p)(e_{1},e_{2})=1\cdot(d_{ij}\cdot
d_{il})=\cos(\theta(e_{1},e_{2})).$

If $i=l$, then

$L^{-}(G,p)(e_{1},e_{2})=(-1)\cdot(d_{ij}\cdot d_{ki})=d_{ij}\cdot
d_{ik}=\cos(\theta(e_{1},e_{2})).$

The other two cases follow similarly. ∎

  * Remark.

In [1], the lower stiffness matrix $L^{-}(G,p)$ was studied in the special
case where $G=K_{3}$, the complete graph on three vertices, and $p$ is an
embedding of the vertices in ${\mathbb{R}}^{2}$.

###  2.1 Interlacing of spectra

We will use the following special case of Cauchy’s interlacing theorem:

######  Theorem 2.2 (See e.g. [3]).

Let $A$ be a real symmetric matrix of size $n\times n$ and $B$ a principal
submatrix of $A$ of size $(n-1)\times(n-1)$. Let
$\mu_{1}\geq\mu_{2}\geq\cdots\geq\mu_{n}$ be the eigenvalues of $A$ and
$\mu^{\prime}_{1}\geq\mu^{\prime}_{2}\geq\cdots\geq\mu^{\prime}_{n-1}$ be the
eigenvalues of $B$. Then, for $1\leq i\leq n-1$, we have

$\mu_{i}\geq\mu^{\prime}_{i}\geq\mu_{i+1}.$

We obtain the following interlacing result, generalizing a known result for
graph Laplacians (see e.g. [6, Theorem 13.6.2]).

######  Theorem 2.3.

Let $G=(V,E)$ be a graph with $|V|=n$, and let $p:V\to{\mathbb{R}}^{d}$. Let
$e\in E$, and let $G\setminus e=(V,E\setminus\\{e\\})$. Let
$\lambda_{1}\leq\lambda_{2}\leq\cdots\leq\lambda_{dn}$ be the eigenvalues of
$L(G,p)$ and $\lambda^{\prime}_{1}\leq\cdots\leq\lambda^{\prime}_{dn}$ be the
eigenvalues of $L(G\setminus e,p)$. Let $\lambda_{0}=0$. Then, we have

$\lambda_{i-1}\leq\lambda^{\prime}_{i}\leq\lambda_{i},$

for all $1\leq i\leq dn$.

###### Proof.

Let $\mu^{\prime}_{1}\geq\cdots\geq\mu^{\prime}_{|E|}$ be the eigenvalues of
$L^{-}(G,p)$ and $\mu_{1}\geq\cdots\geq\mu_{|E|-1}$ be the eigenvalues of
$L^{-}(G\setminus e,p)$.

Note that $L^{-}(G\setminus\\{e\\},p)$ is a principal submatrix of
$L^{-}(G,p)$, therefore by Theorem 2.2, we have

$\mu_{i}\geq\mu^{\prime}_{i}\geq\mu_{i+1}$

for $i=1,\ldots,|E|-1$.

For $i>|E|-1$, let $\mu^{\prime}_{i}=0$, and for $i>|E|$, let $\mu_{i}=0$.
Then, we have

$\mu_{i}\geq\mu^{\prime}_{i}\geq\mu_{i+1}$

for all $i$. Since $L(G,p)$ and $L^{-}(G,p)$ have the same positive
eigenvalues, we have for all $i=1,\ldots,dn$

$\lambda_{dn+1-i}=\mu_{i},$

and similarly

$\lambda^{\prime}_{dn+1-i}=\mu^{\prime}_{i}.$

Therefore, we have

$\lambda_{dn+1-i}\geq\lambda^{\prime}_{dn+1-i}\geq\lambda_{dn-i}$

for all $i=1,\ldots,dn$ (using $\lambda_{0}=0$). So, for $j=1,\ldots,dn$, we
obtain

$\lambda_{j-1}\leq\lambda^{\prime}_{j}\leq\lambda_{j},$

as wanted. ∎

As an application of Theorem 2.3, we show that restricting attention to maps
$p:V\to{\mathbb{R}}^{d}$ that are embeddings (i.e injective) does not affect
the $d$-dimensional algebraic connectivity of a graph $G=(V,E)$.

######  Lemma 2.4.

Let $G=(V,E)$ and $d\geq 1$. Then,

$a_{d}(G)=\sup\left\\{\lambda_{\binom{d+1}{2}+1}(L(G,p))\middle|\,p:V\to{\mathbb{R}}^{d},\,p\text{
is injective}\right\\}.$

###### Proof.

Let

$\tilde{a}_{d}(G)=\sup\left\\{\lambda_{\binom{d+1}{2}+1}(L(G,p))\middle|\,p:V\to{\mathbb{R}}^{d},\,p\text{
is injective}\right\\}.$

Clearly, $\tilde{a}_{d}(G)\leq a_{d}(G)$. In the other direction, let
$p:V\to{\mathbb{R}}^{d}$. We will show that for any $\epsilon>0$ there exists
a $p^{\prime}:V\to{\mathbb{R}}^{d}$ such that $p^{\prime}$ is injective and

$\lambda_{\binom{d+1}{2}+1}(L(G,p^{\prime}))>\lambda_{\binom{d+1}{2}+1}(L(G,p))-\epsilon.$

Let $E^{\prime}=\\{\\{u,v\\}\in E:\,p(u)\neq p(v)\\}$ and let
$G^{\prime}=(V,E^{\prime})$. Note that $L(G,p)=L(G^{\prime},p)$, and in
particular
$\lambda_{\binom{d+1}{2}+1}(L(G,p))=\lambda_{\binom{d+1}{2}+1}(L(G^{\prime},p))$.

By Lemma 2.1, for $p^{\prime}$ in a neighborhood of $p$, the entries of the
lower stiffness matrix $L^{-}(G^{\prime},p^{\prime})$ are continuous functions
of $p^{\prime}$. Therefore, the spectral gap
$\lambda_{\binom{d+1}{2}+1}(L(G^{\prime},p^{\prime}))$ is also continuous in
$p^{\prime}$ (as a root of the characteristic polynomial of
$L^{-}(G^{\prime},p^{\prime}))$. That is, there exists $\delta>0$ such that if
$\|p(u)-p^{\prime}(u)\|<\delta$ for all $u\in V$, then

$\left|\lambda_{\binom{d+1}{2}+1}(L(G^{\prime},p^{\prime}))-\lambda_{\binom{d+1}{2}+1}(L(G^{\prime},p))\right|<\epsilon.$

Now, let $p^{\prime}:V\to{\mathbb{R}}^{d}$ be an embedding satisfying
$\|p(u)-p^{\prime}(u)\|<\delta$ for all $u\in V$. Then, we have

$\lambda_{\binom{d+1}{2}+1}(L(G^{\prime},p^{\prime}))>\lambda_{\binom{d+1}{2}+1}(L(G^{\prime},p))-\epsilon=\lambda_{\binom{d+1}{2}+1}(L(G,p))-\epsilon.$

Finally, by Theorem 2.3, we obtain

$\lambda_{\binom{d+1}{2}+1}(L(G,p^{\prime}))\geq\lambda_{\binom{d+1}{2}+1}(L(G^{\prime},p^{\prime}))>\lambda_{\binom{d+1}{2}+1}(L(G,p))-\epsilon.$

Thus, $\tilde{a}_{d}(G)\geq a_{d}(G)$, as wanted. ∎

##  3 The $d$-dimensional algebraic connectivity of the simplex graph

It is known (see [7]) that $a_{1}(K_{n})=n$ and $a_{2}(K_{n})=n/2$. In
particular, $a_{2}(K_{3})=3/2$. In this section we prove the following:

See 1.2

###  3.1 Lower bound: $a_{d}(K_{d+1})\geq 1$

Recall that $p^{\triangle}:V\to{\mathbb{R}}^{d}$ is the embedding that maps
each vertex of $K_{d+1}$ to one of the vertices of the regular $d$-dimensional
simplex. The lower bound follows from the following result, conjectured in [7,
Conj.1]:

See 1.1

###### Proof.

Let $K_{d+1}=(V,E)$, where $V=[d+1]$ and $E=\binom{[d+1]}{2}$. Since the angle
between every two intersecting edges of the regular simplex is $60\degree$, we
have, by Lemma 2.1,

$L^{-}(K_{d+1},p^{\triangle})(e_{1},e_{2})=\begin{cases}2&\text{ if
}e_{1}=e_{2},\\\ \frac{1}{2}&\text{ if }|e_{1}\cap e_{2}|=1,\\\ 0&\text{
otherwise,}\end{cases}$

for every $e_{1},e_{2}\in E$. We can write

$L^{-}(K_{d+1},p^{\triangle})=I+\frac{1}{2}Q,$

where $Q\in{\mathbb{R}}^{|E|\times|E|}$ is defined by

$Q(e_{1},e_{2})=\begin{cases}2&\text{ if }e_{1}=e_{2},\\\ 1&\text{ if
}|e_{1}\cap e_{2}|=1,\\\ 0&\text{ otherwise,}\end{cases}$

for every $e_{1},e_{2}\in E$.

Let $M\in{\mathbb{R}}^{(d+1)\times|E|}$ be the signless incidence matrix of
$K_{d+1}$, defined by

$M(i,e)=\begin{cases}1&\text{ if }i\in e,\\\ 0&\text{ otherwise,}\end{cases}$

for $i\in V=[d+1]$ and $e\in E$. Then, we have

$Q=M^{t}M.$

Let

$\tilde{Q}=MM^{t}\in{\mathbb{R}}^{(d+1)\times(d+1)}.$

The matrix $\tilde{Q}$ is the signless Laplacian of $K_{d+1}$, namely:

$\tilde{Q}(i,j)=\begin{cases}d&\text{ if }i=j,\\\ 1&\text{
otherwise.}\end{cases}$

Therefore, $\tilde{Q}=(d-1)I+J$, where $J$ is the all-ones matrix. The
spectrum of $J$ is $\\{0^{(d)},d+1^{(1)}\\}$; therefore, the spectrum of
$\tilde{Q}$ is $\\{d-1^{(d)},2d^{(1)}\\}$. Since the non-zero eigenvalues of
$Q$ and $\tilde{Q}$ are the same, the spectrum of $Q$ is
$\\{0^{((d-2)(d+1)/2)},d-1^{(d)},2d^{(1)}\\}$. Thus, the spectrum of
$L^{-}(K_{d+1},p^{\triangle})$ is

$\left\\{1^{((d-2)(d+1)/2)},\frac{d+1}{2}^{(d)},d+1^{(1)}\right\\}.$

Finally, since the non-zero eigenvalues of $L^{-}(K_{d+1},p^{\triangle})$ and
$L(K_{d+1},p^{\triangle})$ are the same, the spectrum of
$L(K_{d+1},p^{\triangle})$ is

$\left\\{0^{(d(d+1)/2)},1^{((d-2)(d+1)/2)},\frac{d+1}{2}^{(d)},d+1^{(1)}\right\\},$

as wanted. ∎

As a consequence of Theorem 1.2, we obtain $a_{d}(K_{d+1})\geq 1$ for all
$d\geq 3$. We are left to show that $a_{d}(K_{d+1})\leq 1$. Before doing that,
let us remark that for $d\geq 3$ there are embeddings $p\neq p^{\triangle}$
such that $\lambda_{\binom{d+1}{2}+1}(L(K_{d+1},p))=1$:

######  Proposition 3.1.

Let $p_{1},p_{2},p_{3}\in{\mathbb{R}}^{2}$ be the vertices of an equilateral
triangle with sides of length $1$ centered at the origin. For $h\geq 0$, let
$p_{h}:[4]\to{\mathbb{R}}^{3}$ be defined by

$p_{h}(i)=\begin{cases}(p_{i},0)&\text{ if }i\in[3],\\\ (0,h)&\text{ if
}i=4.\end{cases}$

Then, the spectrum of $L(K_{4},p_{h})$ is

$\left\\{0^{(6)},1^{(2)},\left(3-\left(h^{2}+\frac{1}{3}\right)^{-1}\right)^{(1)},\left(\frac{3}{2}+\frac{1}{2}\left(h^{2}+\frac{1}{3}\right)^{-1}\right)^{(2)},4^{(1)}\right\\}.$

In particular, for $h\geq\frac{1}{\sqrt{6}}$, we have
$\lambda_{7}(L(K_{4},p_{h}))=1$.

###### Proof.

Denote the edges of the tetrahedron formed by the image of $p_{h}$ by
$e_{ij}$, $1\leq i\neq j\leq 4$. Let $\ell$ be the length of the edges
$e_{i4}$ (for $i\in[3]$). Note that $\ell=\sqrt{h^{2}+\frac{1}{3}}$. It is
easy to check that for three distinct indices $i,j,k$

$\cos(\theta(e_{ij},e_{jk}))=\begin{cases}\frac{1}{2}&\text{ if
}i,j,k\in[3],\\\ \frac{1}{2\ell}&\text{ if }i,j\in[3],k=4,\\\
1-\frac{1}{2\ell^{2}}&\text{ if }i,k\in[3],j=4.\end{cases}$

Therefore, by Lemma 2.1, we have

$L^{-}(K_{4},p_{h})=\begin{pmatrix}2&\frac{1}{2}&\frac{1}{2}&\frac{1}{2\ell}&\frac{1}{2\ell}&0\\\\[5.0pt]
\frac{1}{2}&2&\frac{1}{2}&\frac{1}{2\ell}&0&\frac{1}{2\ell}\\\\[5.0pt]
\frac{1}{2}&\frac{1}{2}&2&0&\frac{1}{2\ell}&\frac{1}{2\ell}\\\\[5.0pt]
\frac{1}{2\ell}&\frac{1}{2\ell}&0&2&1-\frac{1}{2\ell^{2}}&1-\frac{1}{2\ell^{2}}\\\\[5.0pt]
\frac{1}{2\ell}&0&\frac{1}{2\ell}&1-\frac{1}{2\ell^{2}}&2&1-\frac{1}{2\ell^{2}}\\\\[5.0pt]
0&\frac{1}{2\ell}&\frac{1}{2\ell}&1-\frac{1}{2\ell^{2}}&1-\frac{1}{2\ell^{2}}&2\end{pmatrix}.$

The spectrum of $L^{-}(K_{4},p_{h})$ can now be computed with the help of a
computer algebra system. We obtain the following eigenvalues:

$1^{(2)},\left(3-\ell^{-2}\right)^{(1)},\left(\frac{3}{2}+\frac{1}{2}\ell^{-2}\right)^{(2)},4^{(1)}.$

Since the non-zero eigenvalues of $L^{-}(K_{4},p_{h})$ are the same as those
of $L(K_{4},p_{h})$, and $\ell^{2}=h^{2}+\frac{1}{3}$, the spectrum of
$L(K_{4},p_{h})$ is

$\left\\{0^{(6)},1^{(2)},\left(3-\left(h^{2}+\frac{1}{3}\right)^{-1}\right)^{(1)},\left(\frac{3}{2}+\frac{1}{2}\left(h^{2}+\frac{1}{3}\right)^{-1}\right)^{(2)},4^{(1)}\right\\},$

as wanted. Finally, note that for $h\geq\frac{1}{\sqrt{6}}$ we obtain

$3-(h^{2}+\frac{1}{3})^{-1}\geq 3-2=1,$

and therefore $\lambda_{7}(K_{4},p_{h})=1$. ∎

###  3.2 Upper bound: $a_{d}(K_{d+1})\leq 1$

First, we prove the $3$-dimensional case:

######  Proposition 3.2.

$a_{3}(K_{4})=1.$

###### Proof.

Let $p:V\to{\mathbb{R}}^{3}$. Note that, since $|E|=6=dn-\binom{d+1}{2}$ (for
$d=3$ and $n=4$),

$\lambda_{7}(L(K_{4},p))=\lambda_{\binom{3+1}{2}+1}(L(K_{4},p))$

is equal to the minimal eigenvalue of $L^{-}(K_{4},p)$. Thus, for every $0\neq
x\in{\mathbb{R}}^{6}$

$\lambda_{7}(L(K_{4},p))\leq\frac{x^{t}L^{-}(K_{4},p)x}{\|x\|^{2}}.$

Let $e_{1},e_{1}^{\prime},e_{2},e_{2}^{\prime},e_{3},e_{3}^{\prime}$ be the
edges of $K_{4}$, such that $e_{i}\cap e_{i}^{\prime}=\emptyset$ for all $i$.
Let
$\ell_{1},\ell_{1}^{\prime},\ell_{2},\ell^{\prime}_{2},\ell_{3},\ell^{\prime}_{3}$
be the lengths of the images of
$e_{1},e_{1}^{\prime},e_{2},e_{2}^{\prime},e_{3},e_{3}^{\prime}$ (that is, if
$e_{i}=\\{u,v\\}$, $\ell_{i}=\|p(u)-p(v)\|$).

Assume without loss of generality that
$\ell_{3}^{2}+\ell_{3}^{{}^{\prime}2}\leq\min\\{\ell_{1}^{2}+\ell_{1}^{{}^{\prime}2},\ell_{2}^{2}+\ell_{2}^{{}^{\prime}2}\\}$.
Let

$x=\ell_{1}1_{e_{1}}+\ell_{1}^{\prime}1_{e_{1}^{\prime}}-\ell_{2}1_{e_{2}}-\ell_{2}^{\prime}1_{e_{2}^{\prime}}.$

Then,
$\|x\|^{2}=\ell_{1}^{2}+\ell_{1}^{{}^{\prime}2}+\ell_{2}^{2}+\ell_{2}^{{}^{\prime}2}$,
and

$x^{t}L^{-}(K_{4},p)x=2\|x\|^{2}-2(\ell_{1}\ell_{2}\cos(\theta(e_{1},e_{2}))+\ell_{1}\ell_{2}^{\prime}\cos(\theta(e_{1},e^{\prime}_{2}))\\\
+\ell_{1}^{\prime}\ell_{2}\cos(\theta(e^{\prime}_{1},e_{2}))+\ell_{1}^{\prime}\ell_{2}^{\prime}\cos(\theta(e^{\prime}_{1},e^{\prime}_{2}))).$

By the law of cosines, we obtain

$x^{t}L^{-}(K_{4},p)x=2\|x\|^{2}+2(\ell_{3}^{2}+\ell_{3}^{{}^{\prime}2}-\ell_{1}^{2}-\ell_{1}^{{}^{\prime}2}-\ell_{2}^{2}-\ell_{2}^{{}^{\prime}2})=2(\ell_{3}^{2}+\ell_{3}^{{}^{\prime}2}).$

So,

$\frac{x^{t}L^{-}(K_{4},p)x}{\|x\|^{2}}=\frac{2(\ell_{3}^{2}+\ell_{3}^{{}^{\prime}2})}{\ell_{1}^{2}+\ell_{1}^{{}^{\prime}2}+\ell_{2}^{2}+\ell_{2}^{{}^{\prime}2}}\leq
1.$

Therefore, we obtain

$\lambda_{7}(L(K_{4},p))\leq 1.$

∎

Finally, we show that the bound for general $d$ follows from the $d=3$ case:

######  Proposition 3.3.

For all $d\geq 4$,

$a_{d}(K_{d+1})\leq a_{3}(K_{4})=1.$

###### Proof.

Let $K_{d+1}=(V,E)$, where $V=[d+1]$ and $E=\binom{[d+1]}{2}$. We will show
that for every $d$,

$a_{d}(K_{d+1})\leq a_{d-1}(K_{d}).$

Let $G$ be the graph obtained by adding an isolated vertex $v$ to $K_{d}$.
Then, $G$ is obtained from $K_{d+1}$ by removing the $d$ edges containing $v$.
Therefore, for every $p:V\to{\mathbb{R}}^{d}$, we have by Theorem 2.3,

$\lambda_{\binom{d+1}{2}+1}(L(K_{d+1},p))\leq\lambda_{\binom{d+1}{2}+d+1}(L(G,p)).$

Let $H$ be an affine hyperplane containing $p(V\setminus\\{v\\})$. Identify
$H$ with ${\mathbb{R}}^{d-1}$, and let
$p^{\prime}=p|_{V\setminus\\{v\\}}:V\setminus\\{v\\}\to{\mathbb{R}}^{d-1}$.
Note that $L^{-}(G,p)=L^{-}(K_{d},p^{\prime})$; therefore, the non-zero
eigenvalues of $L(G,p)$ and $L(K_{d},p^{\prime})$ are the same. Since
$L(K_{d},p^{\prime})\in{\mathbb{R}}^{(d-1)d\times(d-1)d}$ and
$L(G,p)\in{\mathbb{R}}^{d(d+1)\times d(d+1)}$, this means in particular that

$\lambda_{\binom{d}{2}+1}(L(K_{d},p^{\prime}))=\lambda_{\binom{d}{2}+2d+1}(L(G,p))=\lambda_{\binom{d+1}{2}+d+1}(L(G,p)).$

So, we obtain

$\lambda_{\binom{d+1}{2}+1}(L(K_{d+1},p))\leq\lambda_{\binom{d}{2}+1}(L(K_{d},p^{\prime}))\leq
a_{d-1}(K_{d}).$

Since this holds for every $p:V\to{\mathbb{R}}^{d}$, we obtain

$a_{d}(K_{d+1})\leq a_{d-1}(K_{d}),$

as wanted. Therefore, the bound

$a_{d}(K_{d+1})\leq a_{3}(K_{4})=1$

follows by induction on $d$. ∎

##  4 Spectra of Turán graphs $T(n,d+1)$ and $T(n,2d)$

Recall that $T(n,r)$ is the complete balanced $r$-partite graph with $n$
vertices. For $r=d+1$, we denote by $q^{\triangle}:[n]\to{\mathbb{R}}^{d}$ the
mapping that maps the vertices of each of the $d+1$ parts of $T(n,d+1)$ to one
of the vertices of the regular $d$-dimensional simplex. Similarly, we denote
by $q^{\diamond}:[n]\to{\mathbb{R}}^{d}$ the mapping that maps the vertices of
each of the $2d$ parts of $T(n,2d)$ to one of the vertices of the regular
$d$-dimensional crosspolytope. In this section we determine the spectra of
$L(T(n,d+1),q^{\triangle})$ and $L(T(n,2d),q^{\diamond})$. In fact, in each
case we provide a basis of ${\mathbb{R}}^{E}$ consisting of eigenvectors of
the corresponding lower stiffness matrix.

As a consequence, we obtain a lower bound on the $d$-dimensional algebraic
connectivity of $K_{n}$ (Theorem 1.5).

We begin with the following result of Jordán and Tanigawa:

######  Lemma 4.1 ([7, Lemma 4.3]).

Let $p:[n]\to{\mathbb{R}}^{d}$. If $p$ is not constant, then the largest
eigenvalue of $L(K_{n},p)$ is $n$.

In [7] it was shown that $p$ itself (when considered as a vector in
${\mathbb{R}}^{dn}$) is an eigenvector of $L(K_{n},p)$ with eigenvalue $n$.
The corresponding eigenvector for $L^{-}(K_{n},p)$ is $\phi=R(G,p)^{t}p$,
which satisfies

$\phi(\\{i,j\\})=\|p(i)-p(j)\|$

for each $i\neq j\in[n]$.

The following result shows that for mappings $p$ satisfying certain “spherical
symmetry”, $n/2$ is an eigenvalue of $L(K_{n},p)$ of high multiplicity:

######  Proposition 4.2.

Let $p:[n]\to{\mathbb{R}}^{d}$ such that $\|p(i)\|=1$ for all $i\in[n]$ and
$\sum_{i=1}^{n}p(i)=0$. Assume that the image of $p$ is of size at least $3$.
Then, $n/2$ is an eigenvalue of $L(K_{n},p)$ with multiplicity at least $n-1$.

###### Proof.

Since the non-zero eigenvalues of $L(K_{n},p)$ and $L^{-}(K_{n},p)$ are the
same, it is enough to look at $L^{-}(K_{n},p)$.

Let $f\in{\mathbb{R}}^{n}$ such that $\sum_{i=1}^{n}f_{i}=0$. For every $i\neq
j\in[n]$, let $\ell_{ij}=\|p(i)-p(j)\|$. Let $E=E(K_{n})=\\{\\{i,j\\}:\,1\leq
i<j\leq n\\}$, and let $\phi_{f}\in{\mathbb{R}}^{E}$ be defined by

$\phi_{f}(\\{i,j\\})=(f_{i}+f_{j})\ell_{ij}.$

We will show that $\phi_{f}$ is an eigenvector of $L^{-}(K_{n},p)$ with
eigenvalue $n/2$.

For $i,j,k\in[n]$, let $\theta_{ijk}$ be the angle between $p(i)-p(j)$ and
$p(k)-p(j)$. By the law of cosines, we have

$\ell_{ij}\ell_{jk}\cos(\theta_{ijk})=\frac{1}{2}\left(\ell_{ij}^{2}+\ell_{jk}^{2}-\ell_{ik}^{2}\right).$

Let $I^{\prime}\in{\mathbb{R}}^{E\times E}$ be a diagonal matrix with elements
$I^{\prime}_{e,e}=1$ if $e=\\{i,j\\}$ where $p(i)\neq p(j)$ and
$I^{\prime}_{e,e}=0$ otherwise. Let $A=L^{-}(K_{n},p)-2I^{\prime}$. Let
$e=\\{i,j\\}\in E$. First, assume that $p(i)\neq p(j)$. Then, by Lemma 2.1, we
have

$\displaystyle A\phi_{f}(e)$ $\displaystyle=\sum_{k\neq
i,j}\left(\cos(\theta_{ijk})\phi_{f}(\\{j,k\\})+\cos(\theta_{jik})\phi_{f}(\\{i,k\\})\right)$
$\displaystyle=\sum_{k\neq
i,j}\left(\ell_{jk}\cos(\theta_{ijk})(f_{j}+f_{k})+\ell_{ik}\cos(\theta_{jik})(f_{i}+f_{k})\right)$
$\displaystyle=\sum_{k\neq
i,j}\left(\frac{\ell_{ij}^{2}+\ell_{jk}^{2}-\ell_{ik}^{2}}{2\ell_{ij}}(f_{j}+f_{k})+\frac{\ell_{ij}^{2}+\ell_{ik}^{2}-\ell_{jk}^{2}}{2\ell_{ij}}(f_{i}+f_{k})\right)$
$\displaystyle=\sum_{k\neq i,j}\ell_{ij}f_{k}+\sum_{k\neq
i,j}(f_{i}+f_{j})\frac{\ell_{ij}}{2}+\frac{f_{j}-f_{i}}{2\ell_{ij}}\sum_{k\neq
i,j}(\ell_{jk}^{2}-\ell_{ik}^{2}).$

Note that, since $\sum_{k=1}^{n}f_{k}=0$, we have

$\sum_{k\neq i,j}f_{k}=-(f_{i}+f_{j}).$

Also, since $\|p(x)\|=1$ for all $x\in[n]$, for all $x,y\in[n]$ we have

$\ell_{xy}^{2}=\|p(x)\|^{2}+\|p(y)\|^{2}-2p(x)\cdot p(y)=2-2p(x)\cdot p(y).$

So, since $\sum_{k=1}^{n}p(k)=0$, we obtain

$\sum_{k\neq i,j}(\ell_{jk}^{2}-\ell_{ik}^{2})=2(p(i)-p(j))\cdot\sum_{k\neq
i,j}p(k)\\\ =2(p(j)-p(i))\cdot(p(i)+p(j))=2(\|p(j)\|^{2}-\|p(i)\|^{2})=0.$

Therefore, we obtain

$A\phi_{f}(e)=-(f_{i}+f_{j})\ell_{ij}+\frac{n-2}{2}(f_{i}+f_{j})\ell_{ij}=\frac{n-4}{2}\phi_{f}(e).$

So, $L^{-}(K_{n},p)\phi_{f}(e)=(n/2)\phi_{f}(e)$. Now, assume $p(i)=p(j)$.
Note that $\phi_{f}(e)=(f_{i}+f_{j})\ell_{ij}=0$. Then, since
$\cos(\theta_{ijk})=0$ and $\cos(\theta_{jik})=0$ for all $k\neq i,j$, we
obtain

$A\phi_{f}(e)=\sum_{k\neq
i,j}\left(\cos(\theta_{ijk})\phi_{f}(\\{j,k\\})+\cos(\theta_{jik})\phi_{f}(\\{i,k\\}\right)=0,$

and therefore $L^{-}(K_{n},p)\phi_{f}(e)=0=(n/2)\phi_{f}(e)$. Thus, $\phi_{f}$
is an eigenvector of $L^{-}(K_{n},p)$ with eigenvalue $n/2$.

Finally, we will show that the dimension of the subspace

$U=\left\\{\phi_{f}:\,f\in{\mathbb{R}}^{n},\sum_{i=1}^{n}f_{i}=0\right\\}$

is $n-1$. Indeed, let $W=\\{f\in{\mathbb{R}}^{n}:\,\sum_{i=1}^{n}f_{i}=0\\}$.
Clearly $\dim(W)=n-1$. We have $U=\Phi(W)$, where
$\Phi\in{\mathbb{R}}^{|E|\times n}$ is defined by

$\Phi(e,i)=\begin{cases}\ell_{ij}&\text{ if }e=\\{i,j\\}\text{ for some
}j\in[n],\\\ 0&\text{ otherwise.}\end{cases}$

Let $g\in{\mathbb{R}}^{n}$ such that $\Phi g=0$. Let $i\in[n]$. Since the
image of $p$ is of size at least $3$, there exist $j,k\in[n]$ such that
$p(i),p(j),p(k)$ are pairwise distinct. Then, we have

$\displaystyle 0$ $\displaystyle=(\Phi g)_{\\{i,j\\}}=(g_{i}+g_{j})\ell_{ij},$
$\displaystyle 0$ $\displaystyle=(\Phi g)_{\\{i,k\\}}=(g_{i}+g_{k})\ell_{ik},$
$\displaystyle 0$ $\displaystyle=(\Phi g)_{\\{j,k\\}}=(g_{j}+g_{k})\ell_{jk}.$

We obtain $g_{i}=-g_{j}=g_{k}=-g_{i}$. That is, $g_{i}=0$. Therefore, $g=0$.
Thus, $\Phi$ has linearly independent columns, and so
$\dim(U)=\dim(\Phi(W))=\dim(W)=n-1$, as wanted.

Hence, $n/2$ has multiplicity at least $n-1$ as an eigenvalue of
$L^{-}(K_{n},p)$ (and thus also as an eigenvalue of $L(K_{n},p)$). ∎

We conjecture that for the mappings considered in Proposition 4.2, $n/2$ is
the second largest eigenvalue:

######  Conjecture 4.3.

Let $d\geq 3$, and let $p:[n]\to{\mathbb{R}}^{d}$ such that $\|p(i)\|=1$ for
all $i\in[n]$ and $\sum_{i=1}^{n}p(i)=0$. Assume that the image of $p$ is of
size at least $3$. Then, the second largest eigenvalue of $L(K_{n},p)$ is
$n/2$, and its multiplicity is exactly $n-1$.

In the case $d=2$ we can say more:

######  Proposition 4.4.

Let $p:[n]\to{\mathbb{R}}^{2}$ such that $\|p(i)\|=1$ for all $i\in[n]$ and
$\sum_{i=1}^{n}p(i)=0$. Assume that the $p$ is injective. Then, the spectrum
of $L(K_{n},p)$ is

$\left\\{0^{(3)},\frac{n}{2}^{(2n-4)},n^{(1)}\right\\}.$

Proposition 4.4 extends Zhu’s result [10, Remark 3.4.1], which states that the
same conclusion holds under the more restrictive assumption that $p$ maps
$[n]$ to the roots of unity of order $n$. In particular, this shows that there
are infinitely many embeddings $p:[n]\to{\mathbb{R}}^{2}$ attaining the
supremum $a_{2}(K_{n})=n/2$. For completeness, we include a proof, following
the proof of the special case sketched by Zhu in [10].

###### Proof.

Let $x,y\in{\mathbb{R}}^{2n}$ be defined by

$x=(1,0,1,0,\ldots,1,0)^{t},\ \ y=(0,1,0,1,\ldots,0,1)^{t}.$

For $i\in[n]$, let $p_{x}(i),p_{y}(i)$ be the two coordinates of $p(i)$, and
let

$p^{\perp}(i)=(-p_{y}(i),p_{x}(i))^{t}.$

Define $r\in{\mathbb{R}}^{2n}$ by

$\displaystyle r$
$\displaystyle=(p_{x}^{\perp}(1),p_{y}^{\perp}(1),p_{x}^{\perp}(2),p_{y}^{\perp}(2),\ldots,p_{x}^{\perp}(n),p_{y}^{\perp}(n))^{t}$
$\displaystyle=(-p_{y}(1),p_{x}(1),-p_{y}(2),p_{x}(2),\ldots,-p_{y}(n),p_{x}(n))^{t}.$

It is easy to check (using the fact that $\sum_{i=1}^{n}p(i)=0$) that $x,y,r$
belong to the kernel of $L(K_{n},p)$, and moreover, form an orthogonal set.

We identify the mapping $p$ with the vector

$p=(p_{x}(1),p_{y}(1),\ldots,p_{x}(n),p_{y}(n))^{t}\in{\mathbb{R}}^{2n}.$

By Lemma 4.1, $p$ is an eigenvector of $L(K_{n},p)$ with eigenvalue $n$.

We will show that

$L(K_{n},p)=\frac{n}{2}I+\frac{1}{2}(pp^{t}-xx^{t}-yy^{t}-rr^{t}).$ (1)

Then, it immediately follows that every vector in ${\mathbb{R}}^{2d}$
orthogonal to $p,x,y$ and $r$ is an eigenvector of $L(K_{n},p)$ with
eigenvalue $n/2$, as wanted.

We can write $L(K_{n},p)$ as a $n\times n$ block matrix (see [7, Section
4.4]), formed by $2\times 2$ blocks

$[L(K_{n},p)]_{i,j}=-d_{ij}d_{ij}^{t},$

for $i\neq j\in[n]$, and

$[L(K_{n},p)]_{i,i}=\sum_{j\in[n]\setminus\\{i\\}}d_{ij}d_{ij}^{t}$

for $i\in[n]$. It is then easy to check that proving (1) is equivalent to
showing that, for all $i\in[n]$,

$\sum_{j\in[n]\setminus\\{i\\}}d_{ij}d_{ij}^{t}=\frac{1}{2}p(i)p(i)^{t}-\frac{1}{2}p^{\perp}(i)(p^{\perp}(i))^{t}+\frac{n-1}{2}I,$
(2)

and for all $i\neq j\in[n]$

$-d_{ij}d_{ij}^{t}=\frac{1}{2}p(i)p(j)^{t}-\frac{1}{2}p^{\perp}(i)(p^{\perp}(j))^{t}-\frac{1}{2}I.$
(3)

First, note that (2) follows from (3). Indeed, let $i\in[n]$. By (3), and
using the fact that $\sum_{j\in[n]\setminus\\{i\\}}p(j)=-p(i)$ (and similarly,
$\sum_{j\in[n]\setminus\\{i\\}}p^{\perp}(j)=-p^{\perp}(i)$), we obtain

$\sum_{j\in[n]\setminus\\{i\\}}d_{ij}d_{ij}^{t}=\sum_{j\in[n]\setminus\\{i\\}}\left(\frac{1}{2}I-\frac{1}{2}p(i)p(j)^{t}+\frac{1}{2}p^{\perp}(i)(p^{\perp}(j))^{t}\right)\\\
=\frac{n-1}{2}I-\frac{1}{2}p(i)\left(\sum_{j\in[n]\setminus\\{i\\}}p(j)^{t}\right)+\frac{1}{2}p^{\perp}(i)\left(\sum_{j\in[n]\setminus\\{i\\}}p^{\perp}(j)^{t}\right)\\\
=\frac{n-1}{2}I+\frac{1}{2}p(i)p(i)^{t}-\frac{1}{2}p^{\perp}(i)p^{\perp}(i)^{t}.$

So, we are left to show that (3) holds for all $i\neq j\in[n]$.

Let $i\neq j\in[n]$, and let

$M=d_{ij}d_{ij}^{t}+\frac{1}{2}p(i)p(j)^{t}-\frac{1}{2}p^{\perp}(i)(p^{\perp}(j))^{t}-\frac{1}{2}I.$

We will show that $M=0$. We denote the four coordinates of $M$ by $M_{xx}$,
$M_{xy}$, $M_{yx}$ and $M_{yy}$. Since $\|p(i)\|=\|p(j)\|=1$, we have

$\|p(i)-p(j)\|^{2}=2(1-p(i)\cdot p(j)),$

and therefore

$d_{ij}d_{ij}^{t}=\frac{(p(i)-p(j))(p(i)-p(j))^{t}}{2(1-p(i)\cdot p(j))}.$

Using this and the fact that
$p_{x}(i)^{2}+p_{y}(i)^{2}=p_{x}(j)^{2}+p_{y}(j)^{2}=1$, we obtain

$\displaystyle
M_{xx}=\frac{(p_{x}(i)-p_{x}(j))(p_{x}(i)-p_{x}(j))}{2(1-p_{x}(i)p_{x}(j)-p_{y}(i)p_{y}(j))}+\frac{1}{2}p_{x}(i)p_{x}(j)-\frac{1}{2}p_{y}(i)p_{y}(j)-\frac{1}{2}$
$\displaystyle=\frac{1}{2(1-p_{x}(i)p_{x}(j)-p_{y}(i)p_{y}(j))}\big{(}p_{x}(i)^{2}-2p_{x}(i)p_{x}(j)+p_{x}(j)^{2}+p_{x}(i)p_{x}(j)$
$\displaystyle-
p_{y}(i)p_{y}(j)+p_{y}(i)^{2}p_{y}(j)^{2}-p_{x}(i)^{2}p_{x}(j)^{2}-1+p_{x}(i)p_{x}(j)+p_{y}(i)p_{y}(j)\big{)}$
$\displaystyle=\frac{p_{x}(i)^{2}+p_{x}(j)^{2}-p_{x}(i)^{2}p_{x}(j)^{2}-1+(1-p_{x}(i)^{2})(1-p_{x}(j)^{2})}{2(1-p_{x}(i)p_{x}(j)-p_{y}(i)p_{y}(j))}=0.$

Similarly, $M_{yy}=0$. Finally, we have

$\displaystyle M_{xy}$
$\displaystyle=\frac{(p_{x}(i)-p_{x}(j))(p_{y}(i)-p_{y}(j))}{2(1-p_{x}(i)p_{x}(j)-p_{y}(i)p_{y}(j))}+\frac{1}{2}p_{x}(i)p_{y}(j)+\frac{1}{2}p_{y}(i)p_{x}(j)$
$\displaystyle=\frac{1}{2(1-p_{x}(i)p_{x}(j)-p_{y}(i)p_{y}(j))}\big{(}p_{x}(i)p_{y}(i)-p_{y}(i)p_{x}(j)-p_{x}(i)p_{y}(j)$
$\displaystyle+p_{x}(j)p_{y}(j)+p_{x}(i)p_{y}(j)+p_{y}(i)p_{x}(j)-p_{x}(i)^{2}p_{x}(j)p_{y}(j)$
$\displaystyle-
p_{x}(i)p_{y}(i)p_{x}(j)^{2}-p_{x}(i)p_{y}(i)p_{y}(j)^{2}-p_{y}(i)^{2}p_{x}(j)p_{y}(j)\big{)}$
$\displaystyle=\frac{p_{x}(i)p_{y}(i)+p_{x}(j)p_{y}(j)-p_{x}(j)p_{y}(j)-p_{x}(i)p_{y}(i)}{2(1-p_{x}(i)p_{x}(j)-p_{y}(i)p_{y}(j))}=0,$

and similarly $M_{yx}=0$. So, $M=0$ as wanted. ∎

The following very simple Lemma will be useful for finding the additional
eigenvectors of $L^{-}(T(n,d+1),q^{\triangle})$ and
$L^{-}(T(n,2d),q^{\diamond})$.

######  Lemma 4.5.

Let $G=(V,E)$ and $p:V\to{\mathbb{R}}^{d}$ such that $p(i)\neq p(j)$ for all
$\\{i,j\\}\in E$. Let $L^{-}=L^{-}(G,p)$ and $\phi\in{\mathbb{R}}^{E}$. Let
$\text{supp}(\phi)\subset E$ be the support of $\phi$. Assume that the
following conditions hold:

  1. 1.

For all $e\in E\setminus\operatorname{\text{supp}}(\phi)$,
$\cos(\theta(e,e^{\prime}))=\cos(\theta(e,e^{\prime\prime}))$ for every
$e^{\prime},e^{\prime\prime}\in\operatorname{\text{supp}}(\phi)$ such that
$|e\cap e^{\prime}|=|e\cap e^{\prime\prime}|=1$.

  2. 2.

For all $v\in V$, $\sum_{e\in E:\,v\in e}\phi(e)=0.$

  3. 3.

There is $\lambda\in{\mathbb{R}}$ such that for all
$e\in\operatorname{\text{supp}}(\phi)$

$\sum_{e^{\prime}\in E:\,|e\cap
e^{\prime}|=1}\cos(\theta(e,e^{\prime}))\phi(e^{\prime})=(\lambda-2)\phi(e).$

Then, $\phi$ is an eigenvector of $L^{-}$ with eigenvalue $\lambda$.

###### Proof.

By Lemma 2.1, conditions $(1)$ and $(2)$ imply that $L^{-}\phi(e)=0=\phi(e)$
for every $e\in E\setminus\operatorname{\text{supp}}(\phi)$, and condition
$(3)$ says exactly that $L^{-}\phi(e)=\lambda\phi(e)$ for all
$e\in\operatorname{\text{supp}}(\phi)$. Therefore, we obtain
$L^{-}\phi=\lambda\phi$, as wanted. ∎

###  4.1 The spectrum of $L(T(n,d+1),q^{\triangle})$

See 1.3

Note that for $n=d+1$ the proof below gives a second proof of Theorem 1.1.

###### Proof.

Denote $T(n,d+1)=(V,E)$. First note that, as for all frameworks, $0$ is an
eigenvalue of $L(T(n,d+1),q^{\triangle})$ with multiplicity at least
$\binom{d+1}{2}=d(d+1)/2$.

Moreover, note that $L(T(n,d+1),q^{\triangle})=L(K_{n},q^{\triangle})$. Thus,
by Lemma 4.1 , $n$ is an eigenvalue of $L(T(n,d+1),q^{\triangle})$. Also,
since $\|q^{\triangle}(v)\|=1$ for all $v\in V$ and $\sum_{v\in
V}q^{\triangle}(v)=0$, then by Proposition 4.2, $n/2$ is an eigenvalue of
$L(T(n,d+1),q^{\triangle})$ with multiplicity at least $n-1$.

Therefore, we are left to show that $n/(d+1)$ is an eigenvalue with
multiplicity at least $(d-2)(d+1)/2$ and that $n/(2(d+1))$ is an eigenvalue
with multiplicity at least $(n-d-1)(d-1)$.

Since the non-zero eigenvalues of $L(T(n,d+1),q^{\triangle})$ and
$L^{-}=L^{-}(T(n,d+1),q^{\triangle})$ are the same, we will find the
corresponding eigenvectors for $L^{-}$.

Denote by $V_{1},\ldots,V_{d+1}$ the sides of $T(n,d+1)$. For every $i\neq
j\in[d+1]$, let $E(V_{i},V_{j})$ be the set of edges with one endpoint in
$V_{i}$ and the other in $V_{j}$. Let $i,j,k\in[d+1]$ such that $i\neq j,k$.
Let $v\in V_{i}$, $u\in V_{j}$ and $w\in V_{k}$. Denote by $\theta_{uvw}$ the
angle between $q^{\triangle}(v)-q^{\triangle}(u)$ and
$q^{\triangle}(v)-q^{\triangle}(w)$. Then, we have

$\cos(\theta_{uvw})=\begin{cases}\frac{1}{2}&\text{ if }j\neq k,\\\ 1&\text{
if }j=k.\end{cases}$ (4)

Eigenvalue $\bm{n/(d+1)}$: Assume $d\geq 3$. Let
$i_{1},i_{2},i_{3},i_{4}\in[d+1]$ be four distinct integers. Define
$\Phi_{i_{1},i_{2},i_{3},i_{4}}\in{\mathbb{R}}^{E}$ by

$\Phi_{i_{1},i_{2},i_{3},i_{4}}(e)=\begin{cases}1&\text{ if }e\in
E(V_{i_{1}},V_{i_{2}})\cup E(V_{i_{3}},V_{i_{4}}),\\\ -1&\text{ if }e\in
E(V_{i_{2}},V_{i_{3}})\cup E(V_{i_{1}},V_{i_{4}}),\\\ 0&\text{
otherwise.}\end{cases}$

Note that for every
$e\notin\operatorname{\text{supp}}(\Phi_{i_{1},i_{2},i_{3},i_{4}})$ and every
$e^{\prime}\in\operatorname{\text{supp}}(\Phi_{i_{1},i_{2},i_{3},i_{4}})$ such
that $|e\cap e^{\prime}|=1$, $\cos(\theta(e,e^{\prime}))=1/2$, and that for
all $v\in V$, we have $\sum_{e\in E:\,v\in
e}\Phi_{i_{1},i_{2},i_{3},i_{4}}(e)=0$.

Moreover, let
$e=\\{u,v\\}\in\operatorname{\text{supp}}(\Phi_{i_{1},i_{2},i_{3},i_{4}})$.
Assume $u\in V_{i_{1}}$ and $v\in V_{i_{2}}$ (the other cases are analyzed
similarly). Then, using (4), we obtain

$\sum_{e^{\prime}\in E:\,|e\cap
e^{\prime}|=1}\cos(\theta(e,e^{\prime}))\Phi_{i_{1},i_{2},i_{3},i_{4}}(e^{\prime})=\sum_{w\in
V_{i_{1}}\setminus\\{u\\}}1+\sum_{w\in V_{i_{2}}\setminus\\{v\\}}1\\\
-\sum_{w\in V_{i_{3}}}\frac{1}{2}-\sum_{w\in
V_{i_{4}}}\frac{1}{2}=\frac{n}{d+1}-2=\left(\frac{n}{d+1}-2\right)\Phi_{i_{1},i_{2},i_{3},i_{4}}(e).$

Therefore, by Lemma 4.5, $\Phi_{i_{1},i_{2},i_{3},i_{4}}$ is an eigenvector of
$L^{-}$ with eigenvalue $n/(d+1)$.

Let

$I=\left\\{(1,2,3,k),(1,3,2,k):\,k\in[d+1]\setminus\\{1,2,3\\}\right\\}\\\
\cup\left\\{(2,3,j,k):\,j,k\in[d+1]\setminus\\{1,2,3\\},j<k\right\\},$

and let

$B=\left\\{\Phi_{i_{1},i_{2},i_{3},i_{4}}\right\\}_{(i_{1},i_{2},i_{3},i_{4})\in
I}.$

Note that

$|B|=|I|=2(d-2)+\binom{d-2}{2}=\frac{(d-2)(d+1)}{2}.$

We will show that $B$ is a linearly independent set:

For each $(i_{1},i_{2},i_{3},i_{4})\in I$, let
$\alpha_{i_{1},i_{2},i_{3},i_{4}}\in{\mathbb{R}}$. Assume that

$\sum_{(i_{1},i_{2},i_{3},i_{4})\in
I}\alpha_{i_{1},i_{2},i_{3},i_{4}}\Phi_{i_{1},i_{2},i_{3},i_{4}}=0.$

Let $j,k\in[d+1]\setminus\\{1,2,3\\}$ such that $j<k$. Note that for every
$u\in V_{j}$ and $w\in V_{k}$, $\Phi_{2,3,j,k}$ is the only vector in $B$
containing $\\{u,w\\}$ in its support. Therefore, we must have
$\alpha_{2,3,j,k}=0$.

Now, let $k\in[d+1]\setminus\\{1,2,3\\}$. For every $u\in V_{1}$, $w\in
V_{k}$, the only vectors in $B$ containing $\\{u,w\\}$ in their support are
$\Phi_{1,2,3,k}$ and $\Phi_{1,3,2,k}$. Therefore, we must have
$\alpha_{1,2,3,k}=-\alpha_{1,3,2,k}$. Hence, we obtain a linear relation

$\sum_{k\in[d+1]\setminus\\{1,2,3\\}}\alpha_{1,2,3,k}(\Phi_{1,2,3,k}-\Phi_{1,3,2,k})=0.$

Note that $\Phi_{1,2,3,k}-\Phi_{1,3,2,k}=\Phi_{1,2,k,3}$. So, we obtain

$\sum_{k\in[d+1]\setminus\\{1,2,3\\}}\alpha_{1,2,3,k}\Phi_{1,2,k,3}=0.$

But note that each vector $\Phi_{1,2,k,3}$ contains a unique edge in its
support (for example, any edge $\\{u,w\\}$ where $u\in V_{2}$ and $w\in
V_{k}$). Therefore, $\\{\Phi_{1,2,k,3}\\}_{k\in[d+1]\setminus\\{1,2,3\\}}$ are
independent, and hence $\alpha_{1,2,3,k}=\alpha_{1,3,2,k}=0$ for all
$k\in[d+1]\setminus\\{1,2,3\\}$. Thus, $B$ is linearly independent. So,
$n/(d+1)$ is an eigenvalue of $L^{-}$ with multiplicity at least
$(d-2)(d+1)/2$.

Eigenvalue $\bm{n/(2(d+1))}$:

Let $i,j,k\in[d+1]$ be three distinct indices, and let $u,v\in V_{i}$. Define

$\Psi_{u,v,j,k}=\sum_{w\in V_{j}}(1_{\\{u,w\\}}-1_{\\{v,w\\}})+\sum_{w\in
V_{k}}(1_{\\{v,w\\}}-1_{\\{u,w\\}}).$

Let $e=\\{x,y\\}\notin\operatorname{\text{supp}}(\Psi_{u,v,j,k})$. Assume
$x\in V_{r}$ and $y\in V_{t}$. If $\\{r,t\\}=\\{i,j\\}$ or
$\\{r,t\\}=\\{i,k\\}$, then $\cos(\theta(e,e^{\prime}))=1$ for all
$e^{\prime}\in\operatorname{\text{supp}}(\Psi_{u,v,j,k})$ such that $|e\cap
e^{\prime}|=1$. Otherwise, $\cos(\theta(e,e^{\prime}))=1/2$ for all
$e^{\prime}\in\operatorname{\text{supp}}(\Psi_{u,v,j,k})$ such that $|e\cap
e^{\prime}|=1$.

Also, it is easy to check that for every $w\in V$, $\sum_{e\in E,\\\w\in
e}\Psi_{u,v,j,k}(e)=0$.

Finally, let $e=\\{x,y\\}\in\operatorname{\text{supp}}(\Psi_{u,v,j,k})$.
Assume $x=u$ and $y\in V_{j}$ (the other cases are similar). Then, by (4), we
have

$\displaystyle\sum_{e^{\prime}\in E:\,|e\cap
e^{\prime}|=1}\cos(\theta(e,e^{\prime}))\Psi_{u,v,j,k}(e^{\prime})$
$\displaystyle=\sum_{w\in V_{j}\setminus\\{y\\}}\cos(\theta_{yuw})-\sum_{w\in
V_{k}}\cos(\theta_{yuw})-\cos(\theta_{uyv})$ $\displaystyle=\sum_{w\in
V_{j}\setminus\\{y\\}}1-\sum_{w\in
V_{k}}\frac{1}{2}-1=\frac{n}{2(d+1)}-2=\left(\frac{n}{2(d+1)}-2\right)\Psi_{u,v,j,k}(e).$

Therefore, by Lemma 4.5, $\Psi_{u,v,j,k}$ is an eigenvector of $L^{-}$ with
eigenvalue $n/(2(d+1))$.

For every $i\in[d+1]$, fix some $j(i)\in[d+1]\setminus\\{i\\}$ and $u_{i}\in
V_{i}$, and let

$J_{i}=\left\\{(u_{i},v,j(i),k):\,v\in
V_{i}\setminus\\{u_{i}\\},\,k\in[d+1]\setminus\\{i,j(i)\\}\right\\}$

and

$B_{i}=\left\\{\Psi_{u,v,j,k}\right\\}_{(u,v,j,k)\in J_{i}}.$

Let $B=\cup_{i=1}^{d+1}B_{i}$. Note that

$|B|=\sum_{i=1}^{d+1}|J_{i}|=(d+1)\left(\frac{n}{d+1}-1\right)(d-1)=(n-d-1)(d-1).$

We will show that $B$ is a linearly independent set. Let $i\neq
i^{\prime}\in[d+1]$ and let $(u_{i},v,j,k)\in J_{i}$ and
$(u_{i^{\prime}},v^{\prime},j^{\prime},k^{\prime})\in J_{i^{\prime}}$. We will
show that $\Psi_{u_{i},v,j,k}$ and
$\Psi_{u_{i^{\prime}},v^{\prime},j^{\prime},k^{\prime}}$ are orthogonal.
Indeed, the supports of the two vectors are disjoint unless
$i^{\prime}\in\\{j,k\\}$ and $i\in\\{j^{\prime},k^{\prime}\\}$. In this case,
the intersection of the two supports consists of the four edges
$\\{u_{i},u_{i^{\prime}}\\},\\{u_{i},v^{\prime}\\},\\{v,u_{i^{\prime}}\\},\\{v,v^{\prime}\\}$,
and it is easy to check that we have
$\Psi_{u_{i},v,j,k}\cdot\Psi_{u_{i^{\prime}},v^{\prime},j^{\prime},k^{\prime}}=0$.

Therefore, it is enough to check that for each $i\in[d+1]$, $B_{i}$ is
linearly independent. But this follows from the fact that for every
$(u_{i},v,j(i),k)\in J_{i}$, there is a unique edge in the support of
$\Psi_{u_{i},v,j(i),k}$ (any edge of the form $\\{v,w\\}$ where $w\in V_{k}$).
So $B$ is linearly independent, and therefore $n/(2(d+1))$ is an eigenvector
of $L^{-}$ with multiplicity at least $(n-d-1)(d-1)$. ∎

  * Remark.

In [7], a lower bound
$\lambda_{\binom{d+1}{2}+1}(L(T(n,d+1),q^{\triangle}))\geq\frac{2d^{2}+d}{2(d+1)^{3}}n$
(for $n$ divisible by $d+1$) was stated, in contradiction to Theorem 1.3.
After fixing a typo in [7, Lemma 5.4], the corrected lower bound obtained in
[7] is

$\lambda_{\binom{d+1}{2}+1}(L(T(n,d+1),q^{\triangle}))\geq\frac{dn}{2(d+1)^{2}}.$

From Theorem 1.3 it follows that in fact, for $n$ divisible by $d+1$,

$\lambda_{\binom{d+1}{2}+1}(L(T(n,d+1),q^{\triangle}))=\frac{n}{2(d+1)}.$

###  4.2 The spectrum of $L(T(n,2d),q^{\diamond})$

See 1.4

###### Proof.

Denote $T(n,2d)=(V,E)$. First, note that, as for all frameworks, $0$ is an
eigenvalue of $L(T(n,2d),q^{\diamond})$ with multiplicity at least $d(d+1)/2$.

Note that $L(T(n,2d),q^{\diamond})=L(K_{n},q^{\diamond})$. Thus, by Lemma 4.1
, $n$ is an eigenvalue of $L(T(n,2d),q^{\diamond})$. Also, since
$\|q^{\diamond}(v)\|=1$ for all $v\in V$ and $\sum_{v\in V}q^{\diamond}(v)=0$,
then by Proposition 4.2, $n/2$ is an eigenvalue of $L(T(n,2d),q^{\diamond})$
with multiplicity at least $n-1$.

Therefore, we are left to show that $n/d$ is an eigenvalue with multiplicity
at least $d(d-1)/2$ and that $n/(2d)$ is an eigenvalue with multiplicity at
least $n(d-1)-d^{2}$.

Since the non-zero eigenvalues of $L(T(n,2d),q^{\diamond})$ and
$L^{-}=L^{-}(T(n,2d),q^{\diamond})$ are the same, we will find the
corresponding eigenvectors for $L^{-}$.

Denote the parts of $T(n,2d)$ by
$V_{1,1},V_{1,-1},V_{2,1},V_{2,-1}\ldots,V_{d,1},V_{d,-1}$ where, for
$i\in[d]$ and $s\in\\{1,-1\\}$, $q^{\diamond}(V_{i,s})$ is the singleton set
consisting of the vector $se_{i}$, where $e_{i}$ is the $i$-th standard vector
in ${\mathbb{R}}^{d}$. For every $i,j\in[d]$ and $x,y\in\\{1,-1\\}$, let
$E(V_{i,x},V_{j,y})$ be the set of edges with one endpoint in $V_{i,x}$ and
the other in $V_{j,y}$.

Let $u\in V_{i,x}$ and $v\in V_{j,y}$, where $i\neq j\in[d]$ and
$x,y\in\\{1,-1\\}$. Let $w\neq u,v$, and assume $w\in V_{k,z}$ for $k\in[d]$
and $z\in\\{1,-1\\}$.

Let $\theta_{vuw}$ be the angle between $q^{\diamond}(u)-q^{\diamond}(v)$ and
$q^{\diamond}(u)-q^{\diamond}(w)$. Then,

$\cos(\theta_{vuw})=\begin{cases}\frac{1}{2}&\text{ if }k\neq i,j,\\\
\frac{1}{\sqrt{2}}&\text{ if }k=i,z=-x,\\\ 1&\text{ if }k=j,z=y,\\\ 0&\text{
otherwise.}\end{cases}$ (5)

Eigenvalue $\bm{n/d}$: Let $i<j\in[d]$. Let $\phi_{ij}\in{\mathbb{R}}^{E}$ be
defined by

$\phi_{ij}(e)=\begin{cases}1&\text{ if }e\in E(V_{i,1},V_{j,1})\cup
E(V_{i,-1},V_{j,-1}),\\\ -1&\text{ if }e\in E(V_{i,-1},V_{j,1})\cup
E(V_{i,1},V_{j,-1}),\\\ 0&\text{ otherwise}.\end{cases}$

Let $e\notin\operatorname{\text{supp}}(\phi_{ij})$. If $e\in
E(V_{i,1},V_{i,-1})\cup E(V_{j,1},V_{j,-1})$, then
$\cos(\theta(e,e^{\prime}))=1/\sqrt{2}$ for every
$e^{\prime}\in\operatorname{\text{supp}}(\phi_{ij})$ such that $|e\cap
e^{\prime}|=1$. If $e\in E(V_{k,1},V_{k,-1})$ for some
$k\in[d]\setminus\\{i,j\\}$, then there are no edges
$e^{\prime}\in\operatorname{\text{supp}}(\phi_{ij})$ such that $|e\cap
e^{\prime}|=1$. If $e\notin\cup_{k=1}^{d}E(V_{k,1},V_{k,-1})$, then
$\cos(\theta(e,e^{\prime}))=1/2$ for every
$e^{\prime}\in\operatorname{\text{supp}}(\phi_{ij})$ such that $|e\cap
e^{\prime}|=1$.

Also, note that for all $v\in V$, we have $\sum_{e\in E:\,v\in
e}\phi_{ij}(e)=0$.

Moreover, let $e=\\{u,v\\}\in\operatorname{\text{supp}}(\phi_{ij})$. Assume
$u\in V_{i,1}$ and $v\in V_{j,1}$ (the other cases are analyzed similarly).
Then, using (5), we obtain

$\displaystyle\sum_{e^{\prime}\in E:\,|e\cap
e^{\prime}|=1}\cos(\theta(e,e^{\prime}))\phi_{ij}(e^{\prime})$
$\displaystyle=\sum_{w\in V_{i,1}\setminus\\{u\\}}1+\sum_{w\in
V_{j,1}\setminus\\{v\\}}1$
$\displaystyle=\frac{n}{d}-2=\left(\frac{n}{d}-2\right)\phi_{ij}(e).$

So, by Lemma 4.5, $\phi_{ij}$ is an eigenvector of $L^{-}$ with eigenvalue
$n/d$. Since the supports of the vectors $\\{\phi_{ij}\\}_{i<j\in[d]}$ are
pairwise disjoint, they form a linearly independent set. Thus, $n/d$ is an
eigenvalue of $L^{-}$ with multiplicity at least $d(d-1)/2$.

Eigenvalue $\bm{n/(2d)}$: Let $i\neq j\in[d]$. Define
$\psi_{ij}\in{\mathbb{R}}^{E}$ by

$\psi_{ij}(e)=\begin{cases}1&\text{ if }e\in E(V_{i,1},V_{j,1})\cup
E(V_{i,-1},V_{j,1}),\\\ -1&\text{ if }e\in E(V_{i,1},V_{j,-1})\cup
E(V_{i,-1},V_{j,-1}),\\\ 0&\text{ otherwise.}\end{cases}$

For $k\neq i,j$, let $\Psi_{ijk}=\psi_{ij}-\psi_{kj}$.

Let $e\notin\operatorname{\text{supp}}(\Psi_{ijk})$. If
$e\in\cup_{t=1}^{d}E(V_{t,1},V_{t,-1})$, then
$\cos(\theta(e,e^{\prime}))=1/\sqrt{2}$ for every
$e^{\prime}\in\operatorname{\text{supp}}(\Psi_{ijk})$ such that $|e\cap
e^{\prime}|=1$ (note that if $t\neq i,j,k$ then there are no such edges
$e^{\prime}$). If $e\notin\cup_{t=1}^{d}E(V_{t,1},V_{t,-1})$, then
$\cos(\theta(e,e^{\prime}))=1/2$ for every
$e^{\prime}\in\operatorname{\text{supp}}(\Psi_{ijk})$ such that $|e\cap
e^{\prime}|=1$.

Also, note that for all $v\in V$, we have $\sum_{e\in E:\,v\in
e}\Psi_{ijk}(e)=0$.

Moreover, let $e=\\{u,v\\}\in\operatorname{\text{supp}}(\Psi_{ijk})$. Assume
$u\in V_{i,1}$ and $v\in V_{j,1}$ (the other cases are analyzed similarly).
Then, using (5), we obtain

$\displaystyle\sum_{e^{\prime}\in E:\,|e\cap
e^{\prime}|=1}\cos(\theta(e,e^{\prime}))\Psi_{ijk}(e^{\prime})$
$\displaystyle=\sum_{w\in V_{i,1}\setminus\\{u\\}}1+\sum_{w\in
V_{j,1}\setminus\\{v\\}}1-\sum_{w\in V_{k,1}\cup V_{k,-1}}\frac{1}{2}$
$\displaystyle=\frac{n}{2d}-2=\left(\frac{n}{2d}-2\right)\Psi_{ijk}(e).$

Therefore, by Lemma 4.5, $\Psi_{ijk}$ is an eigenvector of $L^{-}$ with
eigenvalue $n/(2d)$.

For each $j\in[d]$, fix $i(j)\in[d]\setminus\\{j\\}$. Let

$I_{j}=\\{(i(j),j,k):\,k\in[d]\setminus\\{j,i(j)\\}\\}$

and $I=\cup_{j\in[d]}I_{j}$. Note that $|I|=d(d-2)$. We will show that
$\\{\Psi_{ijk}\\}_{(i,j,k)\in I}$ is a linearly independent set.

First, note that the vectors $\\{\psi_{ij}\\}_{i\neq j\in[d]}$ form an
orthogonal set. Indeed, let $i,j,k,s\in[d]$ such that $i\neq j$ and $k\neq s$.
If $\\{i,j\\}\neq\\{k,s\\}$ then $\psi_{ij}$ and $\psi_{ks}$ have disjoint
supports, and therefore $\psi_{ij}\cdot\psi_{ks}=0$. Otherwise, if $i=s$ and
$j=k$ we obtain

$\psi_{ij}\cdot\psi_{ji}=\sum_{e\in E(V_{i,1},V_{j,1})}1\cdot 1+\sum_{e\in
E(V_{i,1},V_{j,-1})}(-1)\cdot 1\\\ +\sum_{e\in
E(V_{i,-1},V_{j,1})}1\cdot(-1)+\sum_{e\in
E(V_{i,-1},V_{j,-1})}(-1)\cdot(-1)=0.$

Hence, for $\\{i,j,k\\}\in\binom{[d]}{3}$ and
$\\{i^{\prime},j^{\prime},k^{\prime}\\}\in\binom{[d]}{3}$ such that $j\neq
j^{\prime}$, we have $\Psi_{ijk}\cdot\Psi_{i^{\prime}j^{\prime}k^{\prime}}=0$.
Therefore, we are left to show that for all $j\in[d]$,
$\\{\Psi_{ijk}\\}_{(i,j,k)\in I_{j}}$ is linearly independent. But this
follows from the fact that for every $(i,j,k)\in I_{j}$ there is an edge in
the support of $\Psi_{ijk}$ that is unique to $\Psi_{ijk}$ (for example, any
edge $\\{u,v\\}$ where $u\in V_{j,1}$ and $v\in V_{k,1}$).

We now complete the set $\\{\Psi_{ijk}\\}_{(i,j,k)\in I}$ to an eigenbasis of
$n/2d$. Let $i\neq j\in[d]$ and $x\in\\{1,-1\\}$. Let $u\neq v\in V_{i,x}$.

Define $f_{j}^{u,v}\in{\mathbb{R}}^{E}$ by

$f_{j}^{u,v}=\sum_{w\in V_{j,1}}(1_{\\{u,w\\}}-1_{\\{v,w\\}})+\sum_{w\in
V_{j,-1}}(-1_{\\{u,w\\}}+1_{\\{v,w\\}}).$

Let $e\notin\operatorname{\text{supp}}(f_{j}^{u,v})$. If $e\in
E(V_{i,x},V_{j,1})\cup E(V_{i,x},V_{j,-1})$, then
$\cos(\theta(e,e^{\prime}))=1$ for all
$e^{\prime}\in\operatorname{\text{supp}}(f_{j}^{u,v})$ such that $|e\cap
e^{\prime}|=1$. If $e\in E(V_{i,1},V_{i,-1})\cup E(V_{j,1},V_{j,-1})$, then
$\cos(\theta(e,e^{\prime}))=1/\sqrt{2}$ for all
$e^{\prime}\in\operatorname{\text{supp}}(f_{j}^{u,v})$ such that $|e\cap
e^{\prime}|=1$. If $e\in E(V_{i,-x},V_{j,1})\cup E(V_{i,-x},V_{j,-1})$, then
$\cos(\theta(e,e^{\prime}))=0$ for all
$e^{\prime}\in\operatorname{\text{supp}}(f_{j}^{u,v})$ such that $|e\cap
e^{\prime}|=1$. Otherwise, $\cos(\theta(e,e^{\prime}))=1/2$ for all
$e^{\prime}\in\operatorname{\text{supp}}(f_{j}^{u,v})$ such that $|e\cap
e^{\prime}|=1$.

In addition, it is easy to check that for every $w\in V$, $\sum_{e\in
E,\\\w\in e}f^{u,v}_{j}(e)=0$.

Finally, let $e=\\{a,b\\}\in\operatorname{\text{supp}}(f_{j}^{u,v})$. Assume
$a=u$ and $b\in V_{j,1}$ (the other cases are similar). Then, by (5), we have

$\displaystyle\sum_{e^{\prime}\in E:\,|e\cap
e^{\prime}|=1}\cos(\theta(e,e^{\prime}))f_{j}^{u,v}(e^{\prime})$
$\displaystyle=\sum_{w\in
V_{j,1}\setminus\\{b\\}}\cos(\theta_{buw})-\sum_{w\in
V_{j,-1}}\cos(\theta_{buw})-\cos(\theta_{ubv})$ $\displaystyle=\sum_{w\in
V_{j}\setminus\\{b\\}}1-\sum_{w\in
V_{k}}0-1=\frac{n}{2d}-2=\left(\frac{n}{2d}-2\right)f_{j}^{u,v}(e).$

Therefore, by Lemma 4.5, $f_{j}^{u,v}$ is an eigenvector of $L^{-}$ with
eigenvalue $n/(2d)$.

For each $i\in[d]$ and $x\in\\{1,-1\\}$, fix some $u(i,x)\in V_{i,x}$. For
$j\in[d]\setminus\\{i\\}$, let

$J_{i,x,j}=\\{(u(i,x),v,j):\,u(i,x)\neq v\in V_{i,x}\\}.$

and let
$J=\cup_{i\in[d]}\cup_{x\in\\{1,-1\\}}\cup_{j\in[d]\setminus\\{i\\}}J_{i,x,j}$.
Note that $|J|=2d(d-1)(n/(2d)-1)$.

We will show that $\\{f_{j}^{u,v}\\}_{(u,v,j)\in J}$ are linearly independent.

Let $u\neq v\in V_{i,x}$ and $u^{\prime}\neq v^{\prime}\in
V_{i^{\prime},x^{\prime}}$. Let $j\neq i$ and $j^{\prime}\neq i^{\prime}$.
Assume $(i,x,j)\neq(i^{\prime},x^{\prime},j^{\prime})$. We will show that
$f_{j}^{u,v}$ and $f_{j^{\prime}}^{u^{\prime},v^{\prime}}$ are orthogonal.
Indeed, the supports of the two vectors are disjoint unless $i^{\prime}=j$ and
$j^{\prime}=i$. But it is easy to check that also in this case we have
$f_{j}^{u,v}\cdot f_{j^{\prime}}^{u^{\prime},v^{\prime}}=0$.

Therefore, it is enough to show that for every $i\neq j\in[d]$ and
$x\in\\{1,-1\\}$, $\\{f_{j}^{u,v}\\}_{(u,v,j)\in J_{i,x,j}}$ is linearly
independent. But again, this follows from the fact that for every $(u,v,j)\in
J_{i,x,j}$ there is an edge in the support of $f_{j}^{u,v}$ that is unique to
it (for example, the edge $\\{v,w\\}$ for any $w\in V_{j,1}$).

Finally, note that $\psi_{ij}\cdot f_{k}^{u,v}=0$ for every $i\neq j\in[d]$
and $(u,v,k)\in J$. Therefore, $\Psi_{ijk}\cdot f_{m}^{u,v}=0$ for all
$(i,j,k)\in I$ and $(u,v,m)\in J$. Thus, the eigenvectors
$\\{\Psi_{ijk}\\}_{(i,j,k)\in I}\cup\\{f_{j}^{u,v}\\}_{(u,v,j)\in J}$ form a
linearly independent set.

So, $n/(2d)$ is an eigenvalue of $L^{-}$ with multiplicity at least

$d(d-2)+2d(d-1)(n/(2d)-1)=n(d-1)-d^{2},$

as wanted. ∎

It was shown in [7, Lemma 4.5] that the removal of a vertex reduces the
$d$-dimensional algebraic connectivity of a graph by at most $1$. Hence, as an
immediate consequence of Theorem 1.4, we obtain:

See 1.5

##  5 The $n$ largest eigenvalues of the complete graph $K_{n}$

We proceed to establish a lower bound for the sum of the largest $n$
eigenvalues of $L(K_{n},p)$ for all embeddings $p:[n]\to{\mathbb{R}}^{d}$. As
a corollary, we derive an upper bound for $a_{d}(K_{n})$.

######  Lemma 5.1.

Let $p:[n]\to{\mathbb{R}}^{d}$ be injective. Then,

$\sum_{j=(d-1)n+1}^{dn}\lambda_{j}(L(K_{n},p))\geq\frac{n^{2}}{3}+n\,.$

See 1.6

###### Proof of Theorem 1.6.

Let $p:V\to{\mathbb{R}}^{d}$ be injective. We compute the trace of
$L(K_{n},p)$ in two ways. By Lemma 2.1, all the diagonal entries of
$L^{-}(K_{n},p)$ equal $2$, since $p$ is injective. Thus, we have

$\mathrm{Tr}(L(K_{n},p))=\mathrm{Tr}(L^{-}(K_{n},p))=2\binom{n}{2}=n^{2}-n\,.$
(6)

On the other hand, let $\lambda=\lambda_{\binom{d+1}{2}+1}(L(K_{n},p))$. We
deduce from Lemma 5.1 that

$\displaystyle\mathrm{Tr}(L(K_{n},p))=$
$\displaystyle~{}\sum_{j=1}^{dn}\lambda_{j}(L(K_{n},p))$ $\displaystyle=$
$\displaystyle\sum_{j=\binom{d+1}{2}+1}^{(d-1)n}\lambda_{j}(L(K_{n},p))+\sum_{j=(d-1)n+1}^{dn}\lambda_{j}(L(K_{n},p))$
$\displaystyle\geq$
$\displaystyle~{}\left((d-1)n-\binom{d+1}{2}\right)\lambda+\frac{n^{2}}{3}+n.$
(7)

By combining (6) and (7), we derive that

$\lambda\leq\frac{2n^{2}/3-2n}{(d-1)n-\binom{d+1}{2}}.$

Finally, we have

$\displaystyle\frac{2n^{2}/3-2n}{(d-1)n-\binom{d+1}{2}}-\frac{2n}{3(d-1)}=\frac{n(d(d+1)-6(d-1))}{3(d-1)\left((d-1)n-\binom{d+1}{2}\right)}$
$\displaystyle\leq\frac{n(d(d+1)-6(d-1))}{3n(d-1)^{2}}=\frac{d(d+1)-6(d-1)}{3(d-1)^{2}}\leq\frac{1}{3}.$

Therefore, we obtain

$\lambda\leq\frac{2n}{3(d-1)}+\frac{1}{3}.$

Thus, by Lemma 2.4, we obtain

$a_{d}(K_{n})\leq\frac{2n}{3(d-1)}+\frac{1}{3},$

as claimed. ∎

To prove Lemma 5.1 we will need the following theorem due to Ky Fan:

######  Theorem 5.2 (Ky Fan [4, Thm. 1]).

Let $A\in{\mathbb{R}}^{m\times m}$ be a symmetric matrix, and let
$\mu_{1}\geq\mu_{2}\geq\cdots\geq\mu_{m}$ be its eigenvalues. Then, for every
$k\leq m$,

$\sum_{i=1}^{k}\mu_{i}=\max\left\\{\text{Tr}(AP):\,P\in\mathcal{P}_{k}\right\\}$

where $\mathcal{P}_{k}$ consists of all orthogonal projection matrices into
$k$-dimensional subspaces of ${\mathbb{R}}^{m}$.

###### Proof of Lemma 5.1.

Let $E=\binom{[n]}{2}$. For $i\in[n]$, let $v^{(i)}\in{\mathbb{R}}^{E}$ be
defined by

$v^{(i)}_{e}=\begin{cases}1&\text{ if }i\in e,\\\ 0&\text{
otherwise.}\end{cases}$

We claim that the $E\times E$ symmetric matrix $P$ defined by

$P_{e,e^{\prime}}=\left\\{\begin{matrix}\frac{2}{n-1}&e=e^{\prime}\\\\[6.0pt]
\frac{n-3}{(n-1)(n-2)}&|e\cap e^{\prime}|=1\\\\[6.0pt]
\frac{-1}{\binom{n-1}{2}}&e\cap e^{\prime}=\emptyset\end{matrix}\right.\,,$

is the orthogonal projection on the subspace spanned by
$\\{v^{(i)}:\,i\in[n]\\}$. Indeed, if $e=\\{i,j\\}$, then the $e$-th row of
$P$ is equal to

$P_{e,\cdot}=\frac{1}{n-1}\left(v^{(i)}+v^{(j)}-\frac{1}{n-2}\sum_{k\neq
i,j}v^{(k)}\right)\,.$

Therefore, $Pw=0$ for every $w$ that is orthogonal to all the vectors
$v^{(i)},i\in[n]$. In addition, a straightforward computation shows that
$Pv^{(i)}=v^{(i)}$ for every $i\in[n]$ since $(v^{(i)})^{t}v^{(j)}=1$ if
$i\neq j$ and $\|v^{(i)}\|^{2}=n-1$.

We apply theorem 5.2 for $L^{-}:=L^{-}(K_{n},p)$ and $P$ to find that

$\displaystyle\sum_{i=(d-1)n+1}^{dn}\lambda_{i}(L(K_{n},p))=\sum_{i=\binom{n-1}{2}}^{\binom{n}{2}}\lambda_{i}(L^{-})\geq$
$\displaystyle~{}\mathrm{Tr}(L^{-}P)=\sum_{e,e^{\prime}}P_{e,e^{\prime}}L^{-}_{e,e^{\prime}}.$

Recall the precise description of $L^{-}$ in Lemma 2.1. Since $p$ is
injective, the contribution of the diagonal terms $e=e^{\prime}$ to the
summation is

$\sum_{e\in E}P_{e,e}L^{-}_{e,e}=\binom{n}{2}\cdot\frac{2}{n-1}\cdot 2=2n\,.$
(8)

In addition, since $L^{-}_{e,e^{\prime}}=0$ if $e\cap e^{\prime}=\emptyset$,
the contribution of the non-diagonal terms is

$\sum_{e\neq
e^{\prime}}P_{e,e^{\prime}}L^{-}_{e,e^{\prime}}=\sum_{i=1}^{n}\sum_{j\neq
i}\sum_{j^{\prime}\neq
i,j}\frac{n-3}{(n-1)(n-2)}L^{-}_{\\{i,j\\},\\{i,j^{\prime}\\}}\,.$ (9)

Note that all the $\binom{n}{3}$ triples $\\{i,j,j^{\prime}\\}$ of vertices
satisfy

$L^{-}_{\\{i,j\\},\\{i,j^{\prime}\\}}+L^{-}_{\\{j,i\\},\\{j,j^{\prime}\\}}+L^{-}_{\\{j^{\prime},i\\},\\{j^{\prime},j\\}}\geq
1.$

Indeed, since $p$ is injective, this is the sum of the cosines of the angles
in the (possibly flat) triangle $p(i),p(j),p(j^{\prime})$— which is bounded
from below by $1$. In addition, note that each term
$L^{-}_{\\{i,j\\},\\{i,j^{\prime}\\}}$ appears twice in (9) since
$j,j^{\prime}$ are ordered. Consequently,

$\sum_{e\neq
e^{\prime}}P_{e,e^{\prime}}L^{-}_{e,e^{\prime}}\geq\binom{n}{3}\cdot\frac{2(n-3)}{(n-1)(n-2)}=\frac{n^{2}}{3}-n\,.$
(10)

Joining (8) and (10), we obtain

$\sum_{i=(d-1)n+1}^{dn}\lambda_{i}(L(K_{n},p))\geq\frac{n^{2}}{3}+n\,.$

∎

We believe that the bound in Lemma 5.1 can be improved:

######  Conjecture 5.3.

Let $p:[n]\to{\mathbb{R}}^{d}$ be injective. Then, the sum of the $n$ largest
eigenvalues of $L(K_{n},p)$ is at least $\frac{n(n+1)}{2}$.

Recall that, by Lemma 4.1, for every non-constant $p:[n]\to{\mathbb{R}}^{d}$,
the largest eigenvalue of $L(K_{n},p)$ is $n$. Thus, Conjecture 5.3 is
equivalent to saying that the average of the next $n-1$ largest eigenvalues is
at least $n/2$.

##  6 Concluding remarks

###  6.1 Complete graphs

We conjecture that the lower bound of Theorem 1.5 is essentially tight:

######  Conjecture 6.1.

Let $n\geq 2d$. Then,

$\left\lfloor\frac{n}{2d}\right\rfloor\leq a_{d}(K_{n})\leq\frac{n}{2d}.$

###  6.2 Regular graphs

From some computer calculations, it seems possible that the following
generalization of [7, Conj. 2] holds:

######  Conjecture 6.2.

For $d\geq 1$,

$\lim_{n\to\infty}\max\\{a_{d}(G):\,G\text{ is $2d$-regular on $n$
vertices}\\}=0.$

###  6.3 Repeated points

In line with our analysis of the minimal nontrivial eigenvalue of $L(G,p)$,
where $G$ is the Turán graph $T(n,d+1)$ (resp. $T(n,2d)$) and
$p=q^{\triangle}$ (resp. $p=q^{\diamond}$) in Theorem 1.3 and Theorem 1.4, we
conjecture the following general phenomena regarding the effect of repeated
points on the spectral gap.

For an injective $p:[n]\to{\mathbb{R}}^{d}$ and graph $G$ with vertex set
$[n]$, denote by $\lambda(G,p)=\lambda_{\binom{d+1}{2}+1}(L(G,p))$. For $k\geq
1$ let $p^{k}:[kn]\to{\mathbb{R}}^{d}$ be a mapping such that
$|(p^{k})^{-1}(p(v))|=k$ for every $v\in[n]$. In words, we put $k$ vertices on
each point of the image of $p$.

######  Conjecture 6.3.

For every injective mapping $p:[n]\to{\mathbb{R}}^{d}$ and every $k\geq 2$,

$\lambda(K_{kn},p^{k})=\frac{k}{2}\lambda(K_{2n},p^{2}).$

We remark that for $k=1$ the assertion fails, as demonstrated by the regular
simplex embedding $p^{\triangle}$.

## References

  * [1] K. Aryankia and R. R. Selmic.  Spectral properties of the normalized rigidity matrix for triangular formations.  IEEE Control Systems Letters, 6:1154–1159, 2021.
  * [2] L. Asimow and B. Roth.  The rigidity of graphs.  Trans. Amer. Math. Soc., 245:279–289, 1978.
  * [3] A. E. Brouwer and W. H. Haemers.  Spectra of graphs.  Springer Science & Business Media, 2011.
  * [4] K. Fan.  On a theorem of Weyl concerning eigenvalues of linear transformations I.  Proceedings of the National Academy of Sciences of the United States of America, 35(11):652, 1949.
  * [5] M. Fiedler.  Algebraic connectivity of graphs.  Czechoslovak mathematical journal, 23(2):298–305, 1973.
  * [6] C. Godsil and G. F. Royle.  Algebraic graph theory, volume 207.  Springer Science & Business Media, 2001.
  * [7] T. Jordán and S. Tanigawa.  Rigidity of random subgraphs and eigenvalues of stiffness matrices.  2020\.
  * [8] F. J. Király and L. Theran.  Coherence and sufficient sampling densities for reconstruction in compressed sensing.  arXiv preprint arXiv:1302.2767, 2013.
  * [9] A. Lew, E. Nevo, Y. Peled, and O. E. Raz.  Sharp threshold for rigidity of random graphs.  arXiv preprint arXiv:2202.09917, 2022.
  * [10] G. Zhu.  Quantitative analysis of multi-agent formations: Theory and applications.  PhD thesis, Purdue University, 2013.
  * [11] G. Zhu and J. Hu.  Stiffness matrix and quantitative measure of formation rigidity.  In Proceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference, pages 3057–3062. IEEE, 2009.


(close to 1.0), which suffices for practical applications. We cite this
example to show that, even when exact values are computationally intractable
to derive, certain assumptions can be made, which allow us to derive estimates
of the true underlying complexity with high confidence. In another example,
the Polycraft World domain illustrates interesting considerations for
calculating complexity in large-scale 3D environments with many object types.
Specifically, even in worlds where the number of potential environment states
is astronomical due to scale, the amount of information needed to define a
specific instance of the world state can still be quite small.

Similar to other domains, the CartPole domains measure their dimensionality
based on an enumeration of the dimensions of the state space and their scales.
In terms of sparsity, the CartPole domains allow for a more analytical
approach based on the ratio of successful action sequences to the total
possible action sequences, which are both computable in CartPole, but not in
more complicated domains like Monopoly or Polycraft World. The diversity
measure is where CartPole deviates most from the other domains. CartPole uses
an entropy-based diversity measure like other domains, but the entropy is
calculated based on observable sequences of features and actions, not the
possible sequences. This calculation does require interaction with the game,
but the interaction can be random and not involve a particular agent, thus
preserving the intrinsic property of the diversity measure. Combined with the
approaches taken in other domains, the overall framework for computing
dimensionality, sparsity, and diversity applies to action-based and
classification-based domains, and in cases where either an analytical or
empirical approach is warranted.

Ultimately, deriving values for such measures in a systematic way enables a
robust and rich set of comparisons. To take just one example, if we compare
MNIST and CIFAR-10, the MNIST dataset has very low normalized entropy, whereas
CIFAR-10 has very high normalized entropy (the former is skewed, whereas the
latter is more similar to the uniform distribution). For both cases, however,
the entropy reflects both low diversity and low uncertainty, because the
highest diversity is achieved when the normalized entropy is close to 0.5.

##  7 Conclusion

Understanding the complexity of domains in a systematic and domain-independent
manner is an important problem in the Artificial Intelligence community.
Understanding domain complexity is especially relevant today, when the focus
has shifted from building task-specific AI designed for rigidly defined
problem, to the development of OWL agents and algorithms that can work across
domains, or that are able to handle ‘novelties’ and other unexpected events in
a single open-world domain. Returning to our example of the AUV from Wilson et
al. (2014), we can express the difficulty that was encountered when
transitioning from the simulator domain to the real-world domain in terms of
the components of our complexity levels. The real world had higher
dimensionality with regard to the environment space complexity and greater
diversity with respect to the perception-task solution space (where noise and
environmental factors meant a diverse collection of different sensor readings
might represent a single system state). These unexpected increases in domain
complexity, as compared to the simulator domain, caused the AI to behave
pathologically, constantly replanning in response to the discrepancies between
its perception of the real world and its less complex internal state space.
Once the complexity of the deployment domain was understood, a bounding-box
technique was introduced, enabling the robot to operate successfully in the
open ocean.

The goal of this article was to present a blueprint, and set of implementable
measures, for systematically understanding domain complexity. We argued that
domain complexity, especially in the context of AI-relevant domains, can be
viewed from two aspects: intrinsic and extrinsic. We also proposed three
categories of measures (dimensionality, sparsity and diversity) and applied
them to a broad range of case studies across action, perception and data
science domains.

As the systematic understanding of domain complexity remains a relatively new
problem in AI, many important questions (both empirical and theoretical)
remain to be answered by future work. In the next section, we close the
article by enumerating several promising questions.

##  8 Next Steps

This paper is an early attempt at synthesizing several measures and aspects of
domain complexity that are hypothesized to apply generally across domains and
tasks. Many questions remain. We believe that these questions need to be
formulated and addressed within a research agenda that treats domain-_general_
complexity (as opposed to domain-_specific_ complexity) as a first-class
citizen. We are not claiming that each such research question should apply
empirically to every domain, but ideally, it should be applicable to a diverse
set of domains, allowing general claims to be made. As next steps, we state
three questions below that (potentially) could be investigated in an
experimental setting with the goal of yielding general insights about domain
complexity:

  1. 1.

Can we derive strong theoretical connections between domain complexity and
_difficulty_? For instance, will it always be the case that tasks in a more
complex domain _necessarily_ will be more difficult, or just more difficult
_in expectation_? And can difficulty be studied independently of complexity?
These are questions with which multiple communities, especially within AI and
open-world learning, are only just beginning to grapple. In addition to
stating theoretical claims, it is also important to test these claims
empirically. We believe that designing appropriate experimental methodologies
that allow us to validate general claims is, in itself, a promising area for
future research.

  2. 2.

Can our measures of domain complexity be used to define and _quantify_
complexity in so-called complex systems, such as networks and dynamical
systems, as well as other nonlinear systems (e.g., differential equations,
computational fluid dynamics simulations, weather forecasting)? Is one system
more complex than another, and if so, then along what perspectives
(components)? Moreover, does this have theoretical ramifications, validated by
appropriate experiments, for analyzing such systems?

  3. 3.

In the cases of infinite action and state spaces, what are the appropriate
mathematical frameworks for distinguishing between domains of (arguably)
differing complexity? In real analysis, for instance, there are different
hierarchies of infinity that are well understood. For instance, integers and
real numbers both form infinite sets, but the latter has provably greater
cardinality than the former. Could similar claims be made for complexity?

These questions are not exhaustive, and some have several other questions
associated with them that may require several parallel lines of theoretical
and experimental research to investigate fully. We emphasize that the one
commonality between all these questions is their lack of dependence on a
single domain or model. Rather, all of them aim toward an agenda that is as
domain-independent as possible. As noted earlier, we believe that this is the
central element that distinguishes other field-specific studies of complexity
from our proposal.

##  9 Acknowledgments

This research was sponsored by DARPA and the Army Research Office (ARO) under
multiple contracts / agreements, including W911NF2020010, W911NF2020003, and
W911NF-20-2-0004. The views contained in this document are those of the
authors and should not be interpreted as representing the official policies,
either expressed or implied, of DARPA, NRL, ARO, or the U.S. government.

The following teams and individuals contributed to the open-world novelty
hierarchy presented in Table 1: Washington State University led by Lawrence
Holder, Australian National University led by Jochen Renz, University of
Southern California led by Mayank Kejriwal, University of Maryland led by
Abhniav Shrivastava, University of Texas at Dallas led by Eric Kildebeck,
University of Massachusetts at Amherst led by David Jensen, Tufts University
led by Matthias Scheutz, Rutgers led by Patrick Shafto, Georgia Tech led by
Mark Riedl, PAR Government led by Eric Robertson, SRI International led by
Giedrius Burachas, Charles River Analytics led by Bryan Loyall, Xerox PARC led
by Shiwali Mohan, Smart Information Flow Technologies led by David Musliner,
Raytheon BBN Technologies led by Bill Ferguson, Kitware led by Anthony Hoogs,
Tom Dietterich, Marshall Brinn, and Jivko Sinapov.

We are especially grateful to Christine Task for collaborating, providing
interesting ideas and extensive literature review for the initial version of
this paper presented at the AAAI Spring 2022 Workshop on Designing Artificial
Intelligence for Open Worlds Doctor et al. (2022). We thank Russell Leong,
Roman Sanelli, and Sarah DaSilva for conducting a literature review,
proofreading, and providing edits of the paper. We especially thank Daniel
Smith for expanding the literature and sparsity calculations for MNIST and
CIFAR-10 domains. The authors would also like to thank David Aha, Robert
Lazar, and Ira Moskowitz for their feedback on this or previous version of
this article.

## References

  * Albert et al. (2007) Albert, M., Nowakowski, R., Wolfe, D., 2007.  Lessons in Play: An Introduction to Combinatorial Game Theory.  CRC Press.  URL: https://books.google.com/books?id=pfLRBQAAQBAJ.
  * Allis (1994) Allis, L.V., 1994.  in: Searching for solutions in games and artificial intelligence, pp. 158–161.
  * Baxter (2011) Baxter, J., 2011.  A model of inductive bias learning.  CoRR abs/1106.0245.  URL: http://arxiv.org/abs/1106.0245, arXiv:1106.0245.
  * Board & Card Games (2022) Board & Card Games, S.E., 2022.  What is the average number of turns in a game of monopoly?  URL: https://boardgames.stackexchange.com/questions/33181/what-is-the-average-number-of-turns-in-a-game-of-monopoly.
  * Boult et al. (2021) Boult, T., Grabowicz, P., Prijatelj, D., Stern, R., Holder, L., Alspector, J., M. Jafarzadeh, M., Ahmad, T., Dhamija, A., Li, C., Cruz, S., Shrivastava, A., Vondrick, C., Walter, S., 2021\.  Towards a unifying framework for formal theories of novelty.  Proceedings of the AAAI Conference on Artificial Intelligence 35, 15047--15052.  URL: https://ojs.aaai.org/index.php/AAAI/article/view/17766.
  * Boult et al. (2022) Boult, T.E., Windesheim, N.M., Zhou, S., Pereyda, C., Holder, L.B., 2022.  Weibull-open-world (wow) multi-type novelty detection in cartpole3d.  Algorithms 15.  URL: https://www.mdpi.com/1999-4893/15/10/381, doi:10.3390/a15100381.
  * Brockman et al. (2016) Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., Zaremba, W., 2016.  Openai gym.  arXiv:arXiv:1606.01540.
  * Cao (2020) Cao, L., 2020.  Data science: Challenges and directions.  CoRR abs/2006.16966.  URL: https://arxiv.org/abs/2006.16966, arXiv:2006.16966.
  * Carroll and Byers (2017) Carroll, T.L., Byers, J.M., 2017\.  Dimension from covariance matrices.  Chaos: An Interdisciplinary Journal of Nonlinear Science 27, 023101.  URL: http://aip.scitation.org/doi/10.1063/1.4975063, doi:10.1063/1.4975063.
  * Casino (2022) Casino, O., 2022.  Mastering monopoly -- the odds of winning.  URL: https://www.onlinecasino.ca/monopoly-odds/.
  * Chaslot et al. (2008) Chaslot, G., Bakkes, S., Szita, I., Spronck, P., 2008\.  Monte-carlo tree search: A new framework for game ai, in: Proceedings of the Fourth Artificial Intelligence and Interactive Digital Entertainment Conference.
  * Claussmann et al. (2017) Claussmann, L., Revilloud, M., Glaser, S., Gruyer, D., 2017\.  A study on AI-based approaches for high-level decision making in highway autonomous driving, in: 2017 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pp. 3671--3676.  doi:10.1109/SMC.2017.8123203.
  * Doctor et al. (2022) Doctor, K., Task, C., Kildebeck, E., Kejriwal, M., Holder, L., Leong, R., 2022\.  Toward defining a domain complexity measure across domains.  AAAI Spring Symposium URL: https://usc-isi-i2.github.io/AAAI2022SS/papers/SSS-22_paper_79.pdf.
  * Ethayarajh et al. (2021) Ethayarajh, K., Choi, Y., Swayamdipta, S., 2021.  Information-theoretic measures of dataset difficulty.  CoRR abs/2110.08420.  URL: https://arxiv.org/abs/2110.08420, arXiv:2110.08420.
  * Fan et al. (2022) Fan, L., Wang, G., Jiang, Y., Mandlekar, A., Yang, Y., Zhu, H., Tang, A., Huang, D.A., Zhu, Y., Anandkumar, A., 2022.  Minedojo: Building open-ended embodied agnets with internet-scale knowledge.  arXiv:2206.08853 URL: https://arxiv.org/abs/2206.08853, arXiv:2206.08853.
  * Feldman (2012) Feldman, D., 2012.  Chaos and Fractals: An Elementary Introduction.  EBSCO ebook academic collection, OUP Oxford.  URL: https://books.google.com/books?id=exnWM_ZHK0MC.
  * Fisher (1936) Fisher, R.A., 1936.  The use of multiple measurements in taxonomic problems.  Annals of Eugenics 7, 179--188.  URL: https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1469-1809.1936.tb02137.x, doi:https://doi.org/10.1111/j.1469-1809.1936.tb02137.x, arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1111/j.1469-1809.1936.tb02137.x.
  * Flake (1998) Flake, G., 1998.  The Computational Beauty of Nature: Computer Explorations of Fractals, Chaos, Complex Systems, and Adaptation.  A Bradford book, MIT Press.  URL: https://www.amazon.com/dp/0262062003/?coliid=I6COO6CGLWZUA&colid=SQVB5SEZMI4L&psc=0&ref_=lv_ov_lig_dp_it.
  * Goss et al. (2023) Goss, S.A., Steininger, R.J., Narayanan, D., Olivença, D.V., Sun, Y., Qiu, P., Amato, J., Voit, E.O., Voit, W.E., Kildebeck, E.J., 2023.  Polycraft world ai lab (pal): An extensible platform for evaluating artificial intelligence agents.  arXiv preprint arXiv:2301.11891 .
  * Griffiths et al. (2010) Griffiths, T.L., Chater, N., Kemp, C., Perfors, A., Tenenbaum, J.B., 2010.  Probabilistic models of cognition: exploring representations and inductive biases.  Trends in Cognitive Sciences 14, 357--364.  URL: https://www.sciencedirect.com/science/article/pii/S1364661310001129, doi:https://doi.org/10.1016/j.tics.2010.05.004.
  * Guss et al. (2021) Guss, W.H., Codel, C., Hofmann, K., Houghton, B., Kuno, N., Milani, S., Mohanty, S., Liebana, D.P., Salakhutdinov, R., Topin, N., Veloso, M., Wang, P., 2021\.  Neurips 2019 competition: The minerl competition on sample efficient reinforcement learning using human priors.  arXiv:1904.10079v3 URL: https://arxiv.org/abs/1904.10079, arXiv:1904.10079v3.
  * Hernández-Orallo and Dowe (2010) Hernández-Orallo, J., Dowe, D.L., 2010\.  Measuring universal intelligence: Towards an anytime intelligence test.  Artificial Intelligence 174, 1508--1539.  URL: https://www.sciencedirect.com/science/article/pii/S0004370210001554, doi:https://doi.org/10.1016/j.artint.2010.09.006.
  * Holzinger et al. (2017) Holzinger, A., Biemann, C., Pattichis, C.S., Kell, D.B., 2017\.  What do we need to build explainable ai systems for the medical domain?  arXiv:1712.09923.
  * Hurley and Rickard (2009) Hurley, N., Rickard, S., 2009\.  Comparing measures of sparsity.  IEEE Transactions on Information Theory 55, 4723--4741.  doi:10.1109/TIT.2009.2027527.
  * Ingrand and Ghallab (2013) Ingrand, F., Ghallab, M., 2013\.  Robotics and artificial intelligence: a perspective on deliberation functions.  AI Communications 27.  doi:10.3233/AIC-130578.
  * Iqbal and Yaacob (2008) Iqbal, A., Yaacob, M., 2008\.  Computational assessment of sparsity in board games.
  * Jackson (2020) Jackson, M.C., 2020.  How we understand “complexity” makes a difference: Lessons from critical systems thinking and the covid-19 pandemic in the uk.  Systems 8.  URL: https://www.mdpi.com/2079-8954/8/4/52, doi:10.3390/systems8040052.
  * Jung et al. (2020) Jung, S., Sinha, K., Suh, E.S., 2020.  Domain mapping matrix-based metric for measuring system design complexity.  IEEE Transactions on Engineering Management , 1--9doi:10.1109/TEM.2020.3004561.
  * Kim (2014) Kim, J., 2014.  How Complexity Domain Impacts Software Development Process.  URL: https://gamemakers.com/how-complexity-domain-impacts-software-development-process/.
  * (30) Krizhevsky, A., .  The cifar-10 dataset.  URL: https://www.cs.toronto.edu/~kriz/cifar.html.
  * Langley (2020) Langley, P., 2020.  Open-world learning for radically autonomous agents.  Proceedings of the AAAI Conference on Artificial Intelligence 34, 13539--13543.  URL: https://ojs.aaai.org/index.php/AAAI/article/view/7078, doi:10.1609/aaai.v34i09.7078.
  * Leavy et al. (2020) Leavy, S., O’Sullivan, B., Siapera, E., 2020.  Data, power and bias in artificial intelligence.  CoRR abs/2008.07341.  URL: https://arxiv.org/abs/2008.07341, arXiv:2008.07341.
  * Legg and Hutter (2007) Legg, S., Hutter, M., 2007.  Universal intelligence: A definition of machine intelligence.  arXiv:0712.3329.
  * Mathematics Stack Exchange (a) Mathematics Stack Exchange, a.  Determining the number of valid tictactoe board states in terms of board dimension.  URL: https://math.stackexchange.com/q/613505, arXiv:https://math.stackexchange.com/q/613505. uRL:https://math.stackexchange.com/q/613505 (version: 2013-12-20).
  * Mathematics Stack Exchange (b) Mathematics Stack Exchange, b.  Tictactoe state space choose calculation.  URL: https://math.stackexchange.com/q/485752, arXiv:https://math.stackexchange.com/q/485752. uRL:https://math.stackexchange.com/q/485752 (version: 2018-05-23).
  * Mitchell (2007) Mitchell, T.M., 2007.  in: The Need for Biases in Learning Generalizations.
  * (37) Olah, C., .  Visualizing mnist: An exploration of dimensionality reduction.  URL: http://colah.github.io/posts/2014-10-Visualizing-MNIST/.
  * O’Connor et al. (2011) O’Connor, B., Bamman, D., Smith, N.A., 2011.  Computational text analysis for social science: Model complexity and assumptions, in: Proc. of the NIPS Workshop on Comptuational Social Science and the Wisdom of Crowds.
  * Pereyda and Holder (2020) Pereyda, C., Holder, L., 2020\.  Measuring the complexity of domains used to evaluate ai systems.  arXiv:2010.01985.
  * Potts et al. (2020) Potts, M.W., Sartor, P.A., Johnson, A., Bullock, S., 2020\.  Assaying the importance of system complexity for the systems engineering community.  Systems Engineering 23, 579--596.  URL: https://incose.onlinelibrary.wiley.com/doi/abs/10.1002/sys.21550, doi:https://doi.org/10.1002/sys.21550, arXiv:https://incose.onlinelibrary.wiley.com/doi/pdf/10.1002/sys.21550.
  * Prnjat and Sack (2001) Prnjat, O., Sack, L., 2001.  Complexity measurements of the inter-domain management system design, in: Proceedings. Ninth IEEE International Conference on Networks, ICON 2001., pp. 2--7.  doi:10.1109/ICON.2001.962308.
  * Remus and Ziegelmayer (2014) Remus, R., Ziegelmayer, D., 2014\.  Learning from domain complexity, in: Proceedings of the Ninth International Conference on Language Resources and Evaluation (LREC’14), European Language Resources Association (ELRA), Reykjavik, Iceland. pp. 2021--2028.  URL: http://www.lrec-conf.org/proceedings/lrec2014/pdf/480_Paper.pdf.
  * Senator (2019) Senator, T., 2019.  Science of artificial intelligence and learning for open-world novelty).  SAIL-ON URL: https://iresearch-cms.tau.ac.il/sites/resauth.tau.ac.il/files/DARPA SAIL-ONHR001119S0038.pdf.
  * Shannon (1948) Shannon, C.E., 1948.  A mathematical theory of communication.  Bell System Technical Journal 27\.  URL: http://cs-www.cs.yale.edu/homes/yry/readings/general/shannon1948.pdf.
  * Smaldone et al. (2017) Smaldone, R.A., Thompson, C.M., Evans, M., Voit, W., 2017\.  Teaching science through video games.  Nature Chemistry 9, 97--102.  URL: https://doi.org/10.1038/nchem.2694, doi:10.1038/nchem.2694.
  * Štuikys and Damaševičius (2009) Štuikys, V., Damaševičius, R., 2009.  Measuring Complexity of Domain Models Represented by Feature Diagrams.  Information Technology And Control 38, 179--187.
  * (47) Wikipedia, .  Game complexity --- Wikipedia, the free encyclopedia.  URL: https://en.wikipedia.org/w/index.php?title=Game_complexity&oldid=1129116028. [Online; accessed 13-January-2023].
  * Wilson et al. (2014) Wilson, M.A., McMahon, J., Aha, D.W., 2014.  Bounded expectations for discrepancy detection in goal-driven autonomy, in: AAAI Workshop - Technical Report, pp. 50--56.
  * XboxPress (2021) XboxPress, 2021.  Minecraft franchise fact sheet.  URL: https://news.xbox.com/en-us/wp-content/uploads/sites/2/2021/04/Minecraft-Franchise-Fact-Sheet_April-2021.pdf.
  * Yong and Yong (2019) Yong, A., Yong, D., 2019.  An estimation method for game complexity.  URL: https://arxiv.org/abs/1901.11161, doi:10.48550/ARXIV.1901.11161.