# Approximate PSD-Completion on Generalized Chordal Graphs

Kevin Shu

###### Abstract.

Recently, there has been interest in the question of whether a partial matrix
in which many of the fully defined principal submatrices are PSD is
approximately PSD completable. These questions are related to graph theory
because we can think of the entries of a symmetric matrix as corresponding to
the edges of a graph.

We first introduce a family of graphs, which we call thickened graphs; these
contain both triangle-free and chordal graphs, and can be viewed as the result
of replacing the edges of a graph by an arbitrary chordal graph. We believe
these graphs might be of independent interest.

We then show that for a class of graphs including thickened graphs, it is
possible to get quantitative bounds on how well the property of having these
principal submatrices being PSD approximates the PSD-completability property.
These bounds frequently only depend on the size of the smallest cycle of size
at least 4 in the graph. We introduce some tools that allow us to better
control the quality of these approximations and indicate how these
approximations can be used to improve the performance of semidefinite
programs. The tools we use in this paper are an interesting mix of algebraic
topology, structural graph theory, and spectral analysis.

##  1\. Introduction

The space of PSD matrices is one of the basic objects that is studied in
convex optimization because of its connection to semidefinite programming. We
will be interested in understanding coordinate projections of the set of PSD
matrices, or equivalently, the theory of PSD matrix completion.

The entries of an $n\times n$ symmetric matrix $X$ are indexed by unordered
pairs $\\{i,j\\}$ for $i,j\in[n]$. Given a graph $G$, there is a natural
projection of $X$ onto just those entries corresponding to the edges of $G$.
We call the image of this projection the space of $G$-partial matrices; they
are represented as matrices where entries corresponding to nonedges of $G$ are
‘forgotten’.

$\begin{pmatrix}1&0&0&0\\\ 0&1&0&0\\\ 0&0&1&0\\\
0&0&0&1\end{pmatrix}\rightarrow\begin{pmatrix}1&0&?&0\\\ 0&1&0&?\\\ ?&0&1&0\\\
0&?&0&1\end{pmatrix}$

Figure 1. An example of the projection of a matrix onto the edges of a cycle
graph.

The image of the PSD matrices under this projection is precisely the set of
$G$-partial matrices which can be completed to a PSD matrix. That is, these
are partial matrices where we can choose the ‘forgotten’ entries to make the
resulting symmetric matrix PSD. Checking that a partial matrix can be
completed to a PSD matrix is known as the PSD completion problem, and it has
been the subject of much study, for example in [10].

We can give a clear necessary condition for a matrix to be PSD completable: if
we can find a subset $S$ of the vertices of $G$ where for all $i,j\in S$,
$\\{i,j\\}\in G$, then we can form a submatrix of a partial matrix $X$ by just
looking at the indices in $S$. Being PSD is preserved under taking
submatrices, so if $X$ is PSD completable, then this submatrix of $X$ must be
PSD. A subset $S$ with this property is a clique of $G$, and if for all
cliques contained in $G$, the corresponding submatrix of $X$ is PSD, then we
say that $X$ is $G$-locally PSD.

Checking that these smaller blocks are PSD is often easier than checking that
the partial matrix is PSD completable. We are interested in understanding
whether it is sufficient to check that these smaller submatrices are PSD.

In the work of Grone et al. in [6], it was shown that if $G$ is chordal, then
$X$ is PSD completable if and only if $X$ is $G$-locally PSD, but that for all
other graphs, there are $G$-locally PSD partial matrices which are not PSD
completable. There have been various results extending this equality result by
introducing additional constraints, besides the submatrix-PSD constraints. For
example, Barrett and Laurent have considered the so-called cycle conditions
for PSD completability in series parallel graphs, and given precise conditions
for PSD completability in these cases in [1] and [8].

More recently, we have been interested in approximate PSD-completability, and
whether the $G$-locally PSD condition is enough to guarantee that a partial
matrix is approximately PSD completable. In [3], these PSD matrix completion
questions were connected to the theory of sum-of-squares and nonnegative
quadratic forms on certain algebraic varieties. There, quantitative results
were shown on the distance between the $G$-locally PSD cone and the PSD-
completable cone. In [11], we strengthened the connection with the theory of
nonnegative quadratic forms over algebraic varieties, which allowed us to
uncover some strong structural properties of these $G$-locally PSD partial
matrices. This paper, which combines the types of questions asked in [3] with
the structural results in [11], obtains approximation guarantees for a much
more general class of graphs, which we hope will prove to be useful in
practical applications.

In this paper, we will review the quantitative measurements of the distance
between the $G$-locally PSD partial matrices and the PSD completable partial
matrices in [3]. We will define our class of thickened graphs in 2.4 and we
will give our quantitative results in Theorem 3.1. These graphs are obtained
by replacing the edges of a given graph by general chordal graphs, and belong
to a more general class of graphs which we say have extreme local rank 1. We
then provide some additional results that complement these quantitative
results and provide stronger bounds in some cases. Though no deep knowledge of
algebraic topology or algebraic geometry is needed to understand the results
in this paper, we will be using techniques from algebraic topology to prove
these bounds.

Figure 2. An illustration of the thickened graph construction, illustrating
how we may replace the edges of a graph by chordal graphs.

###  1.1. PSD Completion and Sparse Semidefinite Programming

One major reason for considering the PSD completion problem is its connection
to sparse semidefinite programming.

A semidefinite program is an optimization problem of the form

minimize $\displaystyle\langle B^{0},X\rangle$ such that $\displaystyle\langle
B^{\ell},X\rangle=b_{\ell}$ $\displaystyle\text{ for }\ell\in\\{1,\dots,k\\}$
$\displaystyle X\succeq 0$

Here, the $B^{\ell}$ are $n\times n$ symmetric matrices, $X$ is an $n\times n$
symmetric matrix of variables, and $X\succeq 0$ means that $X$ is PSD, so that
all of the eigenvalues of $X$ are nonnegative.

A major difficulty encountered when solving these programs is their high
memory usage. The work of Fukuda in [5] showed that sparsity properties of a
semidefinite program can be exploited to reduce the number of variables. [12]
has a modern survey. If $G$ is the graph where $\\{i,j\\}\in E(G)$ when for
some $\ell$, $B^{\ell}_{i,j}\neq 0$, then optimizing a semidefinite program is
equivalent to optimizing over over the PSD completable $G$-partial matrices.

It was shown in [3] that for a certain class of graphs, including the cycle-
completable graphs defined in [1], optimizing over the $G$-locally PSD
matrices gives a $1+O(\frac{n}{g^{3}})$ approximation ratio, where $g$ is the
number of vertices in the smallest induced cycle with at least 4 vertices in
$G$. This is stated precisely in Theorem 26 in [3]. We extend these results to
a much wider class of graphs here.

##  2\. Preliminaries and Set Up

###  2.1. Graph Theoretic Preliminaries

A graph $G$ consists of a set of vertices $V(G)$ and a set of undirected edges
$E(G)\subseteq\\{\\{i,j\\}:i,j\in V(G)\\}$, and we will assume $G$ has all of
its loop edges, i.e. $\\{i,i\\}\in E(G)$ for all $i\in V(G)$.

For a subset $S\subseteq V(G)$, the subgraph of $G$ induced by $S$ is $G[S]$,
where $V(G[S])=S$, and $E(G[S])=\\{\\{i,j\\}\in E(G):i,j\in S\\}$.

An induced cycle of $G$ is a subset $S\subseteq V(G)$ so that $G[S]$ is
isomorphic to a cycle graph with vertex set $S$. A graph is said to be chordal
if it has no induced cycles with at least 4 vertices. The chordal girth of $G$
is the number of vertices in the smallest induced cycle of $G$ with more than
$4$ vertices, and we will let it be $\infty$ if $G$ is chordal. A clique of
$G$ is a subset $S\subseteq V(G)$ so that $G[S]$ is isomorphic to a complete
graph. We will use the term ‘triangle’ to refer to cliques of size $3$ in $G$,
and say that $G$ is triangle free if it contains no triangles. An induced path
in $G$ is a set of vertices $S\subseteq V(G)$ so that the induced subgraph
$G[S]$ is isomorphic to a path graph. A shortest path between vertices $a,b\in
V(G)$ is an induced path in $G$ whose endpoints are $a$ and $b$ so that any
other path from $a$ and $b$ has at least as many vertices.

For graphs $G$ and $H$, $\phi:V(G)\rightarrow V(H)$ is a graph homomorphism if
for $\\{i,j\\}\in E(G)$, $\\{\phi(i),\phi(j)\\}\in E(H)$.

Given an edge $e=\\{i,j\\}\in E(G)$, we will denote by $G/e$ the contraction
of $G$ by the edge $e$, i.e. the graph obtained by identifying the endpoints
of the edge $e$ into a single vertex. Precisely, $G/e$ is a graph defined by

$V(G/e)=(V(G)\setminus e)\sqcup v_{e},\text{ and }$ $E(G/e)=E(G[V(G)\setminus
e])\cup\\{\\{v,v_{e}\\}:\\{v,i\\}\in E(G)\text{ or }\\{v,j\\}\in E(G)\\}.$

There is a natural graph homomorphism $\phi:G\rightarrow G/e$ that sends the
vertices in $G$ not in $e$ to themselves, and sends the two vertices in $e$ to
$v_{e}$

A graph $G$ is series parallel if no sequence of edge contractions of $G$ will
result in the complete graph on $4$ vertices. The wheel graph is a graph
obtained by taking a cycle, introducing a new vertex, and then joining that
vertex to all existing vertices in the cycle.

###  2.2. PSD Matrix Completion

For a graph $G$ on $n$ vertices, a $G$-partial matrix is an $n\times n$
symmetric matrix $X$, where if $i\neq j$ and $\\{i,j\\}\not\in G$, $X_{ij}$ is
set to ‘unknown’. The vector space of $G$-partial matrices is denoted
$\operatorname*{Sym}(G)$.

Given $S\subseteq V(G)$, and $X\in\operatorname*{Sym}(G)$, there is a natural
restriction of $X$ to the subgraph $G[S]$, which we will denote
$X|_{S}\in\operatorname*{Sym}(G[S])$, so that $(X|_{S})_{ij}=X_{ij}$ when
$\\{i,j\\}\in E(G[S])$.

A $G$-partial matrix $X$ is said to be PSD-completable if there is a way of
choosing the unknown entries to make a complete matrix $\hat{X}$ so that
$\hat{X}$ is PSD. We will denote the convex cone of PSD-completable matrices
by $\mathcal{S}(G)$. To differ slightly from the terminology in [3], we will
say that a $G$-partial matrix is $G$-locally PSD if for each clique
$C\subseteq V(G)$, the submatrix $X|_{C}$ is PSD. We will denote the convex
cone of $G$-locally PSD partial matrices by $\mathcal{P}(G)$.

For a $G$-partial matrix $X$, we can define the trace by
$\operatorname*{tr}(X)=\sum_{i=1}^{n}X_{ii}$. Let
$\tilde{\mathcal{P}}(G)=\\{X\in\mathcal{P}(G):\operatorname*{tr}(X)=1\\}$.

We will denote the projection of the identity matrix to
$\operatorname*{Sym}(G)$ by $I_{G}$. Given $G$, and a $G$-partial matrix $X$,
let

$\epsilon_{G}(X)=\min\\{\epsilon:X+\epsilon(G)I_{G}\in\mathcal{S}(G)\\},\text{
and}$ $\epsilon(G)=\min\\{\epsilon_{G}(X):\forall
X\in\tilde{\mathcal{P}}(G)\\}.$

We refer to $\epsilon(G)$ as the additive distance for $G$. $\epsilon(G)$ is
in some senses a measurement of how far $X\in\tilde{\mathcal{P}}(G)$ can be
from being PSD completable. An equivalent definition of $\epsilon_{G}(X)$ is
that $-\epsilon_{G}(X)$ is the largest possible value of the minimum
eigenvalue of $\hat{X}$, where $\hat{X}$ is a completion of $X$.

One reason to consider this $\epsilon(G)$ definition is in the following
conical program for some convex cone $K\subseteq\operatorname*{Sym}(G)$:

minimize $\displaystyle\langle B^{0},X\rangle$ such that $\displaystyle\langle
B^{\ell},X\rangle=b_{\ell}$ $\displaystyle\text{ for }\ell\in\\{1,\dots,k\\}$
$\displaystyle X\in K.$

We say that this program is of Goemanns-Williamson type if
$\operatorname*{tr}(B^{0})=0$; for all feasible $X$,
$\operatorname*{tr}(X)\leq 1$, and $\frac{1}{n}I_{G}$ is a feasible point of
the program.

######  Theorem 2.1 (Theorem 26 in [3]).

Let $\alpha$ denote the value of the program when $K=\mathcal{S}(G)$, and
suppose that it is of Goemanns-Williamson type. Let $\alpha^{\prime}$ denote
the value of the program when $K=\mathcal{P}(G)$, then

$\alpha^{\prime}\leq\alpha\leq\frac{1}{1+n\epsilon(G)}\alpha^{\prime}.$

In [3], we computed the value of $\epsilon(G)$ for a number of different
graphs $G$, including cycles, series parallel graphs, and wheels. We also
provide a few basic operations that interact well with $\epsilon(G)$. We will
be most interested in the following theorems from that paper:

######  Theorem 2.2 (Theorem 25 in [3]).

Let $G$ be series parallel, and $g$ is the chordal girth of $G$, then

$\epsilon(G)=\frac{1}{g}\left(\frac{1}{\cos(\frac{\pi}{g})}-1\right)=O(g^{-3}).$

######  Theorem 2.3 (Theorem 7 in [3]).

Let $G$ and $H$ be graphs, so that $V(G)\cap V(H)$ induces a clique in both
$G$ and $H$. Let the clique sum of $G$ and $H$ be the union $G\cup H$. Then,

$\epsilon(G\cup H)=\max\\{\epsilon(G),\epsilon(H)\\}.$

In [11], we generalize the definition of $\mathcal{P}(G)$ to allow for us to
enforce the PSD condition on an arbitrary set of cliques of $G$, instead of
always enforcing it on all cliques of $G$. We will not need this level of
generality here, but we will introduce a related notion where we only enforce
the PSD condition on edges of $G$. Let $\mathcal{P}^{-}(G)$ denote the set of
$X\in\operatorname*{Sym}(G)$ so that for all $\\{i,j\\}\in E(G)$,
$X|_{\\{i,j\\}}\succeq 0$. If $G$ is triangle free, then all cliques of $G$
are edges, so that $\mathcal{P}^{-}(G)=\mathcal{P}(G)$.

Now, let

$\epsilon^{-}(G)=\max\\{\epsilon_{G}(X):X\in\mathcal{P}^{-}(G)\text{ and
}\operatorname*{tr}(X)=1\\}.$

Just considering $\epsilon^{-}(G)$ will not provide useful bounds for
interesting graphs $G$, but we will use this definition to bound
$\epsilon(G^{\prime})$ for graphs $G^{\prime}$ which are related to $G$.

###  2.3. Extreme Locally-Rank 1 Graphs and Thickened Graphs

The extreme rays of $\mathcal{S}(G)$ can be seen to be those $G$-partial
matrices which are completable to rank 1 PSD matrices.

The extreme rays of $\mathcal{P}(G)$ are in general harder to understand, but
in some cases, they can be seen to have some nice structure. We will say that
$X\in\mathcal{P}(G)$ is locally rank 1 if for all cliques $C\subseteq V(G)$,
$X|_{C}$ is rank 1. We will say that $G$ has extreme local rank 1 if all
extreme rays of $\mathcal{P}(G)$ are locally rank 1. We will describe these
locally rank 1 extreme rays in greater detail in section 4, but it should be
clear that this is a very restrictive property.

One natural question is whether there are in fact any interesting graphs of
extreme local rank 1. We now describe the class of thickened graphs, which
gives a nice family of examples.

Figure 3. A small example of a thickened graph, which we refer to as a
thickened 4-cycle. We will see that the additive distance for this graph is
the same as that of the 4-cycle.

###  2.4. Thickened Graphs

Figure 4. A construction of a thickened 4-cycle. Here, $D$ is a multidigraph
with 3 vertices, and 3 edges $e_{1},e_{2},e_{3}$. We then introduce chordal
graphs $C_{e_{1}}$, $C_{e_{2}}$, and $C_{e_{3}}$ and attach them to form the
thickened 4-cycle.

A multidigraph (also known as a quiver) $D$ is a directed graph possibly with
multiple edges. Formally, we define a multidigraph in terms of a set of edges,
$E(D)$; a set of vertices $V(D)$, and two functions $t:E(D)\rightarrow V(D)$
and $h:E(D)\rightarrow V(D)$ where $t(e)$ is the tail of the edge $e$, and
$h(e)$ is the head of the edge $e$, and for each $e\in E(D)$, $t(e)\neq h(e)$.
The undirected graph associated with $D$ is $D^{\prime}$ where
$V(D^{\prime})=V(D)$ and $E(D^{\prime})=\\{\\{i,j\\}:\exists e\in
E(D),i=t(e)\text{ and }j=h(e)\\}$.

Given a multidigraph, $D$, a thickening of $D$ can be thought of informally as
a graph obtained by replacing the edges of $D$ by chordal graphs, as seen in
figure 4.

Formally, for each edge $e\in E(D)$, we take a connected chordal graph $C_{e}$
and two distinguished vertices $T(e),H(e)\in V(C_{e})$. We then consider the
disjoint union of the $C_{e}$ and $V(D)$, and then identify the vertex $T(e)$
with $t(e)$ and $H(e)$ with $h(e)$ for all $e\in E(D)$, i.e.,

$G=D/\\{C_{e}\\}=\left(\sqcup_{e\in E(D)}C_{e}\sqcup V(D)\right)/\\{T(e)\sim
t(e),H(e)\sim h(e)\\}.$

We will say that $G$ is a thickening of $D$ if every triangle in $G$ is
contained in $C_{e}$ for some $e\in E(D)$. We will say that $G$ is a thickened
graph when $D$ is left implicit.

######  Theorem 2.4.

If $G$ is a thickened graph, then $G$ has extreme local rank 1.

Thickened graphs contain both triangle free and chordal graphs as subclasses,
and we will see that it is possible to bound their additive distances.

##  3\. Results

###  3.1. Additive Distance for Locally Rank 1 Graphs

Our main result concerns the additive distances for thickened graphs. In
particular, it shows that we can reduce the problem of computing the additive
distance for a thickened graph is equivalent to computing the additive
distance for an associated triangle-free graph. Though it is a relatively
simple consequence of the more general theorem 3.7, we will state this theorem
first because it does not require the definition of simplicial cohomology.

######  Theorem 3.1.

Let $D$ be a multidigraph. For each $e\in E(D)$, let $C_{e}$ be a chordal
graph with vertices $T(e),H(e)\in V(C_{e})$, and suppose that $D/\\{C_{e}\\}$
is a thickening of $D$. For each $e\in E(D)$, let $P_{e}$ be a shortest path
from $T(e)$ to $H(e)$ in $C_{e}$. Then

$\epsilon(D/\\{C_{e}\\})=\epsilon(D/\\{P_{e}\\}).$

These results interact nicely with results from [3], and in particular, the
previous result, together with theorem 2.2 implies the following corollary:

######  Corollary 3.2.

Let $D$ be a multidigraph, so that the undirected version of $D$ is triangle
free and series parallel, then for any collection of chordal $C_{e}$ so that
$D/\\{C_{e}\\}$ is a thickening of $D$,

$\epsilon(D/\\{C_{e}\\})=\epsilon(\mathcal{O}_{g}).$

Here $g$ is the chordal girth of $D/\\{C_{e}\\}$, and $\mathcal{O}_{g}$ is a
cycle with $g$ vertices.

This adds to the a large class of graphs for which
$\epsilon(G)=\epsilon(\mathcal{O}_{g})$ for $g$ the chordal girth of $G$
originally described in [3]. We will comment that while
$\epsilon(G)\geq\epsilon(\mathcal{O}_{g})$ for all graphs $G$, not all graphs
meet this bound with equality, and the Peterson graph is a counterexample.

###  3.2. Bounds on $\epsilon^{-}(G)$.

We round out our results with some bounds on $\epsilon^{-}(G)$ for some graphs
$G$. Such results complement the results in the previous section.

Let $\omega(G)$ denote the size of the largest clique in $G$, and let
$\operatorname*{tw}(G)$ denote the treewidth of $G$. The treewidth of a graph
is the smallest possible clique number of a chordal graph with $G$ as a
subgraph.

######  Theorem 3.3.

$1-\frac{2}{\omega(G)}\leq\epsilon^{-}(G)\leq
1-\frac{2}{\operatorname*{tw}(G)+1}.$

Of course, if $G$ contains a triangle, then this gives us a constant lower
bound on $\epsilon^{-}(G)$, and indicates that $\epsilon^{-}$ cannot be used
to bound this approximation ratio. However, we can improve these bounds using
the lengthening operation.

Let $G$ be a graph, and let $G_{\ell}$ be the result of replacing each edge of
$G$ by a path with $\ell$ edges, so that $G_{1}=G$. We formally define this
graph in 6.1, but offer a picture for intuition.

Figure 5. An image depicting the lengthening of a wheel graph.

Let $\mathcal{O}_{\ell}$ denote the $\ell$-vertex cycle.

######  Theorem 3.4.

For $\ell>1$,

$\epsilon(G_{\ell})\leq\frac{\epsilon(\mathcal{O}_{\ell})\epsilon^{-}(G)}{\epsilon(\mathcal{O}_{\ell})+2\epsilon^{-}(G)}.$

This result can be related to the theorem 3.1, as follows:

######  Corollary 3.5.

Let $D$ be a multidigraph, and let $D^{\prime}$ be the unoriented version of
$D$. For each $e\in E(D)$, let $C_{e}$ be a chordal graph with vertices
$T(e),H(e)\in V(C_{e})$, so that the distance from $T(e)$ to $H(e)$ is at
least $\ell$ and $D/\\{C_{e}\\}$ is a thickening of $D$. Then

$\epsilon(D/\\{C_{e}\\})\leq\frac{\epsilon(\mathcal{O}_{\ell})\epsilon^{-}(D^{\prime})}{\epsilon(\mathcal{O}_{\ell})+2\epsilon^{-}(D^{\prime})}.$

Intuitively, this result implies that as long as we use construct a thickened
graph using chordal graphs with endpoints which are far apart, we can still
get a good bound on the additive distance for $G$, even if $D$ is relatively
complicated.

###  3.3. Applications

Typically, semidefinite programs that arise in actual applications do not have
a chordal sparsity pattern or even a sparsity pattern associated with a
thickened graph. Instead, one notices that a semidefinite program which is
sparse for a graph $G$ will also be sparse for a graph $H$ where $H$ contains
$G$, so one finds a larger graph that contains the given sparsity pattern.
Unfortunately, the problem of finding the chordal graph with fewest possible
edges containing a given graph $G$ is NP-hard even to approximate (see [4]).

Corollary 3.5 implies that instead of finding a chordal graph containing $G$,
we can instead break $G$ into smaller pieces, and then find a chordal
completion for those smaller pieces. Then, as along as those smaller pieces
only intersect in vertices, and if the distances between those intersection
points is bounded from below by $\omega(\sqrt{n})$, it is still possible to
obtain good upper bounds on the approximation error given by the locally-PSD
approximation. While this is unlikely to yield asymptotic speed ups in the
general case, it may still be of interest for practical purposes.

###  3.4. Simplicial Cohomology

In order to state our most general result, we will need a definition of
cohomology, where we will refer to [7] for more details. While we will give an
application where cohomology is useful, it is not necessary to understand the
result in the case of thickened graphs, which we consider to be the most
concrete case.

We will say that a function $f:E(G)\rightarrow\mathbb{Z}/2\mathbb{Z}$ is a
cocycle if for all $\\{i,j,k\\}\subseteq V(G)$ so that $\\{i,j,k\\}$ induces a
triangle in $G$, $f(\\{i,j\\})+f(\\{j,k\\})+f(\\{i,k\\})=0$. We will say that
a function $g:E(G)\rightarrow\mathbb{Z}/2\mathbb{Z}$ is a coboundary if there
is some function $d:V(G)\rightarrow\mathbb{Z}/2\mathbb{Z}$ so that
$f(\\{i,j\\})=d(i)+d(j)$ for all $\\{i,j\\}\in E(G)$. Two cocycles $f_{1}$ and
$f_{2}$ are said to be equivalent if $f_{1}+f_{2}$ is a coboundary. The degree
1 simplicial cohomology group of $G$ with $\mathbb{Z}/2\mathbb{Z}$
coefficients, denoted $H^{1}(G;\mathbb{Z}/2\mathbb{Z})$ is the set of
equivalence classes of cocycles of $G$.

######  Remark 3.6.

Technically, what we are calling the simplicial cohomology group of $G$ is
actually the simplicial cohomology group of the clique complex of $G$.
However, for our purposes, we will abbreviate this to the simplicial
cohomology group of $G$.

The notion of cohomology is extremely pervasive in algebraic topology, and we
will see it appear naturally in this context when characterizing the locally
rank 1 extreme rays of $\mathcal{P}(G)$. One reason that cohomology is so
useful is that it interacts nicely with graph homomorphisms.

###  3.5. Induced Maps

If $\phi:G\rightarrow H$ is a graph homomorphism, and
$f:E(H)\rightarrow\mathbb{Z}/2\mathbb{Z}$, then let $\phi^{*}(f)$ be the
function from $E(G)$ to $\mathbb{Z}/2\mathbb{Z}$ defined by
$\phi^{*}(f)(\\{i,j\\})=f(\\{\phi(i),\phi(j)\\})$.

This is called the induced map on cohomology of $\phi$. The name is justified
because $\phi^{*}$ sends cocycles to cocycles, and coboundaries to
coboundaries, so $\phi^{*}$ is a group homomorphism from
$H^{1}(H;\mathbb{Z}/2\mathbb{Z})$ to $H^{1}(G;\mathbb{Z}/2\mathbb{Z})$.

We will say that $\phi$ is surjective in degree 1 if $\phi^{*}$ is surjective.

Given $\phi:G\rightarrow H$, and $S\subseteq V(G)$, there is a restricted map
from $\phi|_{S}:G[S]\rightarrow H$ so that for $v\in S$,
$\phi|_{S}(v)=\phi(v)$. We will say that $\phi$ is completely surjective if
for all $S\subseteq V(G)$, $\phi|_{S}$ is surjective in degree 1.

Completely surjective maps will be useful in constructing our bounds on the
additive distances for extreme locally rank 1 graphs.

###  3.6. Homomorphism Bound for Graphs of Extreme Local Rank 1

Our most general, result relates the additive distances of two graphs which
are related by a completely surjective graph homomorphism.

######  Theorem 3.7.

If $G$ has extreme local rank 1 and $\phi:G\rightarrow H$ is completely
surjective, then $\epsilon(G)\leq\epsilon(H)$.

The remainder of this paper is devoted to proofs of these results.

##  4\. Classification of Locally Rank 1 Extreme Rays and Cohomology

In order to prove our main results, we will need some additional information
about the structure of locally rank 1 extreme rays of $\mathcal{P}(G)$.

The primary thing to notice is that if $X$ is a locally rank 1 partial matrix
then because all of the $2\times 2$ minors are rank 1, we have that for all
$\\{i,j\\}\in E(G)$, $X_{ij}^{2}=X_{ii}X_{jj}$, so that the values of the
$|X_{ij}|$ is determined by the diagonal entries of $X$. If all of the
specified off-diagonal entries of $X$ are nonnegative, and $X$ is locally rank
1, then $X$ is equal to a rank PSD completable matrix. So a locally rank 1 $X$
is equal to a rank 1 PSD completable partial matrix, except the signs of the
off-diagonal entries may not be consistent with a PSD-completable partial
matrix.

We will say that $X\in\operatorname*{Sym}(G)$ has support $S=\\{i\in
V(G):X_{ii}>0\\}=S$.

Given a diagonal matrix $D$, we let $DXD$ be the partial matrix where
$(DXD)_{ij}=D_{ii}D_{jj}X_{ij}$. Notice that if $\hat{X}$ is a completion of
$X$, then $D\hat{X}D$ (which is defined using usual matrix multiplication) is
a completion of $DXD$. We will say that partial matrices $X$ and $Y$ are
diagonally congruent if $X=DYD$ for some diagonal matrix $D$. It is not hard
to see that if $X\in\mathcal{P}(G)$ is locally rank 1 with support $S$, then
$X$ is diagonally congruent to a locally rank 1 matrix $Y$ where $Y_{ii}=1$
for $i\in S$; $Y_{ij}=\pm 1$ for $\\{i,j\\}\in E(G[S])$, and $Y_{ij}=0$ for
$\\{i,j\\}\not\in E(G[S])$.

Given a locally rank 1 $X\in\operatorname*{Sym}(G)$ with support $S$, we will
define the sign pattern of $X$ to be the function
$f:E(G[S])\rightarrow\mathbb{Z}/2\mathbb{Z}$ where
$f(\\{i,j\\})=\sigma(X_{ij})$. Here,

$\sigma(x)=\begin{cases}0\text{ if }x\geq 0\\\ 1\text{ otherwise
}\end{cases}.$

The following theorem is shown in [11].

######  Theorem 4.1.

For any locally rank 1 $X\in\mathcal{P}(G)$ with support $S$, the sign pattern
of $X$ is a cocycle. Also, $X,Y\in\mathcal{P}(G[S])$ are diagonally congruent
if and only if the the sign patterns of $X$ and $Y$ differ by a coboundary.
Finally, for every coycle $f$, there is some locally rank 1
$X\in\mathcal{P}(G)$ with support $S$ so that the sign pattern of $X$ is $f$.

###  4.1. Graph Homomorphisms, Induced Maps, and Cohomology

Given a graph homomorphisms $\phi:G\rightarrow H$, define a linear map
$\phi^{*}:\operatorname*{Sym}(H)\rightarrow\operatorname*{Sym}(G)$ by taking
$X\in\mathcal{P}(H)$ to the partial matrix $Y$ so that
$Y_{ij}=X_{\phi(i)\phi(j)}$ for all $\\{i,j\\}\in E(G)$. We are abusing this
notation because we earlier defined $\phi^{*}$ to be the induced map on
cohomology. This is justified because if $X\in\mathcal{P}(H)$ is locally rank
1, then $\phi^{*}(X)\in\mathcal{P}(G)$ is also locally rank 1, and moreover if
$f$ is the sign pattern of $X$, then $\phi^{*}(f)$ is the sign pattern of
$\phi^{*}(Y)$ (up to coboundaries).

One key thing about $\phi^{*}$ is that it also sends $\mathcal{P}(H)$ to
$\mathcal{P}(G)$ and also it sends $\mathcal{S}(G)$ to $\mathcal{S}(H)$, i.e

######  Lemma 4.2.

If $\phi:G\rightarrow H$ then for any $X\in\mathcal{P}(H)$,
$\phi^{*}(X)\in\mathcal{P}(G)$.

######  Lemma 4.3.

If $\phi:G\rightarrow H$ then for any $X\in\mathcal{S}(H)$,
$\phi^{*}(X)\in\mathcal{S}(G)$.

These facts are not hard to see from the definitions, and are used for example
in [9].

Now, we introduce the main technical tool in this section, which can be seen
from the discussion in this section.

######  Theorem 4.4.

If $\phi$ is completely surjective, then for every locally rank 1
$X\in\mathcal{P}(G)$, there is some locally rank 1 $Y\in\mathcal{P}(H)$ so
that $\phi^{*}(Y)$ is diagonally congruent to $X$.

##  5\. Additive Distance for Locally Rank 1 Graphs

###  5.1. Graph Homomorphism Bound

######  Theorem 5.1 (Theorem 3.7).

Let $G$ and $H$ be extreme locally rank 1 graphs. If $\phi:G\rightarrow H$ is
completely surjective, then $\epsilon(G)\leq\epsilon(H)$.

###### Proof.

Firstly, note that there exists some extreme point $X$ of
$\tilde{\mathcal{P}}(G)$ so that $\epsilon_{G}(X)=\epsilon(G)$. This follows
because $\epsilon_{G}(X)$ was seen to be a concave function of $X$ in [3].

Every extreme ray of $\mathcal{P}(G)$ is locally rank 1 by definition, so we
know that $X$ is locally rank 1. Because $\phi$ is completely surjective,
there is some locally rank 1 $Y\in\mathcal{P}(H)$ so that $\phi^{*}(Y)$ is
diagonally congruent to $X$. Assume that $D\phi^{*}(Y)D=X$ for some diagonal
matrix $D$. In particular, for any $i$ in the support of $X$, $\phi(i)$ is in
the support of $Y$.

By applying an appropriate diagonal transformation to $Y$, we may assume that

$Y_{ii}=\sum_{j\in V(G):\phi(j)=i}X_{ii}.$

In this case,

$\displaystyle\operatorname*{tr}(Y)$ $\displaystyle=\sum_{i\in V(H)}Y_{ii}$
$\displaystyle=\sum_{j\in V(G)}X_{ii}$ $\displaystyle=1.$

Therefore, $Y\in\tilde{\mathcal{P}}(H)$, and from the definition of
$\epsilon(H)$, $Y+\epsilon(H)I_{H}\in\mathcal{S}(H)$.

Therefore, because these induced maps send $\mathcal{S}(H)$ to
$\mathcal{S}(G)$ by Lemma 4.3,
$\phi^{*}(Y+\epsilon(H)I_{H})\in\mathcal{S}(G)$. We can compute then that

$\displaystyle D(\phi^{*}(Y)+\epsilon(H)\phi^{*}(I_{H}))D$
$\displaystyle=D(\phi^{*}(Y)+\epsilon(H)\phi^{*}(I_{H}))D$
$\displaystyle=X+\epsilon(H)D\phi^{*}(I_{H})D$
$\displaystyle\in\mathcal{S}(G).$

Here, we are using the linearity of $\phi^{*}$, the fact that
$D\phi^{*}(Y)D=X$ and the fact that diagonal congruence preserves PSD-
completability.

Let $J=D\phi^{*}(I_{H})D$. We now apply the following lemma (whose proof we
defer until after this proof).

######  Lemma 5.2.

$J$ has a completion whose eigenvalues are all at most 1.

Using this lemma, we see that $I_{G}-J$ is PSD completable. Therefore,

$X+\epsilon(H)I_{G}=(X+\epsilon(H)J)+\epsilon(H)(I_{G}-J)$

is PSD completable, since this is the sum of 2 PSD-completable matrices. ∎

###### Proof.

(of lemma 5.2) Let us consider first the matrix $\phi^{*}(I_{H})$. It can be
verified with a direct computation that $\phi^{*}(I)$ is a partial matrix
where for all $\\{i,j\\}\in E(G)$,

$\phi^{*}(I_{H})_{ij}=\begin{cases}0\text{ if }\phi(i)\neq\phi(j)\\\ 1\text{
otherwise}\end{cases}.$

Therefore,

$J_{ij}=(D\phi^{*}(I_{H})D)_{ij}\begin{cases}0\text{ if }\phi(i)\neq\phi(j)\\\
D_{ii}D_{jj}\text{ otherwise}\end{cases}.$

Consider the completion of $J$ where all of the unknown entries are completed
to 0, which we denote $\hat{J}$. The key thing thing to notice about $\hat{J}$
is that it can be permuted into a block diagonal matrix, where there is a
block $B_{v}$ for each $v\in V(H)$, where $B_{v}=\\{i\in V(G):\phi(i)=v\\}$.
That is, $\hat{J}_{ij}=0$ if $i$ and $j$ do not belong to the same block.

Therefore, every eigenvalue of $\hat{J}$ is an eigenvalue of
$\hat{J}|_{B_{v}}$ for some $v\in V(H)$. Now, we notice that
$\hat{J}|_{B_{v}}$ is a rank 1 matrix, which can easily be seen because for
$i,j\in B_{v}$, $J_{i,j}=D_{ii}D_{jj}$. Therefore, there is a unique nonzero
eigenvalue of $\hat{J}|_{B_{v}}$, which is equal to
$\operatorname*{tr}(\hat{J}|_{B_{v}})$.

To conclude, we compute

$\displaystyle\operatorname*{tr}(\hat{J}|_{B_{v}})$ $\displaystyle=\sum_{j\in
V(G):\phi(j)=i}(D\phi^{*}(I)D)_{jj}$ $\displaystyle=\sum_{j\in
V(G):\phi(j)=i}D_{jj}^{2}$ $\displaystyle=\sum_{j\in
V(G):\phi(j)=i}\frac{X_{jj}}{Y_{ii}}$
$\displaystyle=\frac{1}{Y_{ii}}\sum_{j\in V(G):\phi(j)=i}X_{jj}$
$\displaystyle=1.$

Therefore, all eigenvalues of $\hat{J}$ are either 1 or 0, which concludes our
proof. ∎

###  5.2. Thickened Graphs

We now turn our attention to thickened graphs specifically out of all graphs
of extreme local rank 1. We will need some homological lemmas to prove our
main result in this subsection, Theorem 3.1.

######  Lemma 5.3.

Let $G=D/\\{C_{e}\\}$ be a thickened graph, and let $S\subseteq V(G)$ be a set
of vertices, then the inclusion map $\phi:G[S]\rightarrow G$ is completely
surjective.

###### Proof.

It is not hard to see this directly from the definition of cohomology as we
have given it, but there is a simple way to show this using Meyer-Vietoris
sequences, whose full definition can be found in [7].

It clearly suffices by induction to consider the case when $S=V(G)-v$ for some
vertex $v$, and to show that the induced map
$\phi^{*}:H^{1}(G;\mathbb{Z}/2\mathbb{Z})\rightarrow
H^{1}(G[S];\mathbb{Z}/2\mathbb{Z})$ is surjective.

Let $T$ be the closed neighborhood of $v$ in $G$ (so that $v\in T$), and
notice that $G=G[S]\cup G[T]$. Part of the Meyer-Vietoris exact sequence
states that the following sequence is exact:

$H^{1}(G;\mathbb{Z}/2\mathbb{Z})\rightarrow
H^{1}(G[S];\mathbb{Z}/2\mathbb{Z})\oplus
H^{1}(G[T];\mathbb{Z}/2\mathbb{Z})\rightarrow H^{1}(G[S]\cap
G[T];\mathbb{Z}/2\mathbb{Z}).$

Our assumptions on $G$ implies that $G[S]\cap G[T]$ is in fact a disjoint
union of connected chordal graphs, and therefore, $H^{1}(G[S]\cap
G[T];\mathbb{Z}/2\mathbb{Z})=0$.

Therefore, $H^{1}(G;\mathbb{Z}/2\mathbb{Z})$ surjects onto
$H^{1}(G[S];\mathbb{Z}/2\mathbb{Z})\oplus H^{1}(G[T];\mathbb{Z}/2\mathbb{Z})$,
and in particular, it surjects onto $H^{1}(G[S];\mathbb{Z}/2\mathbb{Z})$, as
desired. ∎

######  Lemma 5.4.

Let $G$ be a graph and let $e\in G$ be an edge of $G$ which is not contained
in any induced 4-cycles. Let $\phi:G\rightarrow G/e$ be the natural graph
homomorphism that contracts the edge $e$. Then
$\phi^{*}:H^{1}(G/e;\mathbb{Z}/2\mathbb{Z})\rightarrow
H^{1}(G;\mathbb{Z}/2\mathbb{Z})$ is surjective.

###### Proof.

This can actually be seen abstractly by observing that the clique complex of a
$G$ deformation retracts to the clique complex of $G/e$. We will show this
directly for completeness.

Let $f\in H^{1}(G;\mathbb{Z}/2\mathbb{Z})$ be a cohomology class. We need to
define some $g\in H^{1}(G/e;\mathbb{Z}/2\mathbb{Z})$ so that $\phi^{*}(g)=f$.

To do this, choose a representative cocycle of $f$ so that $f(e)=0$ (which is
easy to producce). Let $e=\\{i,j\\}$ and consider any $v\in G$ so that
$\\{v,i\\},\\{v,j\\}\in E(G)$. We see that there is a triangle $\\{i,j,v\\}$
in $G$, so that $f(\\{i,j\\})+f(\\{i,v\\})+f(\\{j,v\\})=0$, and therefore,
since $f(\\{i,j\\})=0$, $f(\\{i,v\\})=f(\\{j,v\\})$.

Let $g:E(G/e)\rightarrow\mathbb{Z}/2\mathbb{Z}$ so that for all $e\in E(G/e)$,
$g(d)=f(t)$ for any $t$ so that $\phi(t)=d$. This does not depend on the
choice of $t$ that maps to $d$ by our previous observation. It is clear from
this definition that if $g$ is a cocycle, then $\phi^{*}(g)=f$.

It remains to check that $g$ is a cocycle, i.e. that for any triangle
$\\{a,b,c\\}\in G/d$, $g(\\{a,b\\})+g(\\{b,c\\})+g(\\{a,c\\})=0$. We see that
if $\\{a,b,c\\}$ forms a triangle in $G/d$, then there must be some triangle
$\\{x,y,z\\}\in G$ so that $\phi(\\{x,y,z\\})=\\{a,b,c\\}$ from our assumption
that $e$ is contained in no induced 4-cycles. Therefore,
$g(\\{v,w\\})+g(\\{w,z\\})+g(\\{v,z\\})=f(\\{v,w\\})+f(\\{w,z\\})+f(\\{v,z\\})=0$.

We conclude that $\phi^{*}$ is surjective.

∎

######  Theorem 5.5 (Theorem 3.1).

Let $D$ be a multidigraph. For each $e\in E(D)$, let $C_{e}$ be a chordal
graph with vertices $T(e),H(e)\in V(C_{e})$, and suppose that $D/\\{C_{e}\\}$
is a thickening of $D$. For each $e\in E(D)$, let $P_{e}$ be a shortest path
from $T(e)$ to $H(e)$ in $C_{e}$. Then

$\epsilon(D/\\{C_{e}\\})=\epsilon(D/\\{P_{e}\\}).$

###### Proof.

Firstly, notice that $P_{e}$ is an induced subgraph of $C_{e}$ because it is a
shortest path. It is clear then that $D/\\{P_{e}\\}$ is an induced subgraph of
$D/\\{C_{e}\\}$, and so it is clear that

$\epsilon(G)\geq\epsilon(D/\\{P_{e}\\}).$

To get the inequality in the other direction, we will induct on the number of
edges of $G$. If $|E(G)|=|E(D/\\{P_{e}\\})|$, then $G=D/\\{P_{e}\\}$, and the
equality holds trivially.

Hence, assume that there is an edge $d\in E(G)$ which is not in
$D/\\{P_{e}\\}$. This implies that for some $e$, $d\in E(C_{e})$, so that $d$
is not in $P_{e}$. The next lemma will allow us to apply lemma 5.4 in this
situation.

######  Lemma 5.6.

If $G=D/\\{C_{e}\\}$ is a thickened graph, and $P_{e}$ is a shortest path from
$T(e)$ to $H(e)$ in $C_{e}$. Suppose that $C_{e}$ contains an edge not in
$P_{e}$, then there is an edge $d\in C_{e}$ so that

  * •

$d$ is not contained in any induced 4-cycles

  * •

$d$ is not contained in any shortest path from $T(e)$ to $H(e)$.

Now, we can apply Lemma 5.4 to say that the map $\phi:G\rightarrow G/d$ is
surjective in degree 1, and hence by Lemma 5.3, the map is completely
surjective. Therefore, by Theorem 3.7, we have that
$\epsilon(G)\leq\epsilon(G/e)$.

Now, notice that $C_{e}/d$ is chordal, and therefore, $G/d$ can be viewed as
the thickened graph $D/\\{C^{\prime}_{e}\\}$ where $C^{\prime}_{e}=C_{e}$ when
$d\not\in C_{e}$ and $C^{\prime}_{e}=C_{e}/d$ when $d\in C_{e}$. $G/d$ has at
least 1 fewer edge than $G$, and because $d$ is contained in no shortest path
from $T(e)$ to $H(e)$, we have that $P_{e}$ is a shortest path from $T(e)$ to
$H(e)$. Therefore, by induction, we know that
$\epsilon(G/d)=\epsilon(D/\\{P_{e}\\})$.

Combining these facts, we obtain that $\epsilon(G)=\epsilon(D/\\{P_{e}\\})$. ∎

Before proving the graph theoretic lemma 5.6, we will prove a auxilliary
lemma:

######  Lemma 5.7.

Let $G$ be a connected chordal graph, and let $v,w\in G$. Suppose $G$ is not a
path graph, then there exists an edge not contained in any shortest path from
$v$ to $w$.

###### Proof.

Let $P$ be a shortest path from $v$ to $w$, and suppose that the vertices in
$P$ are ordered $x_{1},\dots,x_{k}$, where $x_{1}=v$ and $x_{k}=w$, and
$\\{x_{i},x_{i+1}\\}\in E(C_{e})$ for $i\in[k]$.

Let $d$ be an edge of $G$ which is a vertex of $P$, and suppose that $d$ is
contained in another shortest path, $Q$ from $v$ to $w$.

It is clear because $P$ and $Q$ have the same start and endpoints that $P\cup
Q$ must contain a cycle, say
$\mathcal{O}=\\{x_{a},\dots,x_{b}\\}\cup\\{y_{c},\dots,y_{d}\\}$, where
$y_{c}=x_{a}$ and $y_{d}=x_{b}$. (It is not hard to see that we can assume
that $a<b$ and $c<d$ using some basic observations about shortest paths.)
Notice that the number of vertices of $P$ in $\mathcal{O}$ must be the same as
the number of vertices of $Q$ in $\mathcal{O}$. This follows because $P$ and
$Q$ are both shortest paths, so any subpath is a shortest path, and in
particular, both $x_{a}\dots,x_{b}$ and $y_{c},\dots,y_{d}$ are shortest paths
of the same length. In particular, this cycle has an even number of vertices.

Based on this observation, we can perform a simple surgery to ensure that in
fact $P\cup Q$ contains a unique cycle. In $Q$, replace $y_{1},\dots,y_{c-1}$
by $x_{1},\dots,x_{a-1}$ and replace $y_{d+1},\dots,y_{k}$ by
$x_{b+1},\dots,x_{c+1}$.

In summation, we have found two shortest paths $P=\\{x_{1},\dots,x_{k}\\}$ and
$Q=\\{y_{1},\dots,y_{k}\\}$ where $y_{i}\neq x_{i}$ iff $i\in[a+1,b-1]$.
Inside $P\cup Q$, there is a cycle
$\mathcal{O}=\\{x_{a},\dots,x_{b}\\}\cup\\{y_{a},\dots,y_{b}\\}$.

Now, this unique cycle cannot have fewer than 4 vertices because it has an
even number of vertices, so because $G$ is chordal, there must be some edge
$\\{x_{e},y_{f}\\}\in E(G)$, where $e,f\in[a+1,b-1]$. We wil call this edge a
chord of $\mathcal{O}$ Suppose that this chord is the edge $\\{x_{e},y_{e}\\}$
for some $e$. We claim that such an edge is not in any shortest paths from $v$
to $w$ in $C_{e}$.

Suppose otherwise, and that there was a path $z_{1},\dots,z_{k}$ where
$z_{c}=x_{e}$ and $z_{c+1}=y_{e}$. Clearly, either $c<e$ or $c+1>e$. If the
former is the case then $z_{1},\dots,z_{c}$ is a shorter path from $v$ to
$x_{e}$ than $x_{1},\dots,x_{e}$, and if the latter is the case, then
$z_{c+1},\dots,z_{k}$ is a shorter path from $y_{e}$ to $w$ than
$y_{e},\dots,y_{k}$. Either of these would be a contradiction.

Therefore, we suppose that the chord is of the form $\\{x_{e},y_{f}\\}$ for
$e\neq f$. In this case, we can either replace $Q$ by the shortest path
$x_{1},\dots,x_{e},y_{f},\dots,y_{k}$, or $P$ by the shortest path
$y_{1},\dots,y_{f},x_{e},\dots,x_{k}$. The difference in the number of
vertices between these two paths decreases in either case, so by doing this
operation repeatedly, we may assume that $P$ and $Q$ differ in exactly one
vertex, say $x_{\ell}\neq y_{\ell}$. In that case,
$\\{x_{\ell-1},x_{\ell},y_{\ell},y_{\ell+1}\\}$ contains a 4 cycle, which must
have a chord, and this chord must be $\\{x_{\ell},y_{\ell}\\}$, giving the
desired edge.

∎

###### Proof.

(of lemma 5.6) The basic idea in this proof is that any induced 4-cycle of $G$
cannot be contained in $C_{e}$ because $C_{e}$ is chordal, and hence, if it
contains any vertex of $C_{e}$, it must contain $T(e)$ and $H(e)$ as well.

We will need to divide this into 4 cases, depending on the length of the
shortest path from $T(e)$ to $H(e)$.

  1. (1)

The distance from $T(e)$ to $H(e)$ is 1 in $C_{e}$.

  2. (2)

The distance from $T(e)$ to $H(e)$ is 2 in $C_{e}$.

  3. (3)

The distance from $T(e)$ to $H(e)$ is 3 in $C_{e}$.

  4. (4)

The distance from $T(e)$ to $H(e)$ greater than 3 in $C_{e}$.

Case 1 is trivial; any edge in $C_{e}$ which is not $\\{T(e),H(e)\\}$ will
satisfy the conditions, as it is clearly not in a shortest path from $T(e)$ to
$H(e)$, and also any induced 4-cycle in $G$ would need to be contained in
$C_{e}$, which is chordal.

In case 2, we have some vertex $v\in C_{e}$ so that $\\{T(e),v\\}$ and
$\\{v,H(e)\\}$ are both in $C_{e}$. We notice that $\\{T(e),H(e)\\}$ is not
contained in $G$ in that case, because we assumed in our definition of
thickened graphs that all triangles in $G$ are contained in $C_{e}$ for some
$e$. Therefore, the only way for a vertex $v\in V(C_{e})$ to be contained in
an induced 4-cycle is if $\\{v,T(e)\\}$ and $\\{v,H(e)\\}$ are both edges of
$G$. Hence, it suffices to find an edge of $C_{e}$ not contained in any paths
of length 2 from $T(e)$ to $H(e)$, which follows from the previous lemma

In case 3, we again claim that as long as we find a vertex which is not on a
path of length 3 in $C_{e}$, then we are done. To see this, notice that a
4-cycle containing a vertex of $C_{e}$ would need to contain both $T(e)$ and
$H(e)$, and because there are no paths of length 2 from $T(e)$ to $H(e)$,
there must be a path of length 1 from $T(e)$ to $H(e)$. Because this edge is
not an edge of $C_{e}$, an edge of $C_{e}$ contained in a 4-cycle must be
contained in a path of length 3 from $T(e)$ to $H(e)$ in $C_{e}$. Thus, the
result follows from the previous lemma.

In our final case, once again, it suffices to appeal to the previous lemma,
simply because any 4 cycle containing $T(e)$ and $H(e)$ can include at most 2
other vertices, and there are no paths of with 2 vertices from $T(e)$ to
$H(e)$ in $C_{e}$. ∎

##  6\. Bounds on $\epsilon^{-}(G)$

######  Theorem 6.1 (Theorem 3.3).

$1-\frac{2}{\omega(G)}\leq\epsilon^{-}(G)\leq
1-\frac{2}{\operatorname*{tw}(G)+1}.$

###### Proof.

The key observation here is shown in [2], that if $C$ is a complete graph on
$n$ vertiecs, then $\epsilon^{-}(C)=1-\frac{2}{n}$ (though it is stated in a
slightly different language).

Let $C\subseteq G$ be a clique of size $n=\omega(G)$. It is clear that
$\epsilon^{-}(G)\leq\epsilon^{-}(C)=1-\frac{2}{n}$, as desired.

On the other hand, let $H$ be a chordal graph containing $H$ whose clique
number is at most $\operatorname*{tw}(G)+1$. Let $X\in\mathcal{P}^{-}(G)$, and
let $X^{\prime}\in\mathcal{P}^{-}(H)$ be any $H$-partial matrix so that
$X^{\prime}_{ij}=X_{ij}$ for $\\{i,j\\}\in E(G)$, and $X_{ij}=0$ otherwise.

If $C\subseteq H$ is any clique of $H$ of size $n$, then
$X^{\prime}|_{C}\in\mathcal{P}^{-}(C)$, so that

$X^{\prime}|_{C}+(1-\frac{2}{n})I_{C}\succeq 0.$

In particular, if we let $n=\operatorname*{tw}(G+1)=\omega(H)$, then we obtain
that for all cliques $C$ of $H$,
$(X^{\prime}+(1-\frac{2}{n})I_{H})|_{C}\succeq 0$.

Therefore, $X^{\prime}+(1-\frac{2}{\operatorname*{tw}(G)+1})I_{H}$ is an
$H$-partial matrix so that for every clique, $C\subseteq H$, the corresponding
submatrix is PSD. By the classic theorem in [6], this impies that
$X^{\prime}+(1-\frac{2}{\operatorname*{tw}(G)+1})I_{H}$ is PSD completable,
and in particular, $X+(1-\frac{2}{\operatorname*{tw}(G)+1})I_{G}$ is PSD
completable. ∎

###  6.1. Lengthening Graphs

Let $G$ be a graph, and let $G_{\ell}$ be the result of replacing each edge of
$G$ by a path with $\ell$ edges, so that $G_{1}=G$. Formally, we can define
$G_{\ell}$ as follows: for each edge $e=\\{u,v\\}\in E(G)$, we introduce
$\ell+1$ new vertices $x_{e,1},x_{e,2},\dots,x_{e,\ell+1}$, set $x_{e,1}=u$
and $x_{e,2}=v$, and include the edges $\\{x_{e,i},x_{e,{i+1}}\\}\in G_{\ell}$
for $i\in[\ell]$.

Notice though that for $\ell>1$, $G_{\ell}$ is triangle free; in particular,
$\mathcal{P}^{-}(G)=\mathcal{P}(G)$. For each $e\in G$, let $P_{e}$ be the
path of length $\ell$ that replaces the edge $e\in G$.

######  Theorem 6.2 (Theorem 3.4).

For $\ell>1$,

$\epsilon(G_{\ell})\leq\frac{\epsilon(\mathcal{O}_{\ell})\epsilon^{-}(G)}{\epsilon(\mathcal{O}_{\ell})+\epsilon^{-}(G)}.$

###### Proof.

The idea of the proof is this: consider the graph $H=G_{\ell}\cup G$. We see
that $H$ is the union of a number of cycles of the form
$\mathcal{O}_{e}=P_{e}\cup e$. We can think of this as being $H$ as being the
result of performing clique sums of $G$ with a cycle of length $\ell+1$ for
each edge.

Then, given $X\in\mathcal{P}^{-}(G_{\ell})$, we first complete $X$ to
$X^{\prime}\in\mathcal{P}^{-}(H)$, in such a way that for each edge $e\in G$,
we can have a lower bound on the minimum eigenvalue of the submatrix $X|_{e}$.
It is clear that this should make it easier in some sense to complete
$X^{\prime}|_{G}$, but doing this may make completing
$X^{\prime}|_{\mathcal{O}_{e}}$ harder.

We then must balance the cost of completing the various cycles of $H$ with the
cost of completing $X^{\prime}|_{G}$.

So, fix some $X\in\mathcal{P}^{-}(G_{\ell})$ with $\operatorname*{tr}(X)=1$,
and assume that $X$ is extreme, so that $X|_{\\{i,j\\}}$ is rank 1 for all
$\\{i,j\\}\in E(G_{\ell})$.

Now, for each $e\in E(G)$, there is a unique PSD completion of $X|_{P_{e}}$,
which is rank 1. Let $x_{e}$ be the entry of this completion associated with
the edge $e\in E(G)$.

Consider the partial matrix $X^{\prime}\in\mathcal{P}(H)$ where
$X^{\prime}_{ij}=X_{ij}$ for $\\{i,j\\}\in E(G_{\ell})$, and where
$X_{ij}^{\prime}=(1-\delta)x_{\\{i,j\\}}$ for $\\{i,j\\}\in E(G)$, where
$\delta$ is to be chosen later.

We want to make two claims:

######  Lemma 6.3.

For each $e\in E(G)$, let $\mathcal{O}_{e}$ be the cycle obtained by taking
$e\cup P_{e}$, then

$\epsilon_{\mathcal{O}_{e}}(X^{\prime}|_{\mathcal{O}_{e}})\leq\delta\frac{\epsilon(\mathcal{O}_{\ell})}{2}.$

######  Lemma 6.4.

$\epsilon_{G}(X^{\prime}|_{V(G)})\leq(1-\delta)\epsilon^{-}(G).$

If we let
$\epsilon=\max\\{\delta\epsilon(\mathcal{O}_{e}),(1-\delta)\epsilon^{-}(G)\\}$,
then consider $X^{\prime}+\epsilon I_{H}$. Our construction implies that
$(X^{\prime}+\epsilon I_{H})|_{\mathcal{O}_{e}}$ is PSD completable for all
$e$, and $(X^{\prime}+\epsilon I_{H})|_{G}$ is PSD completable. Since $H$ is a
clique sum of $G$ and the $\mathcal{O}_{e}$, by Theorem 7 in [3], we have that
$X^{\prime}+\epsilon I_{H}$ is PSD completable. In particular, this implies
that $X+\epsilon I_{G_{\ell}}$ is PSD completable.

Optimizing for the value of $\epsilon$ with respect to $\delta$, we obtain
that it suffices if

$\epsilon=\frac{\epsilon(\mathcal{O}_{\ell})\epsilon^{-}(G)}{\epsilon(\mathcal{O}_{\ell})+2\epsilon^{-}(G)}.$

This is what we wanted. ∎

###### Proof.

(of lemma 6.3) Firstly, we will reindex $X^{\prime}|_{\mathcal{O}_{e}}$, so
that the vertices of $\mathcal{O}_{e}$ are $1,\dots,\ell+1$.

If we consider $X^{\prime}|_{P_{e}}$, we see that this is a $P_{e}$-partial
matrix where all of the specified $2\times 2$ minors are rank 1. Because
$P_{e}$ is chordal, $X^{\prime}|_{P_{e}}$ is PSD completable, and any PSD
completion must have rank 1. Call this PSD completion $\hat{Q}$, and let $Q$
be the $\mathcal{O}_{e}$-partial matrix obtained by projecting $Q$ onto the
edges of $\mathcal{O}_{e}$.

Now, let $A=X^{\prime}|_{\mathcal{O}_{e}}$, and notice that we defined
$A_{1,\ell+1}$ to be $(1-\delta)Q_{1,\ell+1}$. Let $Z$ be the
$\mathcal{O}_{e}$-partial matrix where $Z_{ij}=A_{ij}$ unless
$\\{i,j\\}=\\{1,\ell+1\\}$, and $Z_{1,\ell+1}=-Q_{1,\ell+1}$. Also, notice
that $Z\in\mathcal{P}(\mathcal{O}_{e})$, which can be easily checked by
noticing that for $2\times 2$ PSD matrices, we can negate the off-diagonal
entry and it will still be PSD. Moreover,
$\operatorname*{tr}(Z)=\operatorname*{tr}(A)\leq\operatorname*{tr}(X^{\prime})=1$.
Therefore, $\epsilon_{\mathcal{O}_{e}}(Z)\leq\epsilon(\mathcal{O}_{e})$.

We see that $A=(1-\frac{\delta}{2})Q+\frac{\delta}{2}Z$, and therefore,
because $\epsilon_{\mathcal{O}_{e}}(X)$ is concave,

$\epsilon_{\mathcal{O}_{e}}(A)\leq(1-\frac{\delta}{2})\epsilon_{\mathcal{O}_{e}}(Q)+\frac{\delta}{2}\epsilon_{\mathcal{O}_{e}}(Z)\leq\frac{\delta}{2}\epsilon(\mathcal{O}_{e}).$

∎

###### Proof.

(of lemma 6.4) Let $A=X^{\prime}|_{G}$. $A$ is defined so that
$A_{ii}=X_{ii}$, and for $\\{i,j\\}\in E(G)$, $A_{ij}=(1-\delta)x_{ij}$, where
$x_{ij}$ is such that

$\begin{pmatrix}A_{ii}&x_{ij}\\\ x_{ij}&A_{jj}\end{pmatrix}.$

Consider the $G$-partial matrix $Q$ where $Q_{ii}=A_{ii}$ and $Q_{ij}=x_{ij}$
for $\\{i,j\\}\in E(G)$.
$\operatorname*{tr}(Q)=\operatorname*{tr}(X|_{G})\leq\operatorname*{tr}(X)=1$,
so that $\epsilon_{G}(Q)\leq\epsilon^{-}(G)$.

On the other hand, let $D$ be the $G$-partial matrix where $D_{ii}=A_{ii}$ for
$i\in V(G)$, and $D_{ij}=0$ otherwise. This is clearly completable to a
positive semidefinite diagonal matrix. We see that $A=\delta D+(1-\delta)Q$,
so that by concavity we obtain

$\epsilon_{G}(A)\leq\delta\epsilon_{G}(D)+(1-\delta)\epsilon_{G}(Q)\leq(1-\delta)\epsilon^{-}(G).$

∎

## References

  * [1] Wayne Barrett, Charles R. Johnson, and Pablo Tarazaga.  The real positive definite completion problem for a simple cycle.  Linear Algebra and its Applications, 192:3 – 31, 1993.
  * [2] Grigoriy Blekherman, Santanu S. Dey, Kevin Shu, and Shengding Sun.  Hyperbolic relaxation of $k$-locally positive semidefinite matrices, 2020\.
  * [3] Grigoriy Blekherman and Kevin Shu.  Sums of squares and sparse semidefinite programming, 2020.
  * [4] Yixin Cao and R.B. Sandeep.  Minimum fill-in: Inapproximability and almost tight lower bounds.  Information and Computation, 271:104514, 2020.
  * [5] Mituhiro Fukuda, Masakazu Kojima, Kazuo Murota, and Kazuhide Nakata.  Exploiting sparsity in semidefinite programming via matrix completion i: General framework.  SIAM Journal on Optimization, 11, 02 1970.
  * [6] Robert Grone, Charles R. Johnson, Eduardo M. Sá, and Henry Wolkowicz.  Positive definite completions of partial hermitian matrices.  Linear Algebra and its Applications, 58:109 – 124, 1984.
  * [7] Allen Hatcher.  Algebraic topology.  Cambridge Univ. Press, Cambridge, 2000.
  * [8] Monique Laurent.  The real positive semidefinite completion problem for series-parallel graphs.  Linear Algebra Appl., 252:347–366, 1997.
  * [9] Monique Laurent and Antonios Varvitsiotis.  The gram dimension of a graph.  In International Symposium on Combinatorial Optimization, pages 356–367. Springer, 2012.
  * [10] Monique Laurent and Antonios Varvitsiotis.  Positive semidefinite matrix completion, universal rigidity and the strong arnold property.  Linear Algebra and its Applications, 452:292–317, 2014.
  * [11] Kevin Shu.  Extreme nonnegative quadratics over stanley reisner varieties, 2021.
  * [12] Yang Zheng, Giovanni Fantuzzi, and Antonis Papachristodoulou.  Chordal and factor-width decompositions for scalable semidefinite and polynomial optimization, 2021.