  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.
