# Sum-of-Squares Lower Bounds for Sparse Independent Set

Chris Jones, Aaron Potechin, Goutham Rajendran, Madhur Tulsiani, Jeff Xu
Chris Jones University of Chicago<EMAIL_ADDRESS>Supported in part by NSF
grant CCF-2008920. Aaron Potechin University of Chicago.
<EMAIL_ADDRESS>Supported in part by NSF grant CCF-2008920. Goutham
Rajendran University of Chicago<EMAIL_ADDRESS>Supported in part by
NSF grant CCF-1816372. Madhur Tulsiani Toyota Technological Institute at
Chicago<EMAIL_ADDRESS>Supported by NSF grant CCF-1816372. Jeff Xu
Carnegie Mellon University<EMAIL_ADDRESS>Supported by NSF CAREER
Award #2047933.

###### Abstract

The Sum-of-Squares (SoS) hierarchy of semidefinite programs is a powerful
algorithmic paradigm which captures state-of-the-art algorithmic guarantees
for a wide array of problems. In the average case setting, SoS lower bounds
provide strong evidence of algorithmic hardness or information-computation
gaps. Prior to this work, SoS lower bounds have been obtained for problems in
the “dense" input regime, where the input is a collection of independent
Rademacher or Gaussian random variables, while the sparse regime has remained
out of reach. We make the first progress in this direction by obtaining strong
SoS lower bounds for the problem of Independent Set on sparse random graphs.
We prove that with high probability over an Erdős-Rényi random graph $G\sim
G_{n,\frac{d}{n}}$ with average degree $d>\log^{2}n$, degree-$D_{\text{SoS}}$
SoS fails to refute the existence of an independent set of size
$k=\Omega\left(\frac{n}{\sqrt{d}(\log n)(D_{\text{SoS}})^{c_{0}}}\right)$ in
$G$ (where $c_{0}$ is an absolute constant), whereas the true size of the
largest independent set in $G$ is $O\left(\frac{n\log d}{d}\right)$.

Our proof involves several significant extensions of the techniques used for
proving SoS lower bounds in the dense setting. Previous lower bounds are based
on the pseudo-calibration heuristic of Barak et al. [FOCS 2016] which produces
a candidate SoS solution using a planted distribution indistinguishable from
the input distribution via low-degree tests. In the sparse case the natural
planted distribution _does_ admit low-degree distinguishers, and we show how
to adapt the pseudo-calibration heuristic to overcome this.

Another notorious technical challenge for the sparse regime is the quest for
matrix norm bounds. In this paper, we obtain new norm bounds for _graph
matrices_ in the sparse setting. While in the dense setting the norms of graph
matrices are characterized by the size of the minimum vertex separator of the
corresponding graph, this turns not to be the case for sparse graph matrices.
Another contribution of our work is developing a new combinatorial
understanding of structures needed to understand the norms of sparse graph
matrices.

###### Contents

  1. 1 Introduction
    1. 1.1 Our main results
    2. 1.2 Our approach
    3. 1.3 Related work
    4. 1.4 Organization of the paper
  2. 2 Technical Preliminaries
    1. 2.1 The Sum-of-Squares hierarchy
    2. 2.2 $p$-biased Fourier analysis
    3. 2.3 Ribbons and graph matrices
  3. 3 An overview of the proof techniques
    1. 3.1 Modified pseudocalibration
    2. 3.2 Approximate PSD decompositions, norm bounds and conditioning
  4. 4 Pseudocalibration with connected truncation
    1. 4.1 Pseudo-calibration
    2. 4.2 The failure of "Just try pseudo-calibration"
    3. 4.3 Salvaging the doomed
  5. 5 Norm bounds and factoring
    1. 5.1 Norm bounds
    2. 5.2 Factoring ribbons and shapes
  6. 6 PSD-ness
    1. 6.1 Overview of the approximate PSD decomposition
    2. 6.2 Informal sketch for bounding $\tau$ and $\tau_{P}$
    3. 6.3 Decomposition in terms of ribbons
    4. 6.4 Factor out $\Pi$ and edges incident to $U_{\alpha}\cap V_{\alpha}$
    5. 6.5 Conditioning I: reduction to sparse shapes
    6. 6.6 Shifting to shapes
    7. 6.7 Counting shapes with the tail bound function $c(\alpha)$
    8. 6.8 Statement of main lemmas
    9. 6.9 Conditioning II: Frobenius norm trick
    10. 6.10 Norm bounds
    11. 6.11 Proof of main lemmas
  7. 7 Open Problems
  8. A Trace Power Calculations
  9. B Reserving edges to preserve left/middle shapes
  10. C Second proof of Lemma 6.9
  11. D Formalizing the PSD Decomposition

##  1 Introduction

The Sum-of-Squares (SoS) hierarchy is a powerful convex programming technique
that has led to successful approximation and recovery algorithms for various
problems in the past decade. SoS captures the best-known approximation
algorithms for several classical combinatorial optimization problems. Some of
the additional successes of SoS also include Tensor PCA [HSS15, MSS16] and
Constraint Satisfaction Problems with additional structure [BRS11, GS11]. SoS
is a family of convex relaxations parameterized by degree; by taking larger
degree, one gets a better approximation to the true optimum at the expense of
a larger SDP instance. Thus we are interested in the tradeoff between degree
and approximation quality. For an introduction to Sum-of-Squares algorithms,
see [BS16, FKP19].

The success of SoS on the upper bound side has also conferred on it an
important role for the investigation of algorithmic hardness. Lower bounds for
the SoS hierarchy provide strong unconditional hardness results for several
optimization problems and are of particular interest when NP-hardness results
are unavailable. An important such setting is the study of average case
complexity of optimization problems, where relatively few techniques exist for
establishing NP-hardness results [ABB19]. In this setting, a study of the SoS
hierarchy not only provides a powerful benchmark for average-case complexity,
but also helps in understanding the structural properties of the problems:
what makes them algorithmically challenging? Important examples of such
results include an improved understanding of sufficient conditions for
average-case hardness of CSPs [KMOW17] and lower bounds for the planted clique
problem [BHK+16].

An important aspect of previous lower bounds for the SoS hierarchy is that
they apply for the so-called _dense setting_ , which corresponds to cases when
the input distribution can be specified by a collection of independent
Rademacher or Gaussian variables. In the case of planted clique, this
corresponds to the case when the input is a random graph distributed according
to $G_{n,\frac{1}{2}}$ i.e. specified by a collection of $\binom{n}{2}$
independent Rademacher variables. In the case of CSPs, one fixes the structure
of the lower bound instance and only considers an instance to be specified by
the signs of the literals, which can again be taken as uniformly random
$\\{-1,1\\}$ variables. Similarly, recent results by a subset of the authors
[PR20] for tensor PCA apply when the input tensor has independent Rademacher
or Gaussian entries. The techniques used to establish these lower bounds have
proved difficult to extend to the case when the input distribution naturally
corresponds to a _sparse graph_ (or more generally, when it is specified by a
collection of independent sub-gaussian variables, with Orlicz norm $\omega(1)$
instead of $O(1)$).

In this paper we are interested in extending lower bound technology for SoS to
the sparse setting, where the input is a graph with average degree $d\leq
n/2$. We use as a case study the fundamental combinatorial optimization
problem of independent set. For the dense case $d=n/2$, finding an independent
set is equivalent to finding a clique and the paper [BHK+16] shows an average-
case lower bound against the Sum-of-Squares algorithm. We extend the
techniques introduced there, namely pseudocalibration, graph matrices, and the
approximate decomposition into positive semidefinite matrices, in order to
show the first average-case lower bound for the sparse setting. We hope that
the techniques developed in this paper offer a gateway for the analysis of SoS
on other sparse problems. Section 7 lists several such problems that are
likely to benefit from an improved understanding of the sparse setting.

Sample $G\sim G_{n,\frac{d}{n}}$ as an Erdős-Rényi random
graph111Unfortunately our techniques do not work for a random $d$-regular
graph. See the open problems (Section 7). with average degree $d$, where we
think of $d\ll n$. Specializing to the problem of independent set, a maximum
independent set in $G$ has size:

######  Fact 1.1 ([COE15, DM11, DSS16]).

W.h.p. the max independent set in $G$ has size $(1+o_{d}(1))\cdot\frac{2\ln
d}{d}\cdot n$.

The value of the degree-2 SoS relaxation for independent set equals the Lovász
$\vartheta$ function, which is an upper bound on the independence number
$\alpha(G)$, by virtue of being a relaxation. For random graphs $G\sim
G_{n,d/n}$ this value is larger by a factor of about $\sqrt{d}$ than the true
value of $\alpha(G)$ with high probability.

######  Fact 1.2 ([CO05]).

W.h.p. $\vartheta(G)=\Theta(\frac{n}{\sqrt{d}})$.

We will prove that the value of higher-degree SoS is also on the order of
$n/\sqrt{d}$, rather than $n/d$, and thereby demonstrate that the information-
computation gap against basic SDP/spectral algorithms persists against higher-
degree SoS.

###  1.1 Our main results

The solution to the convex relaxations obtained via the SoS hierarchy can be
specified by the so-called “pseudoexpectation operator".

######  Definition 1.3 (Pseudoexpectation).

A degree-$D$ pseudoexpectation operator
$\operatorname{\widetilde{{\mathbb{E}}}}$ is a linear functional on
polynomials of degree at most $D$ (in $n$ variables) such that
$\operatorname{\widetilde{{\mathbb{E}}}}[1]=1$ and
$\operatorname{\widetilde{{\mathbb{E}}}}[f^{2}]\geq 0$ for every polynomial
$f$ with degree at most $D/2$. A pseudoexpectation is said to satisfy a
polynomial constraint $g=0$ if $\operatorname{\widetilde{{\mathbb{E}}}}[f\cdot
g]=0$ for all polynomials $f$ when $\deg(f\cdot g)\leq D$.

In considering relaxations for independent set of a graph $G=(V,E)$, with
variables $x_{v}$ being the $0/1$ indicators of the independent set, the SoS
relaxation searches for pseudoexpectation operators satisfying the polynomial
constraints

$\forall v\in V.\quad
x_{v}^{2}=x_{v}\qquad\quad\text{and}\quad\qquad\forall(u,v)\in E.\quad
x_{u}x_{v}=0\,.$

The objective value of the convex relaxation is given by the quantity
$\operatorname{\widetilde{{\mathbb{E}}}}[\sum_{v\in V}x_{v}]=\sum_{v\in
V}\operatorname{\widetilde{{\mathbb{E}}}}[x_{v}]$. For the results below, we
say that an event occurs with high probability (w.h.p.) when it occurs with
probability at least $1-O(1/n^{c})$ for some $c>0$. The following theorem
states our main result.

######  Theorem 1.4.

There is an absolute constant $c_{0}\in{\mathbb{N}}$ such that for
sufficiently large $n\in{\mathbb{N}}$ and ${d\in[(\log n)^{2},n^{0.5}]}$, and
parameters $k,D_{\text{SoS}}$ satisfying

$k~{}\leq~{}\frac{n}{D_{\text{SoS}}^{c_{0}}\cdot\log n\cdot d^{1/2}}\,,$

it holds w.h.p. for $G=(V,E)~{}\sim~{}G_{n,~{}d/n}$ that there exists a
degree-$D_{\text{SoS}}$ pseudoexpectation satisfying

$\forall v\in V.\quad
x_{v}^{2}=x_{v}\qquad\quad\text{and}\quad\qquad\forall(u,v)\in E.\quad
x_{u}x_{v}=0\,,$

and objective value $\operatorname{\widetilde{{\mathbb{E}}}}[\sum_{v\in
V}x_{v}]~{}\geq~{}(1-o(1))k$.

######  Remark 1.5.

This is a non-trivial lower bound whenever
$D_{\text{SoS}}~{}\leq~{}\left(\frac{d^{1/2}}{\log n}\right)^{1/c_{0}}$.

######  Remark 1.6.

It suffices to set $c_{0}=20$ for our current proof. We did not optimize the
tradeoff in $D_{\text{SoS}}$ with $k$, but we did optimize the log factor
(with the hope of eventually removing it).

######  Remark 1.7.

Using the same technique, we can prove an $n^{\Omega(\varepsilon)}$ SoS-degree
lower bound for all $d\in[\sqrt{n},n^{1-\varepsilon}]$.

For $n^{\varepsilon}\leq d\leq n^{0.5}$, the theorem gives a polynomial
$n^{\delta}$ SoS-degree lower bound. For smaller $d$, the bound is still
strong against low-degree SoS, but it becomes trivial as $D_{\text{SoS}}$
approaches $(d^{1/2}/\log n)^{1/c_{0}}$ or $d$ approaches $(\log n)^{2}$ since
$k$ matches the size of the maximum independent set in $G$, hence there is an
actual distribution over independent sets of this size (the expectation
operator for which is trivially is also a pseudoexpectation operator).

The above bound says nothing about the “almost dense” regime
$d\in[n^{1-\varepsilon},n/2]$. To handle this regime, we observe that our
techniques, along with the ideas from the $\Omega(\log n)$-degree SoS bound
from [BHK+16] for the dense case, prove a lower bound for any degree $d\geq
n^{\varepsilon}$.

######  Theorem 1.8.

For any $\varepsilon_{1},\varepsilon_{2}>0$ there is $\delta>0$, such that for
$d\in[n^{\varepsilon_{1}},n/2]$ and $k\leq\frac{n}{d^{1/2+\varepsilon_{2}}}$,
it holds w.h.p. for $G=(V,E)~{}\sim~{}G_{n,~{}d/n}$ that there exists a
degree-$(\delta\log d)$ pseudoexpectation satisfying

$\forall v\in V.\quad
x_{v}^{2}=x_{v}\qquad\quad\text{and}\quad\qquad\forall(u,v)\in E.\quad
x_{u}x_{v}=0\,,$

and objective value $\operatorname{\widetilde{{\mathbb{E}}}}[\sum_{v\in
V}x_{v}]~{}\geq~{}(1-o(1))k$.

In particular, these theorems rule out polynomial-time certification (i.e.
constant degree SoS) for any $d\geq{\mathrm{polylog}}(n)$.

###  1.2 Our approach

Proving lower bounds for the case of sparse graphs requires extending the
previous techniques for SoS lower bounds in multiple ways. The work closest to
ours is the planted clique lower bound of [BHK+16]. The idea there is to view
a random graph $G\sim G_{n,~{}1/2}$ as a random input in
$\\{-1,1\\}^{\binom{n}{2}}$, and develop a canonical method called
“pseudocalibration" for obtaining the pseudoexpectation
$\operatorname{\widetilde{{\mathbb{E}}}}$ as a function of $G$. The
pseudocalibration method takes the low-degree Fourier coefficients of $\mu$
based on a _different_ distribution on inputs $G$ (with large planted
cliques), and takes higher degree coefficients to be zero. This is based on
the heuristic that distribution $G_{n,~{}1/2}$ and the planted distribution
are indistinguishable by low-degree tests. The pseudoexpectation obtained via
this heuristic is then proved to be PSD (i.e., to satisfy
$\operatorname{\widetilde{{\mathbb{E}}}}[f^{2}]\geq 0$) by carefully
decomposing its representation as a (moment) matrix $\Lambda$. One then needs
to estimate the norms of various terms in this decomposition, known as “graph
matrices", which are random matrices with entries as low-degree polynomials
(in $\\{-1,1\\}^{\binom{n}{2}}$), and carefully group terms together to form
PSD matrices.

Each of the above components require a significant generalization in the
sparse case. To begin with, there is no good planted distribution to work
with, as the natural planted distribution (with a large planted independent
set) _is distinguishable from $G_{n,~{}d/n}$ via low-degree tests_! While we
still use the natural planted distribution to compute _some_ pseudocalibrated
Fourier coefficients, we also truncate (set to zero) several low-degree
Fourier coefficients, in addition to the high-degree coefficients as in
[BHK+16]. In particular, when the Fourier coefficients correspond to subgraphs
where certain vertex sets are disconnected (viewed as subsets of
$\binom{n}{2}$), we set them to zero. This is perhaps the most conceptually
interesting part of the proof, and we hope that the same “connected
truncation” will be useful for other integrality gap constructions.

The technical machinery for understanding norm bounds, and obtaining PSD
terms, also requires a significant update in the sparse case. Previously, norm
bounds for graph matrices were understood in terms of minimum vertex
separators for the corresponding graphs, and arguments for obtaining PSD terms
required working with the combinatorics of vertex separators [AMP20]. However,
the number of vertices in a vertex separator turns out to be insufficient to
control the relevant norm bounds in the sparse case. This is because of the
fact that unlike random $\pm 1$ variables, their $p$-biased analogs no longer
have Orlicz norm $O(1)$ but instead $O(\frac{1}{\sqrt{p}})$, which results in
both the vertices as well as edges in the graph playing a role in the norm
bounds. We then characterize the norms of the relevant random matrices in
terms of vertex separators, where the cost of a separator depends on the
number of vertices and also the number of induced edges. Moreover, the
estimates on spectral norms obtained via the trace power method can fluctuate
significantly due to rare events (presence of some dense subgraphs), and we
need to carefully condition on the absence of these events. A more detailed
overview of our approach is presented in Section 3.

###  1.3 Related work

Several previous works prove SoS lower bounds in the dense setting, when the
inputs can be viewed as independent Gaussian or Rademacher random variables.
Examples include the planted clique lower bound of Barak et al. [BHK+16], CSP
lower bounds of Kothari et al. [KMOW17], and the tensor PCA lower bounds
[HKP+17, PR20]. The technical component of decomposing the moment matrix in
the dense case, as a sum of PSD matrices, is developed into a general
“machinery" in a recent work by a subset of the authors [PR20]. A different
approach than the ones based on pseudocalibration, which also applies in the
dense regime, was developed by Kunisky [Kun20].

For the case of independent set in random sparse graphs, many works have
considered the _search_ problem of finding a large independent set in a random
sparse graph. Graphs from $G_{n,d/n}$ are known to have independent sets of
size $(1+o_{d}(1))\cdot\frac{2\ln d}{d}\cdot n$ with high probability, and it
is possible to find an independent set of size
$(1~{}+~{}o_{d}(1))\cdot\frac{\ln d}{d}~{}\cdot~{}n$, either by greedily
taking a maximal independent set in the dense case [GM75] or by using a local
algorithm in the sparse case [Wor95]. This is conjectured to be a
computational phase transition, with concrete lower bounds against search
beyond $\frac{\ln d}{d}\cdot n$ for local algorithms [RV17] and low-degree
polynomials [Wei20]. The game in the search problem is all about the constant
1 vs 2, whereas our work shows that the integrality gap of SoS is
significantly worse, on the order of $\sqrt{d}$. Lower bounds against search
work in the regime of constant $d$ (though in principle they could be extended
to at least some $d=\omega(1)$ with additional technical work), while our
techniques require $d\geq\log(n)$. For search problems, the _overlap
distribution_ of two high-value solutions has emerged as a heuristic indicator
of computational hardness, whereas for certification problems it is unclear
how the overlap distribution plays a role.

Norm bounds for sparse graph matrices were also obtained using a different
method of matrix deviation inequalities, by a subset of the authors [RT20].

The work [BBK+20] constructs a computationally quiet planted distribution that
is a candidate for pseudocalibration. However, their distribution is not quite
suitable for our purposes. 222[BBK+20] provide evidence that their
distribution is hard to distinguish from $G_{n,d/n}$ with probability $1-o(1)$
(it is not “strongly detectable”). However, their distribution _is_
distinguishable with probability $\Omega(1)$, via a triangle count (it is
“weakly detectable”). In SoS pseudocalibration, this manifests as
$\operatorname{\widetilde{{\mathbb{E}}}}[1]=\Theta_{d}(1)$. We would like the
low-degree distinguishing probability to be $o(1)$ i.e.
$\operatorname{\widetilde{{\mathbb{E}}}}[1]=1+o_{d}(1)$ so that normalizing by
$\operatorname{\widetilde{{\mathbb{E}}}}[1]$ does not affect the objective
value. 333Another issue is that their planted distribution introduces noise by
adding a small number of edges inside the planted independent set.

A recent paper by Pang [Pan21] fixes a technical shortcoming of [BHK+16] by
constructing a pseudoexpectation operator that satisfies “$\sum_{v\in
V}x_{v}=k$” as a polynomial constraint (whereas the shortcoming was
$\operatorname{\widetilde{{\mathbb{E}}}}[\sum_{v\in V}x_{v}]\geq(1-o(1))k$
like we have here).

###  1.4 Organization of the paper

In Section 2, we introduce the technical preliminaries and notation required
for our arguments. A technical overview of our proof strategy is presented in
Section 3. Section 4 describes our modification of the pseudo-calibration
heuristic using additional truncations. Norm bounds for sparse graph matrices
are obtained in Section 5. Section 6 then proves the PSD-ness of our SoS
solutions broadly using the machinery developed in [BHK+16] and [PR20].

##  2 Technical Preliminaries

###  2.1 The Sum-of-Squares hierarchy

The Sum-of-Squares (SoS) hierarchy is a hierarchy of semidefinite programs
parameterized by its degree $D$. We will work with two equivalent definitions
of a degree-$D$ SoS solution: a pseudoexpectation operator
$\operatorname{\widetilde{{\mathbb{E}}}}$ (Definition 1.3) and a moment
matrix. For a degree-$D$ solution to be well defined, we need $D$ to be at
least the maximum degree of all constraint polynomials. The degree-$D$ SoS
algorithm checks feasibility of a polynomial system by checking whether or not
a degree-$D$ pseudoexpectation operator exists. This can be done in time
$n^{O(D)}$ via semidefinite programming (ignoring some issues of bit
complexity [RW17]). To show an SoS lower bound, one must construct a
pseudoexpectation operator that exhibits the desired integrality gap.

####  2.1.1 Moment matrix

We define the moment matrix associated with a degree-$D$ pseudoexpectation
$\operatorname{\widetilde{{\mathbb{E}}}}$.

######  Definition 2.1 (Moment Matrix of
$\operatorname{\widetilde{{\mathbb{E}}}}$).

The moment matrix $\Lambda=\Lambda(\operatorname{\widetilde{{\mathbb{E}}}})$
associated to a pseudoexpectation $\operatorname{\widetilde{{\mathbb{E}}}}$ is
a $\binom{[n]}{\leq D/2}\times\binom{[n]}{\leq D/2}$ matrix with rows and
columns indexed by subsets of $I,J\subseteq[n]$ of size at most $D/2$ and
defined as

$\Lambda[I,J]:=\operatorname{\widetilde{{\mathbb{E}}}}\left[x^{I}\cdot
x^{J}\right].$

To show that a candidate pseudoexpectation satisfies
$\operatorname{\widetilde{{\mathbb{E}}}}[f^{2}]\geq 0$ in Definition 1.3, we
will rely on the following standard fact.

######  Fact 2.2.

In the definition of pseudoexpectation, Definition 1.3, the condition
$\operatorname{\widetilde{{\mathbb{E}}}}[f^{2}]\geq 0$ for all $\deg(f)\leq
D/2$ is equivalent to $\Lambda\succeq 0$.

###  2.2 $p$-biased Fourier analysis

Since we are interested in sparse Erdös-Rényi graphs in this work, we will
resort to $p$-biased Fourier analysis [O’D14, Section 8.4]. Formally, we view
the input graph $G\sim G_{n,p}$ as a vector in $\\{0,1\\}^{\binom{n}{2}}$
indexed by sets $\\{i,j\\}$ for $i,j\in[n],i\neq j$, where each entry is
independently sampled from the $p$-biased Bernoulli distribution,
$\operatorname{Bernoulli}(p)$. Here, by convention $G_{e}=1$ indicates the
edge $e$ is present, which happens with probability $p$. The Fourier basis we
use for analysis on $G$ is the set of $p$-biased Fourier characters (which are
naturally indexed by graphs $H$ on $[n]$).

######  Definition 2.3.

$\chi$ denotes the $p$-biased Fourier character,

$\chi(0)=\sqrt{\frac{p}{1-p}},\qquad\chi(1)=-\sqrt{\frac{1-p}{p}}.$

For $H$ a subset or multi-subset of $\binom{[n]}{2}$, let
$\chi_{H}(G):=\prod_{e\in H}\chi(G_{e})$.

We will also need the function $1-G_{e}$ which indicates that an edge is not
present.

######  Definition 2.4.

For $H\subseteq\binom{[n]}{2}$, let $1_{\overline{H}}(G)=\prod_{e\in
H}(1-G_{e})$.

When $H$ is a clique, this is the independent set indicator for the vertices
in $H$.

######  Proposition 2.5.

For $e\in\\{0,1\\}$, $1+\sqrt{\frac{p}{1-p}}\chi(e)=\frac{1}{1-p}(1-e)$.
Therefore, for any $H\subseteq\binom{[n]}{2}$,

$\sum_{T\subseteq H}\left(\frac{p}{1-p}\right)^{\left\lvert
T\right\rvert/2}\chi_{T}(G)=\frac{1}{(1-p)^{\left\lvert H\right\rvert}}\cdot
1_{\overline{H}}(G).$

###  2.3 Ribbons and graph matrices

A degree-$D$ pseudoexpectation operator is a vector in
${\mathbb{R}}^{\binom{[n]}{\leq D}}$. The matrices we consider will have rows
and columns indexed by all subsets of $[n]$. We express the moment matrix
$\Lambda$ in terms of the Fourier basis on $G_{n,p}$. A particular Fourier
character in a particular matrix entry is identified by a combinatorial
structure called a ribbon.

######  Definition 2.6 (Ribbon).

A ribbon is a tuple $R=(V(R),E(R),A_{R},B_{R})$, where $(V(R),E(R))$ is an
undirected multigraph without self-loops, $V(R)\subseteq[n]$, and
$A_{R},B_{R}\subseteq V(R)$. Let $C_{R}:=V(R)\setminus(A_{R}\cup B_{R})$.

######  Definition 2.7 (Matrix for a ribbon).

For a ribbon $R$, the matrix $M_{R}$ has rows and columns indexed by all
subsets of $[n]$ and has a single nonzero entry,

$M_{R}[I,J]=\begin{cases}\displaystyle\chi_{E(R)}(G)&I=A_{R},J=B_{R}\\\
0&\text{Otherwise}\end{cases}$

######  Definition 2.8 (Ribbon isomorphism).

Two ribbons $R,S$ are isomorphic, or have the same shape, if there is a
bijection between $V(R)$ and $V(S)$ which is a multigraph isomorphism between
$E(R),E(S)$ and is a bijection from $A_{R}$ to $A_{S}$ and $B_{R}$ to $B_{S}$.
Equivalently, letting $S_{n}$ permute the vertex labels of a ribbon, the two
ribbons are in the same $S_{n}$-orbit.

If we ignore the labels on the vertices of a ribbon, what remains is the shape
of the ribbon.

######  Definition 2.9 (Shape).

A shape is an equivalence class of ribbons with the same shape. Each shape has
associated with it a representative
$\alpha=(V(\alpha),E(\alpha),U_{\alpha},V_{\alpha})$, where
$U_{\alpha},V_{\alpha}\subseteq V(\alpha)$. Let
$W_{\alpha}:=V(\alpha)\setminus(U_{\alpha}\cup V_{\alpha}).$

######  Definition 2.10 (Embedding).

Given a shape $\alpha$ and an injective function
$\varphi:V(\alpha)\rightarrow[n],$ we let $\varphi(\alpha)$ be the ribbon
obtained by labeling $\alpha$ in the natural way.

######  Definition 2.11 (Graph matrix).

For a shape $\alpha$, the graph matrix $M_{\alpha}$ is

$M_{\alpha}=\displaystyle\sum_{\text{injective
}\varphi:V(\alpha)\rightarrow[n]}M_{\varphi(\alpha)}.$

Injectivity is an important property of graph matrices. On the one hand, we
have a finer partition of ribbons than allowing all assignments, and this
allows more control. On the other hand, injectivity introduces technically
challenging “intersection terms” into graph matrix multiplication. A graph
matrix is essentially a sum over all ribbons with shape $\alpha$ (this is not
entirely accurate as each ribbon will be repeated
$\left\lvert\operatorname{Aut}(\alpha)\right\rvert$ times).

######  Definition 2.12 (Automorphism).

For a shape $\alpha$, $\operatorname{Aut}(\alpha)$ is the group of bijections
from $V(\alpha)$ to itself such that $U_{\alpha}$ and $V_{\alpha}$ are fixed
as sets and the map is a multigraph automorphism on $E(\alpha)$. Equivalently,
$\operatorname{Aut}(\alpha)$ is the stabilizer subgroup (of $S_{n}$) of any
ribbon of shape $\alpha$.

######  Fact 2.13.

$M_{\alpha}=\sum_{\text{injective
}\varphi:V(\alpha)\rightarrow[n]}M_{\varphi(\alpha)}=\left\lvert\operatorname{Aut}(\alpha)\right\rvert\sum_{R\text{
ribbon of shape }\alpha}M_{R}$

Figure 1: An example of a ribbon and a shape

######  Example 2.14 (Ribbon).

As an example, consider the ribbon in Fig. 1. We have
$A_{R}=\\{1,2\\},B_{R}=\\{3\\},V(R)=\\{1,2,3\\},E(R)=\\{\\{1,2\\},\\{2,3\\}\\}$.
The Fourier character is $\chi_{E_{R}}=\chi_{1,3}\chi_{2,3}$. And finally,
$M_{R}$ is a matrix with rows and columns indexed by subsets of $[n]$, with
exactly one nonzero entry
$M_{R}(\\{1,2\\},\\{3\\})=\chi_{\\{1,3\\}}\chi_{\\{2,3\\}}$. Succinctly,

$M_{R}=\blockarray{rl<EMAIL_ADDRESS>$\\{3\\}$}\\\
\,\downarrow\\\
\block{r(l@{}c@{}r)}\makebox[31.0001pt]{\Large$0$\bigstrut[t]}\vdots\makebox[42.00003pt]{\Large$0$}\\\
\text{row
}\\{1,2\\}\rightarrow\mkern-9.0mu\raisebox{2.15277pt}{\makebox[32.00002pt][l]{\dotfill}}\chi_{1,3}\chi_{2,3}\raisebox{2.15277pt}{\makebox[42.00003pt][r]{\dotfill}}\\\
\makebox[31.0001pt]{\Large$0$}\vdots\makebox[42.00003pt]{\bigstrut\Large$0$}\\\
$

######  Example 2.15 (Shape).

In Fig. 1, consider the shape $\alpha$ as shown. We have
$U_{\alpha}=\\{u_{1},u_{2}\\},V_{\alpha}=\\{v_{1}\\},W_{\alpha}=\emptyset,V(\alpha)=\\{u_{1},u_{2},v_{1}\\},$
and $E(\alpha)=\\{\\{u_{1},v_{1}\\},\\{u_{2},v_{1}\\}\\}$. $M_{\alpha}$ is a
matrix with rows and columns indexed by subsets of $[n]$. The nonzero entries
will have rows and columns indexed by $\\{a_{1},a_{2}\\}$ and $b_{1}$
respectively for all distinct $a_{1},a_{2},b_{1}\in[n]$, with the
corresponding entry being
$M_{\alpha}(\\{a_{1},a_{2}\\},\\{b_{1}\\})=\chi_{a_{1},b_{1}}\chi_{a_{2},b_{1}}$.
Succinctly,

$M_{\alpha}=\blockarray{rl<EMAIL_ADDRESS>$\\{b_{1}\\}$}\\\
\,\downarrow\\\ \block{r(l@{}c@{}r)}\vdots\\\ \text{row
}\\{a_{1},a_{2}\\}\rightarrow\mkern-9.0mu\raisebox{2.15277pt}{\makebox[32.00002pt][l]{\dotfill}}\chi_{a_{1},b_{1}}\chi_{a_{2},b_{1}}\raisebox{2.15277pt}{\makebox[42.00003pt][r]{\dotfill}}\\\
\vdots\\\ $

######  Definition 2.16 (Proper).

A ribbon or shape is proper if it has no multi-edges. Otherwise, it is
improper. Let ${\sf mul}_{\alpha}(e)$ be the multiplicity of edge $e$ in
ribbon or shape $\alpha$.

An improper ribbon or shape with an edge $e$ of multiplicity 2, e.g., has a
squared Fourier character $\chi_{e}^{2}$. Since this is a function on
$\\{0,1\\}$, by expressing it in the Fourier basis an improper ribbon or shape
can be decomposed in a unique way into a linear combination of proper ones,
which we call _linearizations_.

######  Definition 2.17 (Linearization).

Given an improper ribbon or shape $\alpha$, a linearization $\beta$ is a
proper ribbon or shape such that ${\sf mul}_{\beta}(e)\leq{\sf
mul}_{\alpha}(e)$ for all $e\in E(\alpha)$.

######  Definition 2.18 (Isolated vertex).

For a shape $\alpha$, an isolated vertex is a degree-0 vertex in $W_{\alpha}$.
Let $I_{\alpha}$ denote the set of isolated vertices in $\alpha$. Similarly,
for a ribbon $R$, the isolated vertices are denoted $I_{R}$.

We stress that an isolated vertex never refers to degree-0 vertices inside
$U_{\alpha}\cup V_{\alpha}$.

######  Definition 2.19 (Trivial shape).

A shape $\alpha$ is trivial if $V(\alpha)=U_{\alpha}=V_{\alpha}$ and
$E(\alpha)=\emptyset$.

$M_{\alpha}$ for a trivial $\alpha$ is the identity matrix restricted to the
degree-$\left\lvert U_{\alpha}\right\rvert$ block.

######  Definition 2.20 (Transpose).

Given a ribbon $R$ or shape $\alpha$, we define its transpose by swapping
$A_{R}$ and $B_{R}$ (resp. $U_{\alpha}$ and $V_{\alpha}$). Observe that this
transposes the matrix for the ribbon/shape.

##  3 An overview of the proof techniques

Here, we will give a sketch of the proof techniques that we utilize in our SoS
lower bound. Recall that we are given a graph $G\sim G_{n,p}$ where $d=pn$ is
the average degree and our goal is to show that for any constant
$\varepsilon>0$, $D_{\text{SoS}}\approx n^{\delta}$ for some $\delta>0$,
degree $D_{\text{SoS}}$ SoS thinks there exists an independent set of size
$k\approx\frac{n}{d^{1/2+\varepsilon}(D_{\text{SoS}}\log n)^{c_{0}}}$ whereas
the true independent set has size $\approx\frac{n\log d}{d}$ for some absolute
constant $c_{0}$.

To prove the lower bound, we review the Planted Clique lower bound [BHK+16]
and describe the obstacles that need to be overcome in the sparse setting.

###  3.1 Modified pseudocalibration

Since SoS is a convex program, the goal of an SoS lower bound is to construct
a dual object: a set of pseudomoments
$\operatorname{\widetilde{{\mathbb{E}}}}[x^{S}]$ for each small $S\subseteq
V(G)$, which are summarized in the moment matrix. The moment matrix must (i)
obey the problem constraints (ii) be SoS-symmetric, and (iii) be positive
semidefinite (PSD). Following the recipe of pseudocalibration introduced by
[BHK+16], we can produce a candidate moment matrix which is guaranteed to
satisfy the first two conditions, while like all other SoS lower bounds, the
hard work remains in verifying the PSDness of the moment matrix.
Pseudocalibration has been successfully exploited in a multitude of SoS lower
bound applications, e.g., [BHK+16, KMOW17, MRX20, GJJ+20, PR20]. So, this is a
natural starting point for us.

##### Failure of pseudocalibration

The first obstacle we overcome is the lack of a planted distribution.
Pseudocalibration requires a planted and random distribution which are hard to
distinguish using the low-degree, likelihood ratio test (i.e.
$\widetilde{{\mathbb{E}}}[1]$ is bounded whp) [HKP+17, Hop18]. In the case of
sparse independent set, we have the following natural hypothesis testing
problem with which one may hope to pseudocalibrate.

  * -

Null Hypothesis: Sample a graph $G\sim G_{n,p}$.

  * -

Alternate Hypothesis: Sample a graph $G\sim G_{n,p}$. Then, sample a subset
$S\subseteq[n]$ where each vertex is chosen with probability $\frac{k}{n}$.
Then, plant an independent set in $S$, i.e. remove all the edges inside $S$.

In the case of sparse independent set, the naïve planted distribution is
distinguishable from a random instance via a simple low-degree test – counting
4-cycles. In all uses of pseudocalibration that we are aware of, the two
distributions being compared are conjecturally hard to distinguish by all
polynomial-time algorithms. We are still searching for a suitable planted
distribution for sparse independent set, and we believe this is an interesting
question on its own.

##### Fixing pseudocalibration via connected truncation

To get around with this issue, we close our eyes and ”pretend” the planted
distribution is quiet, ignoring the obvious distinguisher, and make a
“connected truncation” of the moment matrix to remove terms which correspond
to counting subgraphs in $G$. What remains is that
$\operatorname{\widetilde{{\mathbb{E}}}}[x^{S}]$ is essentially independent of
the global statistics of $G$. It should be pointed out here that this is
inherently distinct from the local truncation for weaker hierarchies (e.g.
Sherali-Adams) where the moment matrix is an entirely local function [CM18].
In contrast, our $\operatorname{\widetilde{{\mathbb{E}}}}[x^{S}]$ may depend
on parts of the graph that are far away from $S$, in fact, even up to radius
$n^{\delta}$, exceeding the diameter of the random graph!

At this point, the candidate moment matrix can be written as follows.

$\displaystyle\Lambda$
$\displaystyle:=\displaystyle\sum_{\alpha\in{\mathcal{S}}}\left(\frac{k}{n}\right)^{\left\lvert
V(\alpha)\right\rvert}\cdot\left(\frac{p}{1-p}\right)^{\frac{\left\lvert
E(\alpha)\right\rvert}{2}}M_{\alpha}.$

Here, ${\mathcal{S}}$ ranges over all proper shapes $\alpha$ of appropriately
bounded size such that _all vertices of $\alpha$ are connected to
$U_{\alpha}\cup V_{\alpha}$_. The latter property is the important distinction
from standard pseudocalibration and will turn out to be quite essential for
our analysis.

Using connected objects to take advantage of correlation decay is also a theme
in the cluster expansion from statistical physics (see Chapter 5 of [FV18]).
Although not formally connected with connected truncation, the two methods
share some similar characteristics.

###  3.2 Approximate PSD decompositions, norm bounds and conditioning

Continuing, to show the moment matrix is PSD, Planted Clique [BHK+16] performs
an approximate factorization of the moment matrix in terms of graph matrices.
A crucial part of this approach is to identify "dominant" and "non-dominant"
terms in the approximate PSD decomposition. Then, the dominant terms are shown
to be PSD and the non-dominant terms are bounded against the dominant terms.
In this approach, a crucial component in the latter step is to control the
norms of graph matrices.

##### Tighter norm bounds for sparse graph matrices

Existing norm bounds in the literature [MP16, AMP20] for graph matrices have
focused exclusively on the dense setting $G_{n,1/2}$. Unfortunately, while
these norm bounds apply for the sparse setting, they’re too weak to be useful.
Consider the case where we sample $G\sim G_{n,p}$ and try to bound the
spectral norm of the centered adjacency matrix. Existing norm bounds give a
bound of $\tilde{O}(\frac{\sqrt{n(1-p)}}{\sqrt{p}})$ whereas the true norm is
${O}(\sqrt{n})$ regardless of $d$. This is even more pronounced when we use
shapes with more vertices. So, our first step is to tighten the existing norm
bounds in the literature for sparse graph matrices.

For a shape $\alpha$, a vertex separator $S$ is a subset of vertices such that
there are no paths from $U_{\alpha}$ to $V_{\alpha}$ in $\alpha\setminus S$.
It is known from previous works that in the dense case the spectral norm is
controlled by the number of vertices in the minimum vertex separator between
$U_{\alpha}$ and $V_{\alpha}$. Assuming $\alpha$ does not have isolated
vertices and $U_{\alpha}\cap V_{\alpha}=\emptyset$ for simplicity, the norm of
$M_{\alpha}$ is given by the following expression, up to polylog factors and
the leading coefficient of at most $\left\lvert
V(\alpha)\right\rvert^{\left\lvert V(\alpha)\right\rvert}$,

$\left\lVert M_{\alpha}\right\rVert\leq\max_{\text{vertex separator
}S}\sqrt{n}^{|V(\alpha)|-|V(S)|}$

However, it turns out this is no longer the controlling quantity if the
underlying input matrix is sparse, and tightly determining this quantity
arises as a natural task for our problem, and for future attack on SoS lower
bounds for other problems in the sparse regime. To motivate the difference, we
want to point out this is essentially due to the following simple observation.
For $k\geq 2$,

$\displaystyle|{\mathbb{E}}[X^{k}]|=1$
$\displaystyle|{\mathbb{E}}[Y^{k}]|\leq\left(\sqrt{\frac{1-p}{p}}\right)^{k-2}\approx\left(\sqrt{\frac{n}{d}}\right)^{k-2}$

for $X$ a uniform $\pm 1$ bit and $Y$ a $p$-biased random variable
$\text{Ber}(p)$. This suggests that in the trace power method, there will be a
preference among vertex separators of the same size if some contain more edges
inside the separator (because vertices inside vertex separators are ”fixed” in
the dominant term in the trace calculation, and thus edges within the
separator will contribute some large power of $\sqrt{\frac{n}{d}}$, creating a
noticeable influence on the final trace). Finally, this leads us to the
following characterization for sparse matrix norm bounds, up to polylog
factors and the leading coefficient of at most $\left\lvert
V(\alpha)\right\rvert^{\left\lvert V(\alpha)\right\rvert}$,

$\left\lVert M_{\alpha}\right\rVert\leq\max_{\text{vertex separator
}S}\sqrt{n}^{\left\lvert V(\alpha)\right\rvert-\left\lvert
V(S)\right\rvert}\left(\sqrt{\frac{1-p}{p}}\right)^{\left\lvert
E(S)\right\rvert}$

The formal statement is given in Section 6.10. We prove this via an
application of the trace method followed by a careful accounting of the large
terms.

The key conceptual takeaway is that we need to redefine the weight of a vertex
separator to also incorporate the edges within the separator, as opposed to
only considering the number of vertices. We clearly distinguish these with the
terms Dense Minimum Vertex Separator (DMVS) and Sparse Minimum Vertex
Separator (SMVS). When $p=\frac{1}{2}$, these two bounds are the same up to
lower order factors.

##### Approximate PSD decomposition

We then perform an approximate PSD decomposition of the graph matrices that
make up $\Lambda$. The general factoring strategy is the same as [BHK+16],
though in the sparse regime we must be very careful about what kind of
combinatorial factors we allow. Each shape comes with a natural “vertex decay”
coefficient arising from the fractional size of the independent set and an
“edge decay” coefficient arising from the sparsity of the graph. The vertex
decay coefficients can be analyzed in a method similar to Planted Clique
(which only has vertex decay). For the edge decay factors, we use novel
charging arguments. At this point, the techniques are strong enough to prove
Theorem 1.8, an SoS-degree $\Omega(\log n)$ lower bound for $d\geq
n^{\varepsilon}$. The remaining techniques are needed to push the SoS degree
up and the graph degree down.

##### Conditioning

In our analysis, it turns out that to obtain strong SoS lower bounds in the
sparse regime, a norm bound from the vanilla trace method is not quite
sufficient. Sparse random matrices’ spectral norms are fragile with respect to
the influence of an unlikely event, exhibiting deviations away from the
expectation with polynomially small probability (rather than exponentially
small probability, like what is obtained from a good concentration bound).
These “bad events” are small dense subgraphs present in a graph sampled from
$G_{n,p}$.

To get around this, we condition on the high probability event that $G$ has no
small dense subgraphs. For example, for $d=n^{1-\varepsilon}$ whp every small
subgraph $S$ has $O(\left\lvert S\right\rvert)$ edges (even up to size
$n^{\delta}$). For a shape which is dense (i.e. $v$ vertices and more than
$O(v)$ edges) we can show that its norm falls off extremely rapidly under this
conditioning. This allows us to throw away dense shapes, which is critical for
controlling combinatorial factors that would otherwise dominate the moment
matrix.

This type of conditioning is well-known: a long line of work showing tight
norm bounds for the simple adjacency matrix appeals to a similar conditioning
argument within the trace method [BLM15, Bor19, FM17, DMO+19]. We instantiate
the conditioning in two ways. The first is through the following identity.

######  Observation 3.1.

Given a set of edges $E\subseteq\binom{[n]}{2}$, if we know that not all of
the edges of $E$ are in $E(G)$ then

$\chi_{E}(G)=\sum_{E^{\prime}\subseteq E:E^{\prime}\neq
E}{\left(\sqrt{\frac{p}{1-p}}\right)^{|E|-|E^{\prime}|}\chi_{E^{\prime}}(G)}$

This simple observation whose proof is deferred to Section 6.5 can be applied
recursively to replace a dense shape $\alpha$ by a sum of its sparse subshapes
$\\{\beta\\}$. The second way we eliminate dense shapes is by using a bound on
the Frobenius norm which improves on the trace calculation for dense shapes.
After conditioning, we can restrict our attention to sparse shapes, which
allows us to avoid several combinatorial factors which would otherwise
overwhelm the ”charging” argument.

Handling the subshapes $\\{\beta\\}$ requires some care. Destroying edges from
a shape can cause its norm to either go up or down: the vertex separator gets
smaller (increasing the norm), but if we remove edges from inside the SMVS,
the norm goes down. An important observation is we do not necessarily have to
apply 3.1 on the entire set of edges of a shape, but we can also just apply it
on some of the edges. We will choose a set of edges ${\sf
Res}(\alpha)\subseteq E(\alpha)$ that “protects the minimum vertex separator”
and only apply conditioning on edges outside ${\sf Res}(\alpha)$. In this way
the norm of subshapes $\beta$ will be guaranteed to be less than $\alpha$. The
fact that it’s possible to reserve such edges is shown separately for the
different kind of shapes we encounter in our analysis (see Appendix B).

Finally, we are forced to include certain dense shapes that encode indicator
functions of independent sets. These shapes must be factored out and tracked
separately throughout the analysis.444One may ask if we could definitionally
get rid of dense shapes, like we did for disconnected shapes via the connected
truncation, but these dense shapes are absolutely necessary. After handling
all of these items we have shown that $\Lambda$ is PSD.

##  4 Pseudocalibration with connected truncation

###  4.1 Pseudo-calibration

Pseudo-calibration is a heuristic introduced by [BHK+16] to construct
candidate moment matrices to exhibit SoS lower bounds. Here, we formally
describe the heuristic briefly.

To pseudocalibrate, a crucial starting point is to come up with a hard
hypothesis testing problem. Let $\nu$ denote the null distribution and $\mu$
denote the alternative distribution. Let $v$ denote the input and $x$ denote
the variables for our SoS relaxation. The main idea of pseudo-calibration is
that, for an input $v$ sampled from $\nu$ and any polynomial $f(x)$ of degree
at most the SoS degree, and for any low-degree test $g(v)$, the correlation of
$\operatorname{\widetilde{{\mathbb{E}}}}[f(x)]$ with $g$ as functions of $v$
should match in the planted and random distributions. That is,

$\mathbb{E}_{v\sim\nu}[\operatorname{\widetilde{{\mathbb{E}}}}[f(x)]g(v)]=\mathbb{E}_{(x,v)\sim\mu}[f(x)g(v)]$

Here, the notation $(x,v)\sim\mu$ means that in the planted distribution
$\mu$, the input is $v$ and $x$ denotes the planted structure in that
instance. For example, in independent set, $x$ would be the indicator vector
of the planted independent set.

Let ${\mathcal{F}}$ denote the Fourier basis of polynomials for the input $v$.
By choosing $g$ from ${\mathcal{F}}$ such that the degree is at most the
truncation parameter $D_{V}=CD_{\text{SoS}}\log n$ (hence the term “low-degree
test”), the pseudo-calibration heuristic specifies all lower order Fourier
coefficients for $\operatorname{\widetilde{{\mathbb{E}}}}[f(x)]$ as a function
of $v$. The heuristic suggests that the higher order coefficients are set to
be $0$. In total the candidate pseudoexpectation operator can be written as

$\operatorname{\widetilde{{\mathbb{E}}}}[f(x)]=\sum_{\begin{subarray}{c}g\in{\mathcal{F}}:\\\
deg(g)\leq
D_{V}\end{subarray}}\mathbb{E}_{v\sim\nu}[\operatorname{\widetilde{{\mathbb{E}}}}[f(x)]g(v)]g(v)=\sum_{\begin{subarray}{c}g\in{\mathcal{F}}:\\\
deg(g)\leq D_{V}\end{subarray}}\mathbb{E}_{(x,v)\sim\mu}[f(x)g(v)]g(v)$

The Fourier coefficients $\mathbb{E}_{(x,v)\sim\mu}[f(x)g(v)]$ can be
explicitly computed in many settings, which therefore gives an explicit
pseudoexpectation operator $\operatorname{\widetilde{{\mathbb{E}}}}$.

An advantage of pseudo-calibration is that this construction automatically
satisfies some nice properties that the pseudoexpectation
$\operatorname{\widetilde{{\mathbb{E}}}}$ should satisfy. It’s linear in $v$
by construction. For all polynomial equalities of the form $f(x)=0$ that are
satisfied in the planted distribution, it’s true that
$\operatorname{\widetilde{{\mathbb{E}}}}[f(x)]=0$. For other polynomial
equalities of the form $f(x,v)=0$ that are satisfied in the planted
distribution, the equality $\operatorname{\widetilde{{\mathbb{E}}}}[f(x,v)]=0$
is approximately satisfied. In many cases,
$\operatorname{\widetilde{{\mathbb{E}}}}$ can be mildly adjusted to satisfy
these exactly.

The condition $\operatorname{\widetilde{{\mathbb{E}}}}[1]=1$ is not
automatically satisfied. In all previous successful applications of pseudo-
calibration,
$\operatorname{\widetilde{{\mathbb{E}}}}[1]=1\pm\operatorname{o}(1)$. Once we
have this, we simply set our final pseudoexpectation operator to be
$\operatorname{\widetilde{{\mathbb{E}}}}^{\prime}$ defined as
$\operatorname{\widetilde{{\mathbb{E}}}}^{\prime}[f(x)]=\operatorname{\widetilde{{\mathbb{E}}}}[f(x)]/\operatorname{\widetilde{{\mathbb{E}}}}[1]$.
We remark that the condition
$\operatorname{\widetilde{{\mathbb{E}}}}[1]=1\pm\operatorname{o}(1)$ has been
quite successful in predicting distinguishability of the planted/null
distributions [HKP+17, Hop18].

###  4.2 The failure of "Just try pseudo-calibration"

Despite the power of pseudocalibration in guiding the construction of a
pseudomoment matrix in SoS lower bounds, it heavily relies upon a planted
distribution that is hard to distinguish from the null distribution.
Unfortunately, a ”quiet” planted distribution remains on the search in our
setting.

Towards this end, we will consider the following "naïve" planted distribution
${\mathcal{D}}_{pl}$ that likely would have been many peoples’ first guess:

  1. (1)

Sample a random graph $G\sim G_{n,p}$;

  2. (2)

Sample a subset $S\subseteq[n]$ by picking each vertex with probability
$\frac{k}{n}$;

  3. (3)

Let $\tilde{G}$ be $G$ with edges inside $S$ removed, and output
$(S,\tilde{G})$.

######  Proposition 4.1.

For all $d=O(\sqrt{n})$ and $k=\Omega(n/d)$, the naïve planted distribution
${\mathcal{D}}_{pl}$ is distinguishable in polynomial time from $G_{n,p}$ with
$\Omega(1)$ probability.

###### Proof.

The number of labeled 4-cycles in $G_{n,d/n}$ has expectation
${\mathbb{E}}[C_{4}]=\frac{d^{4}}{n^{4}}\cdot n(n-1)(n-2)(n-3)$ and variance
$\mathchoice{{\mathrm{Var}}\left[C_{4}\right]}{{\mathrm{Var}}[C_{4}]}{{\mathrm{Var}}[C_{4}]}{{\mathrm{Var}}[C_{4}]}=O(d^{4})$.
In ${\mathcal{D}}_{pl}$ the expected number of labeled 4-cycles is

$\displaystyle{\mathbb{E}}_{pl}[C_{4}]$
$\displaystyle=\frac{d^{4}}{n^{4}}\cdot
n(n-1)(n-2)(n-3)\cdot\left(\left(1-\frac{k}{n}\right)^{4}+4\frac{k}{n}\left(1-\frac{k}{n}\right)^{3}+2\left(\frac{k}{n}\right)^{2}\left(1-\frac{k}{n}\right)^{2}\right)$
$\displaystyle=\frac{d^{4}}{n^{4}}\cdot
n(n-1)(n-2)(n-3)\cdot\left(1-O(k^{2}/n^{2})\right)$
$\displaystyle={\mathbb{E}}[C_{4}]-O(d^{4}k^{2}/n^{2})={\mathbb{E}}[C_{4}]-O(d^{2})$

Since this is less than ${\mathbb{E}}[C_{4}]$ by a factor on the order of
$\sqrt{\mathchoice{{\mathrm{Var}}\left[C_{4}\right]}{{\mathrm{Var}}[C_{4}]}{{\mathrm{Var}}[C_{4}]}{{\mathrm{Var}}[C_{4}]}}$,
counting 4-cycles succeeds with constant probability.

######  Remark 4.2.

To beat distinguishers of this type, it may be possible to construct the
planted distribution from a sparse quasirandom graph (in the sense that all
small subgraph counts match $G_{n,p}$ to leading order) which has an
independent set size of $\Omega(n/\sqrt{d})$. In the dense setting, the theory
of quasirandom graphs states that if the planted distribution and $G_{n,1/2}$
match the subgraph count of $C_{4}$, this is sufficient for all subgraph
counts to match; in the sparse setting this is no longer true and the
situation is more complicated [CG02].

######  Remark 4.3.

Coja-Oghlan and Efthymiou [COE15] show that a slight modification of this
planted distribution (correct the expected number of edges to be
$p\binom{n}{2}$) is indistinguishable from the random distribution provided
$k$ is slightly smaller than the size of the maximum independent set in
$G_{n,p}$. This is not useful for pseudocalibration because we are trying to
plant an independent set with larger-than-expected size.

The Fourier coefficients of the planted distribution are:

######  Lemma 4.4.

Let $x_{T}(S)$ be the indicator function for $T$ being in the planted solution
i.e. $T\subseteq S$. Then, for all $T\subseteq[n]$ and
$\alpha\subseteq\binom{[n]}{2}$,

$\displaystyle{\mathbb{E}}_{(S,\tilde{G})\sim{\mathcal{D}}_{pl}}[x_{T}(S)\cdot\chi_{\alpha}(\tilde{G})]=\left(\frac{k}{n}\right)^{|V(\alpha)\cup
T|}\left(\frac{p}{1-p}\right)^{\frac{|E(\alpha)|}{2}}$

###### Proof.

First observe that if any vertex of $V(\alpha)\cup T$ is outside $S$, then the
expectation is $0$. This is because either $T$ is outside $S$, in which case
$x_{T}=0$, or a vertex of $\alpha$ is outside $S$, in which case the
expectation of any edge incident on this vertex is $0$ so the entire
expectation is $0$ using independence. Now, each vertex of $V(\alpha)\cup T$
is in $S$ independently with probability
$\left(\frac{k}{n}\right)^{|V(\alpha)\cup T|}$. Conditioned on this event
happening, the character is simply
$\chi_{\alpha}(0)=\left(\frac{p}{1-p}\right)^{\frac{|E(\alpha)|}{2}}$. Putting
them together gives the result.

This planted distribution motivates the following incorrect definition of the
pseudo-expectation operator.

######  Definition 4.5 (Incorrect definition of
$\operatorname{\widetilde{{\mathbb{E}}}}$).

For $S\subseteq[n],\left\lvert S\right\rvert\leq D_{\text{SoS}}$,

$\operatorname{\widetilde{{\mathbb{E}}}}[x^{S}]:=\sum_{\begin{subarray}{c}\alpha\subseteq\binom{[n]}{2}:\\\
\left\lvert\alpha\right\rvert\leq
D_{V}\end{subarray}}\left(\frac{k}{n}\right)^{\left\lvert V(\alpha)\cup
S\right\rvert}\left(\frac{p}{1-p}\right)^{\frac{\left\lvert
E(\alpha)\right\rvert}{2}}\chi_{\alpha}(G)$

For this operator, $\operatorname{\widetilde{{\mathbb{E}}}}[1]=1+\Omega(1)$.
More generally, tail bounds of graph matrix sums are not small, which ruins
our analysis technique.

###  4.3 Salvaging the doomed

We will now discuss our novel truncation heuristic. The next paragraphs are
for discussion and the technical proof resumes at Definition 4.7. Letting
${\mathcal{S}}$ be the set of shapes $\alpha$ that contribute to the moment
$\operatorname{\widetilde{{\mathbb{E}}}}[x^{I}]$, the “connected truncation”
restricts ${\mathcal{S}}$ to shapes $\alpha$ such that all vertices in
$\alpha$ have a path to $I$ (or in the shape view, to $U_{\alpha}\cup
V_{\alpha}$).

Why might this be a good idea? Consider the planted distribution. The only
tests we know of to distinguish the random/planted distributions are counting
the number of edges or counting occurrences of small subgraphs. These tests
cannot be implemented using only connected Fourier characters; shapes with
disconnected middle vertices are needed to count small subgraphs. For example,
suppose we fix a particular vertex $v\in V(G)$, and we consider the set of
functions on $G$ which are allowed to depend on $v$ but are otherwise
symmetric in the vertices of $G$. A basis for these functions can be made by
taking shapes $\alpha$ such that $U_{\alpha}$ has a single vertex,
$V_{\alpha}=\emptyset$, then fixing $U_{\alpha}=v$ (i.e. take the vector entry
in row $v$). Let $\textsf{sym}_{v}$ denote this set of functions.

######  Proposition 4.6.

Let $T(G)$ be the triangle counting function on $G$. Let
$\operatorname{conn}(\textsf{sym}_{v})$ be the subset of $\textsf{sym}_{v}$
such that all vertices have a path to $v$. Then
$T(G)\not\in\operatorname{span}(\operatorname{conn}(\textsf{sym}_{v}))$.

###### Proof.

$T(G)$ has a unique representation in $\textsf{sym}_{v}$ which requires
disconnected Fourier characters. For example, one component of the function is
$T_{\overline{v}}(G)=$ number of triangles not containing $v$. This is three
vertices $x,y,z$ outside of $U_{\alpha}$ with $1_{(x,y)\in E(G)}1_{(x,z)\in
E(G)}1_{(y,z)\in E(G)}$. The edge indicator function is implemented by
Proposition 2.5. But there are no edges between $x,y,z$ and $U_{\alpha}=v$ in
these shapes.

It’s not even possible to implement $T_{v}(G)=$ number of triangles containing
$G$, as a required shape is two vertices $x,y$ outside of $U_{\alpha}$
connected with an edge.

Despite the truncation above, our pseudocalibration operator is not a “local
function" of the graph. Our $\operatorname{\widetilde{{\mathbb{E}}}}[x^{S}]$
can depend on vertices that are far away from $S$, but in an attenuated way.
The graph matrix for $\alpha$ is a sum of all ways of overlaying the vertices
of $\alpha$ onto $G$. The edges do not need to be overlaid. If an edge
“misses” in $G$, then we can use this edge to get far away from $S$, but we
take a decay factor of
$\chi_{e}(0)=\sqrt{\frac{p}{1-p}}=\sqrt{\frac{d}{n-d}}$.

The “local function” property of
$\operatorname{\widetilde{{\mathbb{E}}}}[x^{S}]$ is also a connected
truncation, but it is a connected truncation in a different basis. The basis
is the 0/1 basis of $1_{H}(G)$ for $H\subseteq\binom{n}{2}$. A reasonable
definition of graph matrices in this basis is

$M_{\alpha}=\sum_{\text{injective
}\sigma:V(\alpha)\rightarrow[n]}1_{\sigma(E(\alpha))}(G)$

which sums all ways to embed $\alpha$ into $G$.
$\operatorname{\widetilde{{\mathbb{E}}}}[x^{S}]$ is a local function if and
only if in this basis it is a sum of shapes $\alpha$ satisfying the (same)
condition that all vertices are connected to $S=U_{\alpha}\cup V_{\alpha}$.

For sparse graphs, the two bases are somewhat heuristically interchangeable
since:

$\frac{1}{p}1_{e}(G)=1-\sqrt{\frac{1-p}{p}}\chi_{e}(G)\approx-\sqrt{\frac{1-p}{p}}\chi_{e}(G).$

Comparing the 0/1 basis and the Fourier basis, the 0/1 basis expresses
combinatorial properties such as subgraph counts more nicely, while spectral
analysis is only feasible in the Fourier basis. In the proof (see Definition
6.21), we will augment ribbons so that they may also contain 0/1 indicators,
and this flexibility helps us overcome both the spectral and combinatorial
difficulties in the analysis.

Formally we define the candidate moment matrix as:

######  Definition 4.7 (Moment matrix).

$\displaystyle\Lambda$
$\displaystyle:=\displaystyle\sum_{\alpha\in{\mathcal{S}}}\left(\frac{k}{n}\right)^{\left\lvert
V(\alpha)\right\rvert}\cdot\left(\frac{p}{1-p}\right)^{\frac{\left\lvert
E(\alpha)\right\rvert}{2}}\frac{M_{\alpha}}{\left\lvert\operatorname{Aut}(\alpha)\right\rvert}.$

where ${\mathcal{S}}$ is the set of proper shapes such that

  1. 1.

$\left\lvert U_{\alpha}\right\rvert,\left\lvert V_{\alpha}\right\rvert\leq
D_{\text{SoS}}$.

  2. 2.

$\left\lvert V(\alpha)\right\rvert\leq D_{V}$ where $D_{V}=CD_{\text{SoS}}\log
n$ for a sufficiently large constant $C$.

  3. 3.

Every vertex in $\alpha$ has a path to $U_{\alpha}\cup V_{\alpha}$.

We refer to $\left(\frac{k}{n}\right)^{\left\lvert V(\alpha)\right\rvert}$ as
the “vertex decay factor” and $\left(\frac{p}{1-p}\right)^{\frac{\left\lvert
E(\alpha)\right\rvert}{2}}$ as the “edge decay factor”. The candidate moment
matrix is the principal submatrix indexed by $\binom{[n]}{\leq
D_{\text{SoS}}/2}$. The non-PSDness properties of $\Lambda$ are easy to
verify:

######  Lemma 4.8.

$\Lambda$ is SoS-symmetric.

###### Proof.

This is equivalent to the fact that the coefficient of $\alpha$ does not
depend on how $U_{\alpha}\cup V_{\alpha}$ is partitioned into $U_{\alpha}$ and
$V_{\alpha}$ for $\left\lvert U_{\alpha}\cup V_{\alpha}\right\rvert\leq
D_{\text{SoS}}$.

######  Lemma 4.9.

$\operatorname{\widetilde{{\mathbb{E}}}}[1]=1$.

###### Proof.

For $U_{\alpha}=V_{\alpha}=\emptyset$, the only shape in which all vertices
are connected to $U_{\alpha}\cup V_{\alpha}$ is the empty shape. Therefore
$\operatorname{\widetilde{{\mathbb{E}}}}[1]=1$.

######  Lemma 4.10.

$\operatorname{\widetilde{{\mathbb{E}}}}$ satisfies the feasibility
constraints.

###### Proof.

We must show that $\operatorname{\widetilde{{\mathbb{E}}}}[x^{S}]=0$ whenever
$S$ is not an independent set in $G$. Observe that if ribbon $R$ contributes
to $\operatorname{\widetilde{{\mathbb{E}}}}[x^{S}]$, then if we modify the set
of edges inside $S$, the resulting ribbon still contributes to
$\operatorname{\widetilde{{\mathbb{E}}}}[x^{S}]$. In fact, each edge also
comes with a factor of $\sqrt{\frac{p}{1-p}}$. By Proposition 2.5, we can
group these ribbons into an indicator function
$\frac{1}{(1-p)^{\binom{|S|}{2}}}{1}_{\overline{E(S)}}$. That is,
$\operatorname{\widetilde{{\mathbb{E}}}}[x^{S}]=0$ if $S$ has an edge.

######  Lemma 4.11.

With probability at least $1-o_{n}(1)$,
$\operatorname{\widetilde{{\mathbb{E}}}}$ has objective value
$\operatorname{\widetilde{{\mathbb{E}}}}[\sum x_{i}]\geq(1-o(1))k$.

###### Proof.

######  Claim 4.12.

${\mathbb{E}}[\operatorname{\widetilde{{\mathbb{E}}}}[x_{i}]]=\frac{k}{n}$

###### Proof.

The only shape that survives under expectation is the shape with one vertex,
and it comes with coefficient $\frac{k}{n}$.

######  Claim 4.13.

$\mathchoice{{\mathrm{Var}}\left[\operatorname{\widetilde{{\mathbb{E}}}}[x_{i}]\right]}{{\mathrm{Var}}[\operatorname{\widetilde{{\mathbb{E}}}}[x_{i}]]}{{\mathrm{Var}}[\operatorname{\widetilde{{\mathbb{E}}}}[x_{i}]]}{{\mathrm{Var}}[\operatorname{\widetilde{{\mathbb{E}}}}[x_{i}]]}\leq
d^{-\Omega(\varepsilon)}$

###### Proof.

Let Count$(v,e)$ be the number of shapes with
$|U_{\alpha}|=1,V_{\alpha}=\emptyset$, $v$ vertices and $e$ edges,

$\displaystyle\mathchoice{{\mathrm{Var}}\left[\operatorname{\widetilde{{\mathbb{E}}}}[x_{i}]\right]}{{\mathrm{Var}}[\operatorname{\widetilde{{\mathbb{E}}}}[x_{i}]]}{{\mathrm{Var}}[\operatorname{\widetilde{{\mathbb{E}}}}[x_{i}]]}{{\mathrm{Var}}[\operatorname{\widetilde{{\mathbb{E}}}}[x_{i}]]}$
$\displaystyle=\sum_{\alpha\neq\emptyset:\text{connected to
$i$}}\left(\left(\frac{k}{n}\right)^{\left\lvert
V(\alpha)\right\rvert}\left(\frac{p}{1-p}\right)^{\left\lvert
E(\alpha)\right\rvert/2}\right)^{2}$
$\displaystyle=\sum_{v=2}^{D_{V}}\sum_{v-1\leq e\leq
v^{2}}\left(\frac{k}{n}\right)^{2v}\left(\frac{p}{1-p}\right)^{e}\cdot\text{Count}(v,e)\cdot
n^{v}$ $\displaystyle\leq
O(1)\sum_{v=2}^{D_{V}}\left(\frac{4k\sqrt{d}}{(1-p)n}\right)^{v}$
$\displaystyle\leq O\left(\frac{k\sqrt{d}}{n}\right)$

where the first inequality follows by observing the dominant term is tree-like
and bounding the number of trees (up-to-isomorphism) with $v$ vertices by
$2^{2v}$.

Hence,

$\Pr[\left\lvert\sum\operatorname{\widetilde{{\mathbb{E}}}}[x_{i}]-k\right\rvert\geq
t]\leq\frac{\mathchoice{{\mathrm{Var}}\left[\sum\operatorname{\widetilde{{\mathbb{E}}}}[x_{i}]\right]}{{\mathrm{Var}}[\sum\operatorname{\widetilde{{\mathbb{E}}}}[x_{i}]]}{{\mathrm{Var}}[\sum\operatorname{\widetilde{{\mathbb{E}}}}[x_{i}]]}{{\mathrm{Var}}[\sum\operatorname{\widetilde{{\mathbb{E}}}}[x_{i}]]}}{t^{2}}=\frac{k\sqrt{d}}{t^{2}}\leq
o_{n}(1)$

where the last inequality follows by picking $t=n^{\frac{1}{2}+\delta}=o(k)$
for $\delta>0$.

What remains is to show $\Lambda\succeq 0$. To do this it’s helpful to
renormalize the matrix entries by multiplying the degree-($k,l)$ block by a
certain factor.

######  Definition 4.14 (Shape coefficient).

For all shapes $\alpha$, let

$\lambda_{\alpha}:=\left(\frac{k}{n}\right)^{\left\lvert
V(\alpha)\right\rvert-\frac{\left\lvert U_{\alpha}\right\rvert+\left\lvert
V_{\alpha}\right\rvert}{2}}\cdot\left(\frac{p}{1-p}\right)^{\frac{\left\lvert
E(\alpha)\right\rvert}{2}}.$

It suffices to show
$\sum_{\alpha\in{\mathcal{S}}}\lambda_{\alpha}\frac{M_{\alpha}}{\left\lvert\operatorname{Aut}(\alpha)\right\rvert}\succeq
0$ because left and right multiplying by a rank-1 matrix and its transpose
returns $\Lambda$.

######  Proposition 4.15.

If $\alpha,\beta$ are composable shapes, then
$\lambda_{\alpha}\lambda_{\beta}=\lambda_{\alpha\circ\beta}.$

##  5 Norm bounds and factoring

As explained in Section 3, existing norm bounds in the literature are not
tight enough for sparse graph matrices. We first obtain tighter norm bounds
for sparse graph matrices.

###  5.1 Norm bounds

In this section, we show the spectral norm bounds for $M_{\alpha}$ in terms of
simple combinatorial factors involving $\alpha$. With only log factor loss the
norm bounds hold with very high probability (all but probability
$n^{-\Omega(\log n)}$). This is too tight of a probabilistic bound since it
allows for polynomially rare events such as small dense subgraphs. We will
need to use conditioning to improve the norm bound for shapes with a lot of
edges.

######  Definition 5.1.

For a shape $\alpha$, define a vertex separator (or a separator) $S$ to be a
subset of vertices such that there is no path from $U_{\alpha}$ to
$V_{\alpha}$ in the graph $\alpha\setminus S$.

Roughly, the norm bounds for a proper shape $\alpha$ are:

$\left\lVert M_{\alpha}\right\rVert\leq\widetilde{O}\left(\max_{\text{vertex
separator }S}\left\\{\sqrt{n}^{\left\lvert V(\alpha)\right\rvert-\left\lvert
S\right\rvert}\sqrt{\frac{1-p}{p}}^{\left\lvert
E(S)\right\rvert}\right\\}\right).$

The maximizer of the above is called the _sparse minimum vertex separator._
The proof of this bound uses the trace method, which also underlies graph
matrix norm bounds in the dense case. We defer the proof to Appendix A.

To get norm bounds for improper shapes, we linearize the shape and take the
largest norm bound among its linearizations.

######  Definition 5.2.

For a linearization $\beta$ of a shape $\alpha$, $E_{phantom}(\beta)$ is the
set (not multiset) of “phantom edges” of $\alpha$ which are not in $\beta$.

For an improper shape $\alpha$:

$\left\lVert
M_{\alpha}\right\rVert\leq\widetilde{O}\left(\max_{\beta,S}\left\\{\sqrt{n}^{|V(\alpha)|-|S|+|I_{\beta}|}\left(\sqrt{\frac{1-p}{p}}\right)^{|E(\alpha)|-|E(\beta)|-2|E_{phantom}(\beta)+|E(S)|}\right\\}\right)$

where $\beta$ is a linearization of $\alpha$ and $S$ is a separator of
$\beta$.

###  5.2 Factoring ribbons and shapes

Because on the fact that norm bounds depend on vertex separators, we will need
to do some combinatorics on vertex separators of shapes. The essential ideas
presented in this section have appeared in prior works such as [BHK+16, AMP20,
PR20], but we redefine them for convenience and to set up the notation for the
rest of the paper.

######  Definition 5.3 (Composing ribbons).

Two ribbons $R,S$ are composable if $B_{R}=A_{S}$. The composition $R\circ S$
is the (possibly improper) ribbon $T=(V(R)\cup V(S),E(R)\sqcup
E(S),A_{R},B_{S})$.

######  Fact 5.4.

If $R,S$ are composable ribbons, then $M_{R\circ S}=M_{R}M_{S}$.

######  Definition 5.5 (Composing shapes).

Two shapes $\alpha,\beta$ are composable if $\left\lvert
V_{\alpha}\right\rvert=\left\lvert U_{\beta}\right\rvert$. Given a bijection
$\varphi:V_{\alpha}\rightarrow U_{\beta}$, the composition
$\alpha\circ_{\varphi}\beta$ is the (possibly improper) shape $\zeta$ whose
multigraph is the result of gluing together the graphs for $\alpha,\beta$
along $V_{\alpha}$ and $U_{\beta}$ using $\varphi$. Set $U_{\zeta}=U_{\alpha}$
and $V_{\zeta}=V_{\beta}$.

If we write $\alpha\circ\beta$ then we will implicitly assume that $\alpha$
and $\beta$ are composable and the bijection $\varphi$ is given. We would like
to say that the graph matrix $M_{\alpha\circ\beta}$ also factors as
$M_{\alpha}M_{\beta}$, but this is not quite true. There are intersection
terms.

######  Definition 5.6 (Intersection pattern).

For composable shapes $\alpha_{1},\alpha_{2},\dots,\alpha_{k}$, let
$\alpha=\alpha_{1}\circ\alpha_{2}\circ\cdots\circ\alpha_{k}$. An intersection
pattern $P$ is a partition of $V(\alpha)$ such that for all $i$ and $v,w\in
V(\alpha_{i})$, $v$ and $w$ are not in the same block of the partition. 555The
intersection pattern also specifies the bijections $\varphi$ for composing the
shapes $\alpha_{1},\dots,\alpha_{k}$. We say that a vertex “intersects” if its
block has size at least 2 and let $\operatorname{Int}(P)$ denote the set of
intersecting vertices.

Let ${\mathcal{P}}_{\alpha_{1},\alpha_{2},\dots,\alpha_{k}}$ be the set of
intersection patterns between $\alpha_{1},\alpha_{2},\dots,\alpha_{k}$.

######  Definition 5.7 (Intersection shape).

For composable shapes $\alpha_{1},\alpha_{2},\dots,\alpha_{k}$ and an
intersection pattern
$P~{}\in~{}{\mathcal{P}}_{\alpha_{1},\alpha_{2},\dots,\alpha_{k}}$, let
$\alpha_{P}=\alpha_{1}\circ\alpha_{2}\circ\cdots\circ\alpha_{k}$ then identify
all vertices in blocks of $P$, i.e. contract them into a single super vertex.
Keep all edges (and hence $\alpha_{P}$ may be improper).

Composable ribbons $R_{1},\dots,R_{k}$ with shapes
$\alpha_{1},\dots,\alpha_{k}$ induce an intersection pattern
${P\in{\mathcal{P}}_{\alpha_{1},\dots,\alpha_{k}}}$ based on which vertices
are equal. When multiplying graph matrices, by casing on which vertices are
equal we have:

######  Proposition 5.8.

For composable shapes $\alpha_{1},\alpha_{2},\dots,\alpha_{k}$,

$M_{\alpha_{1}}\cdots
M_{\alpha_{k}}=\sum_{P\in{\mathcal{P}}_{\alpha_{1},\dots,\alpha_{k}}}M_{\alpha_{P}}.$

Note that different $P$ may give the same $\alpha_{P}$, and hence the total
coefficient on $M_{\alpha_{P}}$ for a given shape $\alpha_{P}$ is more
complicated.

######  Definition 5.9 (Minimum vertex separators).

For a shape $\alpha$, a vertex separator $S$ is a minimum vertex separator
(MVS) if it has the smallest possible size. MVS $S$ is the leftmost minimum
vertex separator (LMVS) if $\alpha\setminus S$ cuts all paths from
$U_{\alpha}$ to any other MVS. The rightmost minimum vertex separator (RMVS)
likewise cuts paths from $V_{\alpha}$.

The LMVS and RMVS can be easily shown to be uniquely defined [BHK+16].

######  Definition 5.10 (Left shape).

A shape $\sigma$ is a left shape if it is proper, the unique minimum vertex
separator is $V_{\sigma}$, there are no edges with both endpoints in
$V_{\sigma}$, and every vertex is connected to $U_{\sigma}$.

######  Definition 5.11 (Middle shape).

A shape $\tau$ is a middle shape if $U_{\tau}$ is the leftmost minimum vertex
separator of $\tau$, and $V_{\tau}$ is the rightmost minimum vertex separator
of $\tau$. If $\tau$ is proper, we say it is a proper middle shape.

######  Definition 5.12 (Right shape).

$\sigma^{\prime}$ is a right shape if $\sigma^{\prime\intercal}$ is a left
shape.

We also extend the definition of (L/R)MVS, left, middle, and right to ribbons.
Every proper shape admits a canonical decomposition into left, right, and
middle parts.

######  Proposition 5.13.

Every proper shape $\alpha$ has a unique decomposition
$\alpha=\sigma\circ\tau\circ\sigma^{\prime\intercal}$, where $\sigma$ is a
left shape, $\tau$ is a middle shape, and $\sigma^{\prime\intercal}$ is a
right shape.

The decomposition takes $\sigma$ to be the set of vertices reachable from
$U_{\alpha}$ via paths that do not pass through the LMVS, similarly for
$\sigma^{\prime}$ vis-à-vis the RMVS, and then $\tau$ is the remainder. This
decomposition respects the connected truncation:

######  Proposition 5.14.

If all vertices in $\alpha$ have a path to $U_{\alpha}\cup V_{\alpha}$, then
decomposing $\alpha=\sigma\circ\tau\circ\sigma^{\prime\intercal}$, all
vertices in $\tau$ have a path to both $U_{\tau}$ and $V_{\tau}$.

###### Proof.

It suffices to show that there is a path to $U_{\tau}\cup V_{\tau}$. In this
case, say there is a path to vertex $u\in U_{\tau}$, then $u$ must have a path
to $V_{\tau}$. Otherwise, $U_{\tau}\setminus\\{u\\}$ would be a smaller vertex
separator of $\tau$ than $U_{\tau}$, a contradiction to $\tau$ being a middle
shape.

Let $v\in V(\tau)\subseteq V(\alpha)$. By assumption there is a path from $v$
to $u\in U_{\alpha}\cup V_{\alpha}$; without loss of generality, $u\in
U_{\alpha}$. Since $v$ is not in $\sigma$, which was constructed by taking all
vertices reachable from $U_{\alpha}$ without passing through $U_{\tau}$, the
path must pass through $U_{\tau}$.

##  6 PSD-ness

To prove PSD-ness, we perform an approximate PSD decomposition of the moment
matrix $\Lambda$. This type of decomposition originates from the planted
clique problem [BHK+16]. Our usage of it will be similar at a high level, but
the accounting of graph matrices is more complicated.

###  6.1 Overview of the approximate PSD decomposition

Recall that our goal is to show that the matrix
$\sum_{\alpha\in{\mathcal{S}}}\lambda_{\alpha}M_{\alpha}$ is PSD. Each shape
$\alpha$ decomposes into left, middle, and right parts
$\alpha=\sigma\circ\tau\circ\sigma^{\prime\intercal}$. We have a corresponding
approximate decomposition of the graph matrix for $\alpha$, up to intersection
terms,

$M_{\alpha}=M_{\sigma\circ\tau\circ\sigma^{\prime\intercal}}\approx
M_{\sigma}M_{\tau}M_{\sigma^{\prime}}^{\intercal}.$

The dominant term in the PSD decomposition of $\Lambda$ (call it
${\mathcal{H}}$) collects together $\alpha$ such that its middle shape $\tau$
is trivial. Since the coefficients $\lambda_{\alpha}$ also factor, this term
is automatically PSD.

$\sum_{\begin{subarray}{c}\alpha:\text{
trivial}\end{subarray}}\lambda_{\alpha}M_{\alpha}=\sum_{\sigma,\sigma^{\prime}}\lambda_{\sigma\circ\sigma^{\prime\intercal}}M_{\sigma\circ\sigma^{\prime\intercal}}\approx\sum_{\sigma,\sigma^{\prime}}\lambda_{\sigma}\lambda_{\sigma^{\prime}}M_{\sigma}M_{\sigma^{\prime}}^{\intercal}=\left(\sum_{\sigma}\lambda_{\sigma}M_{\sigma}\right)\left(\sum_{\sigma}\lambda_{\sigma}M_{\sigma}\right)^{\intercal}=:{\mathcal{H}}.$

There are two types of things to handle: $\alpha$ with nontrivial $\tau$, and
intersection terms. For $\alpha$ with a fixed middle shape $\tau$, these
should all be charged directly to ${\mathcal{H}}$ (include $\tau^{\intercal}$
so the matrix is symmetric):

$\left(\sum_{\sigma}\lambda_{\sigma}M_{\sigma}\right)\lambda_{\tau}(M_{\tau}+M_{\tau}^{\intercal})\left(\sum_{\sigma}\lambda_{\sigma}M_{\sigma}\right)^{\intercal}\preceq\frac{1}{c(\tau)}\left(\sum_{\sigma}\lambda_{\sigma}M_{\sigma}\right)\left(\sum_{\sigma}\lambda_{\sigma}M_{\sigma}\right)^{\intercal}$

where we leave some space $c(\tau)$. Intuitively this is possible because
nontrivial $\tau$ have smaller coefficients $\lambda_{\tau}$ due to
vertex/edge decay, and the norm of $M_{\tau}$ is controlled due to the
factorization of $\alpha$ into left, middle, and right parts. This check
amounts to $\sum_{\tau\text{
nontrivial}}\lambda_{\tau}M_{\tau}~{}\preceq~{}o(1)\textup{Id}$.

The intersection terms need to be handled in a recursive way so that their
norms can be kept under control: if $\sigma,\tau,\sigma^{\prime\intercal}$
intersect to create a shape $\zeta$, then we need to factor out the non-
intersecting parts of $\sigma$ and $\sigma^{\prime}$ from the intersecting
parts $\gamma,\gamma^{\prime}$. Informally writing

$\zeta=(\sigma-\gamma)\circ\tau_{P}\circ(\sigma^{\prime}-\gamma^{\prime})^{\intercal},$

where $\tau_{P}$ is the intersection of
$\gamma,\tau,\gamma^{\prime\intercal}$, we now perform a further factorization

$M_{\zeta}\approx
M_{\sigma-\gamma}M_{\tau_{P}}M_{\sigma^{\prime}-\gamma^{\prime}}^{\intercal}$

which recursively creates more intersection terms. The point is that the sum
over $\sigma-\gamma,\sigma^{\prime}-\gamma^{\prime}$ is equivalent to the sum
over $\sigma,\sigma^{\prime}$ (up to truncation error).

$\displaystyle\sum_{\sigma-\gamma}\sum_{\sigma^{\prime}-\gamma^{\prime}}\lambda_{\sigma\circ\tau\circ\sigma^{\prime\intercal}}M_{\sigma-\gamma}M_{\tau_{P}}M_{\sigma^{\prime}-\gamma^{\prime}}^{\intercal}$
$\displaystyle=\left(\sum_{\sigma-\gamma}\lambda_{\sigma-\gamma}M_{\sigma-\gamma}\right)\lambda_{\gamma\circ\tau\circ\gamma^{\prime\intercal}}M_{\tau_{P}}\left(\sum_{\sigma-\gamma}\lambda_{\sigma-\gamma}M_{\sigma-\gamma}^{\intercal}\right)$
$\displaystyle=\left(\sum_{\sigma}\lambda_{\sigma}M_{\sigma}\right)\lambda_{\gamma\circ\tau\circ\gamma^{\prime\intercal}}M_{\tau_{P}}\left(\sum_{\sigma}\lambda_{\sigma}M_{\sigma}^{\intercal}\right)+\text{truncation
error}.$

In summary, we have the following informal decomposition of the moment matrix,

$\Lambda=\left(\sum_{\sigma}\lambda_{\sigma}M_{\sigma}\right)\left(\textup{Id}+\sum_{\tau\text{
nontrivial}}\lambda_{\tau}M_{\tau}+\sum_{\begin{subarray}{c}\text{intersection
terms}\\\
\tau_{P}\in{\mathcal{P}}_{\gamma,\tau,\gamma^{\prime}}\end{subarray}}\lambda_{\gamma\circ\tau\circ\gamma^{\prime\intercal}}M_{\tau_{P}}\right)\left(\sum_{\sigma}\lambda_{\sigma}M_{\sigma}\right)^{\intercal}+\text{truncation
error}.$

We then need to compare the intersection terms $M_{\tau_{P}}$ with Id. The
vertex decay factors are compared with $\tau$ via the “intersection tradeoff
lemma”. For the edge decay factors, we give new charging arguments. The number
of ways to produce $\tau_{P}$ as an intersection pattern needs to be bounded
combinatorially.

Finally, there is the issue of truncation. The total norm of the truncation
error should be small. This can be accomplished by taking a large truncation
parameter.

The matrix

$\textup{Id}+\sum_{\tau\text{
nontrivial}}\lambda_{\tau}M_{\tau}+\sum_{\begin{subarray}{c}\text{intersection
terms}\\\
\tau_{P}\in{\mathcal{P}}_{\gamma,\tau,\gamma^{\prime}}\end{subarray}}\lambda_{\gamma\circ\tau\circ\gamma^{\prime\intercal}}M_{\tau_{P}}$

actually does have a nullspace, which prevents the above strategy from working
perfectly. This is because $\Lambda$ needs to satisfy the independent set
constraints ($\operatorname{\widetilde{{\mathbb{E}}}}[x^{S}]=0$ if $S$ has an
edge). For independent set it’s easy to factor out these constraints. Instead
of Id, the leading term is a diagonal projection matrix
${\pi:=\sum_{\tau:V(\tau)=U_{\tau}=V_{\tau}}\lambda_{\tau}M_{\tau}}$ and the
non-dominant middle shapes are $\tau$ with
$|V(\tau)|>\frac{|U_{\tau}|+|V_{\tau}|}{2}$.

###  6.2 Informal sketch for bounding $\tau$ and $\tau_{P}$

The most important part of the overview given in the previous section is
showing that middle shapes $\tau$ and intersection terms $\tau_{P}$ can be
charged to the identity matrix, i.e. a type of “graph matrix tail bound” for
middle shapes and intersection terms. In this subsection, we describe the
properties that $\tau$ and $\tau_{P}$ satisfy, their coefficients, and their
norm bounds. Using this, we show that for each individual non-trivial $\tau$,
$\lambda_{\tau}\left\lVert M_{\tau}\right\rVert\ll 1$ and for each
intersection pattern $P$,
$\lambda_{\gamma\circ\tau\circ{\gamma^{\prime}}^{\intercal}}\left\lVert
M_{\tau_{P}}\right\rVert\ll 1$. We then explain how these arguments are used
to prove Theorem 1.8. The combinatorial arguments in this section crucially
rely on the connected truncation.

####  6.2.1 Middle shapes

######  Proposition 6.1.

For each middle shape $\tau$ such that
$|V(\tau)|>\frac{|U_{\tau}|+|V_{\tau}|}{2}$ and every vertex in $\tau$ is
connected to $U_{\tau}\cup V_{\tau}$, $\lambda_{\tau}\left\lVert
M_{\tau}\right\rVert~{}\ll~{}1$.

###### Proof.

The coefficient $\lambda_{\tau}$ is

$\lambda_{\tau}=\left(\frac{k}{n}\right)^{|V(\tau)|-\frac{|U_{\tau}|+|V_{\tau}|}{2}}\left(-\sqrt{\frac{p}{1-p}}\right)^{|E(\tau)|}$

The norm bound on $M_{\tau}$ is

$\left\lVert
M_{\tau}\right\rVert\leq\widetilde{O}\left(n^{\frac{|V(\tau)\setminus
S|}{2}}\left(\sqrt{\frac{1-p}{p}}\right)^{|E(S)|}\right)$

where $S$ is the sparse minimum vertex separator of $\tau$. We now have that
$|\lambda_{\tau}|\left\lVert M_{\tau}\right\rVert$ is

$\widetilde{O}\left(\left(\frac{k}{\sqrt{n}}\sqrt{\frac{p}{1-p}}\right)^{|V(\tau)|-\frac{|U_{\tau}|+|V_{\tau}|}{2}}\left(\sqrt{\frac{1-p}{np}}\right)^{|S|-\frac{|U_{\tau}|+|V_{\tau}|}{2}}\left(\sqrt{\frac{p}{1-p}}\right)^{|E(\tau)\setminus
E(S)|-|V(\tau)\setminus S|}\right).$

We claim that each of the three terms is upper bounded by 1. This will prove
the claim, since the first term provides a decay for
$|V(\tau)|>\frac{|U_{\tau}|+|V_{\tau}|}{2}$. The base of the first term is
less than 1 for $k\lessapprox n/\sqrt{d}$. The exponent of the second term is
nonnegative: since $\tau$ is a middle shape, both $U_{\tau}$ and $V_{\tau}$
are minimum vertex separators of $\tau$, and since $S$ is a vertex separator,
it must have larger size. The exponent of the third term is nonnegative by the
following lemma.

######  Lemma 6.2.

For a middle shape $\tau$ such that every vertex is connected to $U_{\tau}\cup
V_{\tau}$, and any vertex separator $S$ of $\tau$,

$\left\lvert E(\tau)\setminus E(S)\right\rvert\geq\left\lvert V(\tau)\setminus
S\right\rvert.$

###### Proof.

First, we claim that every vertex in $\tau$ is connected to $S$. Let $v\in
V(\tau)$, and by the connected truncation, $v$ is connected to some $u\in
U_{\tau}$. Since $\tau$ is a middle shape, there must be a path from $u$ to
$V_{\tau}$ (else $U_{\tau}\setminus\\{u\\}$ would be a smaller vertex
separator than $U_{\tau}$). The path necessarily passes through $S$ since $S$
is a vertex separator, therefore we now have a path from $v$ to $S$.

Now, we can assign an edge of $E(\tau)\setminus E(S)$ to each vertex of
$V(\tau)\setminus S$ to prove the claim. To do this, run a breadth-first
search from $S$, and assign an edge to the vertex that it explores.

####  6.2.2 Intersection terms

Recall that intersection terms are formed by the intersection of
$\sigma,\tau,\sigma^{\prime\intercal}$. Then we factor out the non-
intersecting parts, leaving the _middle intersection_ $\tau_{P}$, which is an
intersection of some portion $\gamma$ of $\sigma$, the middle shape $\tau$,
and some portion $\gamma^{\prime}$ of $\sigma^{\prime}$, which we now make
formal.

######  Definition 6.3 (Middle intersection).

Let $\gamma,\gamma^{\prime}$ be left shapes and $\tau$ be a shape such that
$\gamma\circ\tau\circ\gamma^{\prime\intercal}$ are composable. We say that an
intersection pattern
$P\in{\mathcal{P}}_{\gamma,\tau,\gamma^{\prime\intercal}}$ is a _middle
intersection_ if $U_{\gamma}$ is a minimum vertex separator in $\gamma$ of
$U_{\gamma}$ and $V_{\gamma}\cup\operatorname{Int}(P)$. Similarly,
$U_{\gamma^{\prime}}$ is a minimum vertex separator in $\gamma^{\prime}$ of
$U_{\gamma^{\prime}}$ and $V_{\gamma^{\prime}}\cup\operatorname{Int}(P)$.
Finally, we also require that $P$ has at least one intersection.

Let ${\mathcal{P}}^{mid}_{\gamma,\tau,\gamma^{\prime}}$ denote the set of
middle intersections.

######  Remark 6.4.

For middle intersections we use the notation $\tau_{P}$ to denote the
resulting shape, as compared to $\alpha_{P}$ which is used for an arbitrary
intersection pattern.

######  Remark 6.5.

In fact this definition also captures recursive intersection terms which are
created from later rounds of factorization. We say that
${P\in{\mathcal{P}}_{\gamma_{k},\dots,\gamma_{1},\tau,\gamma_{1}^{\prime\intercal},\dots,\gamma_{k}^{\prime\intercal}}}$
is a middle intersection, denoted
${P\in{\mathcal{P}}^{mid}_{\gamma_{k},\dots\gamma_{1},\tau,\gamma_{1}^{\prime},\dots,\gamma_{k}^{\prime}}}$,
if for all $j=0,\dots,k-1$, letting $\tau_{j}$ be the shape of intersections
so far between
$\gamma_{j},\dots,\gamma_{1},\tau,\gamma_{1}^{\prime\intercal},\dots,\gamma_{j}^{\prime\intercal}$,
the intersection $\gamma_{j+1},\tau_{j},\gamma_{j+1}^{\prime\intercal}$ is a
middle intersection.

We need the following structural property of middle intersections.

######  Proposition 6.6.

For a middle intersection
$P\in{\mathcal{P}}^{mid}_{\gamma,\tau,\gamma^{\prime}}$ such that every vertex
of $\tau$ is connected to both $U_{\tau}$ and $V_{\tau}$, every vertex in
$\tau_{P}$ is connected to both $U_{\tau_{P}}$ and $V_{\tau_{P}}$.

###### Proof.

By assumption, all vertices in $\tau$ have a path to both $U_{\tau}$ and
$V_{\tau}$. Since $U_{\tau}=V_{\gamma}$, and all vertices in $\gamma$ have a
path to $U_{\gamma}$ by definition of a left shape, all vertices in $\tau$
have a path to $U_{\gamma}=U_{\tau_{P}}$. Similarly,
$V_{\tau}=U_{\gamma^{\prime}}$ is connected to
$V_{\gamma^{\prime}}=V_{\tau_{P}}$. Thus we have shown that all vertices in
$\tau$ are connected to both $U_{\tau_{P}}$ and $V_{\tau_{P}}$.

Vertices in $\gamma$ have a path to $U_{\tau_{P}}$ by definition; we must show
that they also have a path to $V_{\tau_{P}}$. A similar argument will hold for
vertices in $\gamma^{\prime}.$ Since all vertices in $\gamma$ have paths to
$U_{\gamma}$, it suffices to show that all $u\in U_{\gamma}$ have a path to
$V_{\tau_{P}}$. There must be a path from $u$ to some $v\in
V_{\gamma}\cup\operatorname{Int}(P)$, else this would violate the definition
of a middle intersection by taking $U_{\gamma}\setminus\\{u\\}$. The vertex
$v$ is in either $\tau$ or $\gamma^{\prime}$, both of which are connected to
$V_{\tau_{P}}$, hence we are done.

Now we show that middle intersections have small norm. We focus on the first
level of intersection terms; the general case of middle intersections in
Remark 6.5 follows by induction.

######  Proposition 6.7.

For left shapes $\gamma,\gamma^{\prime}$, proper middle shape $\tau$ such that
every vertex in $\tau$ is connected to $U_{\tau}\cup V_{\tau}$, and a middle
intersection $P\in{\mathcal{P}}^{mid}_{\gamma,\tau,\gamma^{\prime}}$,
${\left\lvert\lambda_{\gamma\circ\tau\circ\gamma^{\prime\intercal}}\right\rvert\left\lVert
M_{\tau_{P}}\right\rVert\ll 1}$.

###### Proof.

For an intersection pattern $P$, the coefficient is

$\lambda_{\gamma\circ\tau\circ{\gamma^{\prime}}^{\intercal}}=\left(\frac{k}{n}\right)^{|V(\tau_{P})|+i_{P}-\frac{|U_{\tau_{P}}|+|V_{\tau_{P}}|}{2}}\left(-\sqrt{\frac{p}{1-p}}\right)^{|E(\tau_{P})|}$

where $i_{P}:=\left\lvert
V(\gamma\circ\tau\circ\gamma^{\prime\intercal})\right\rvert-\left\lvert
V(\tau_{P})\right\rvert$ is the number of intersections in $P$.

The norm bound on $M_{\tau_{P}}$ is

$\widetilde{O}\left(\max_{\beta,S}\left\\{n^{\frac{|V(\beta)|+|I_{\beta}|-|S|}{2}}\left(\sqrt{\frac{1-p}{p}}\right)^{|E(S)|+|E(\tau_{P})|-|E(\beta)|-2|E_{phantom}|}\right\\}\right)$

where the maximization is taken over all linearizations $\beta$ of $\tau_{P}$
and all separators $S$ for $\beta$.

We now have that
$\left\lvert\lambda_{\gamma\circ\tau\circ\gamma^{\prime\intercal}}\right\rvert\left\lVert
M_{\tau_{P}}\right\rVert$ is

$\displaystyle\widetilde{O}\Bigg{(}\max_{\beta,S}\Bigg{\\{}$
$\displaystyle\left(\frac{k}{\sqrt{n}}\sqrt{\frac{p}{1-p}}\right)^{|V(\gamma\circ\tau\circ\gamma^{\prime\intercal})|-\frac{|U_{\beta}|+|V_{\beta}|}{2}}\left(\sqrt{\frac{1-p}{np}}\right)^{i_{P}-|I_{\beta}|+|S|-\frac{|U_{\beta}|+|V_{\beta}|}{2}}\cdot$
$\displaystyle\left(\sqrt{\frac{p}{1-p}}\right)^{|E(\beta)\setminus
E(S)|-|V(\beta)\setminus S|-|I_{\beta}|+2|E_{phantom}|}\Bigg{\\}}\Bigg{)}.$

We claim that each of the three terms is upper bounded by 1, which proves the
proposition since the first term provides a decay (since an intersection is
nontrivial). The base of the first term (vertex decay) is less than 1 for
$k\lessapprox n/\sqrt{d}$. The second term has a nonnegative exponent by the
_intersection tradeoff lemma_ from [BHK+16]. The version we cite is Lemma 9.32
in [PR20], with the simplification that $\tau$ is a proper middle shape, so
$I_{\tau}=\emptyset$ and $\left\lvert S_{\tau,min}\right\rvert=\left\lvert
U_{\tau}\right\rvert=\left\lvert V_{\tau}\right\rvert$ (the full form is used
for intersection terms with $\gamma_{1},\dots,\gamma_{k},k>1$).

######  Lemma 6.8 (Intersection tradeoff lemma).

For all left shapes $\gamma,\gamma^{\prime}$ and proper middle shapes $\tau$,
let $P\in{\mathcal{P}}_{\gamma,\tau,\gamma^{\prime\intercal}}$ be a middle
intersection, then

$|V(\tau)|-\frac{|U_{\tau}|+|V_{\tau}|}{2}+|V(\gamma)|-|U_{\gamma}|+|V(\gamma^{\prime})|-|U_{\gamma^{\prime}}|\geq|V(\tau_{P})|+|I_{\tau_{P},min}|-|S_{\tau_{P},min}|$

where $S_{\alpha,min}$ is defined to be a minimum vertex separator of $\alpha$
with all multi-edges deleted, and $I_{\alpha,min}$ is the set of isolated
vertices in $\alpha$ with all multi-edges deleted.

The above inequality is equivalent to

$i_{P}+\frac{|U_{\tau}|+|V_{\tau}|}{2}-|U_{\gamma}|-|U_{\gamma^{\prime}}|\geq\left\lvert
I_{\tau_{P},min}\right\rvert-\left\lvert S_{\tau_{P},min}\right\rvert.$

Since
$|U_{\tau}|\leq|U_{\gamma}|=|U_{\beta}|,|V_{\tau}|\leq|U_{\gamma^{\prime}}|=|V_{\beta}|,\left\lvert
I_{\tau_{P},min}\right\rvert\geq|I_{\beta}|,|S|\geq\left\lvert
S_{\tau_{P},min}\right\rvert$, this implies

$i_{P}-|I_{\beta}|+|S|-\frac{|U_{\beta}|+|V_{\beta}|}{2}\geq 0.$

The third term has a nonnegative exponent, as the following lemma shows.

######  Lemma 6.9.

For any linearization $\beta$ of $\tau_{P}$ and all separators $S$ for
$\beta$,

$|E(\beta)|+2|E_{phantom}|-|E(S)|\geq|V(\tau_{P})|+|I_{\beta}|-|S|.$

###### Proof.

We give a proof using induction. An alternate proof that uses an explicit
charging scheme is given in Appendix C.

We start with $E(\beta)$ and add in pairs of phantom edges one by one. The
final graph will have $\left\lvert E(\beta)\right\rvert+2\left\lvert
E_{phantom}\right\rvert$ edges. The inductive claim is that at any time in the
process, for all connected components $C$ in the current graph,

  1. 1.

If $C$ is not connected to $U_{\tau_{P}}=U_{\beta}$ or
$V_{\tau_{P}}=V_{\beta}$, $|E(C)\setminus
E(S)|+2|E_{phantom}(C)|\geq|C\setminus S|+|I_{\beta}\cap C|-2$. For example,
$C$ may consist of a single isolated vertex or a set of isolated vertices
connected by phantom edges.

  2. 2.

If $C$ is connected to $U_{\tau_{P}}$ or $V_{\tau_{P}}$ but not both,
$|E(C)\setminus E(S)|+2|E_{phantom}(C)|\geq|C\setminus S|+|I_{\beta}\cap
C|-1$.

  3. 3.

If $C$ is connected to both $U_{\tau_{P}}$ and $V_{\tau_{P}}$, $|E(C)\setminus
E(S)|+2|E_{phantom}(C)|\geq|C\setminus S|+|I_{\beta}\cap C|$

To see that the base case holds for $E(\beta)$ and $E_{phantom}(C)=\emptyset$,
let $C$ be a component $C$ of $E(\beta)$. If $C$ is a single isolated vertex,
we are in case (1), and the inequality is a tight equality. Otherwise, $C$ has
no isolated vertices, and therefore $\left\lvert E(C)\setminus
E(S)\right\rvert\geq\left\lvert C\setminus S\right\rvert-1$ holds by
connectivity, which is sufficient for $C$ in either case (1) or (2). If $C$ is
in case (3), $C$ is connected to both $U_{\tau_{P}}$ and $V_{\tau_{P}}$. Since
$S$ is a separator, in this case $C$ must include at least one vertex in $S$
and the stronger inequality $\left\lvert E(C)\setminus
E(S)\right\rvert\geq\left\lvert C\setminus S\right\rvert$ holds as required
for the base case.

Now consider adding another phantom edge $e$. If $e$ is entirely contained
within a component $C$, the right-hand side of the inequality is unchanged,
therefore the inequality for $C$ continues to hold. If $e$ goes between two
components $C_{1}$ and $C_{2}$, there are six cases depending on which case
$C_{1}$ and $C_{2}$ are in. Let $C$ denote the new joined component. We show
the argument when $C_{1},C_{2}$ are both case (1) or both case (2). The
remaining cases are similar.

(Both are case (1)) $C$ is connected to neither $U_{\tau_{P}}$ nor
$V_{\tau_{P}}$, so we must show the inequality for case (1) still holds.
Adding the inequalities for $C_{1}$ and $C_{2}$,

$\displaystyle\left\lvert E(C_{1})\setminus E(S)\right\rvert+2\left\lvert
E_{phantom}(C_{1})\right\rvert+\left\lvert E(C_{2})\setminus
E(S)\right\rvert+2\left\lvert E_{phantom}(C_{2})\right\rvert$
$\displaystyle\geq$ $\displaystyle\left\lvert C_{1}\setminus
S\right\rvert+\left\lvert I_{\beta}\cap C_{1}\right\rvert+\left\lvert
C_{2}\setminus S\right\rvert+\left\lvert I_{\beta}\cap C_{2}\right\rvert-4.$

Equivalently, using
$2|E_{phantom}(C)|=2|E_{phantom}(C_{1})|+2|E_{phantom}(C_{2})|+2$,

$\displaystyle\left\lvert E(C)\setminus E(S)\right\rvert+2\left\lvert
E_{phantom}(C)\right\rvert-2\geq\left\lvert C\setminus
S\right\rvert+\left\lvert I_{\beta}\cap C\right\rvert-4$
$\displaystyle\Leftrightarrow$ $\displaystyle\left\lvert E(C)\setminus
E(S)\right\rvert+2\left\lvert E_{phantom}(C)\right\rvert\geq\left\lvert
C\setminus S\right\rvert+\left\lvert I_{\beta}\cap C\right\rvert-2.$

(Both are case (2)) $C$ is connected to either one or both of $U_{\tau_{P}}$
and $V_{\tau_{P}}$; we show the tighter inequality required by both, case (3).
Adding the inequalities for $C_{1}$ and $C_{2}$,

$\displaystyle\left\lvert E(C_{1})\setminus E(S)\right\rvert+2\left\lvert
E_{phantom}(C_{1})\right\rvert+\left\lvert E(C_{2})\setminus
E(S)\right\rvert+2\left\lvert E_{phantom}(C_{2})\right\rvert$
$\displaystyle\geq$ $\displaystyle\left\lvert C_{1}\setminus
S\right\rvert+\left\lvert I_{\beta}\cap C_{1}\right\rvert+\left\lvert
C_{2}\setminus S\right\rvert+\left\lvert I_{\beta}\cap C_{2}\right\rvert-2.$

Again using $2|E_{phantom}(C)|=2|E_{phantom}(C_{1})|+2|E_{phantom}(C_{2})|+2$,

$\displaystyle\left\lvert E(C)\setminus E(S)\right\rvert+2\left\lvert
E_{phantom}(C)\right\rvert-2\geq\left\lvert C\setminus
S\right\rvert+\left\lvert I_{\beta}\cap C\right\rvert-2$
$\displaystyle\Leftrightarrow$ $\displaystyle\left\lvert E(C)\setminus
E(S)\right\rvert+2\left\lvert E_{phantom}(C)\right\rvert\geq\left\lvert
C\setminus S\right\rvert+\left\lvert I_{\beta}\cap C\right\rvert.$

At the end of the process, the connectivity of the graph is the same as the
graph $\tau_{P}$ (though nonzero edge multiplicities may be modified). By
Proposition 5.14, every vertex in $V(\tau_{P})$ is connected to both
$U_{\tau_{P}}$ and $V_{\tau_{P}}$. Therefore only case (3) holds. Summing the
inequalities proves the lemma.

####  6.2.3 Proof of Theorem 1.8

The preceding lemmas are informal, but they actually show something more that
justifies Theorem 1.8. For technical reasons, our formal proof that implements
Section 6.1 will break for $d\geq n^{0.5}$, and thus it doesn’t cover Theorem
1.8, though we show that the arguments above plus the argument of [BHK+16] are
already sufficient to prove Theorem 1.8.

In the proof of Proposition 6.1 the term $\lambda_{\tau}\left\lVert
M_{\tau}\right\rVert$ was broken into three parts, each less than 1. Using
just the first two parts,

$\left\lvert\lambda_{\tau}\right\rvert\left\lVert
M_{\tau}\right\rVert\leq\widetilde{O}\left(\left(\frac{k}{\sqrt{n}}\sqrt{\frac{p}{1-p}}\right)^{|V(\tau)\setminus
S|}\left(\frac{k}{n}\right)^{\left\lvert
S\right\rvert-\frac{|U_{\tau}|+|V_{\tau}|}{2}}\right).$

Letting $k=\frac{n}{d^{1/2+\varepsilon}}$,

$\displaystyle\left\lvert\lambda_{\tau}\right\rvert\left\lVert
M_{\tau}\right\rVert$
$\displaystyle\leq\widetilde{O}\left(\left(\frac{1}{d^{\varepsilon}}\right)^{|V(\tau)|-|S|}\left(\frac{1}{d^{1/2+\varepsilon}}\right)^{\left\lvert
S\right\rvert-\frac{|U_{\tau}|+|V_{\tau}|}{2}}\right)$
$\displaystyle\leq\widetilde{O}\left(\left(\frac{1}{d^{\varepsilon}}\right)^{|V(\tau)|-|S_{\tau}|}\left(\frac{1}{d^{1/2+\varepsilon}}\right)^{\left\lvert
S_{\tau}\right\rvert-\frac{|U_{\tau}|+|V_{\tau}|}{2}}\right)$

where $S_{\tau}$ is the dense MVS of $\tau$. Observe that _this equals
$\lambda_{\tau}\left\lVert M_{\tau}\right\rVert$ in the dense case $(p=1/2$)
for a random graph of size $d$._ That is, suppose we performed the
pseudocalibration and norm bounds from [BHK+16] for a random graph $G\sim
G_{d,1/2}$. Then we would get
$\lambda_{\tau}=\left(\frac{1}{d^{1/2+\varepsilon}}\right)^{\left\lvert
V(\tau)\right\rvert-\frac{\left\lvert U_{\tau}\right\rvert+\left\lvert
V_{\tau}\right\rvert}{2}}$ and $\left\lVert M_{\tau}\right\rVert\leq(\log
d)^{O(1)}\sqrt{d}^{\left\lvert V(\tau)\right\rvert-\left\lvert
S_{\tau}\right\rvert}$, and $\lambda_{\tau}\left\lVert M_{\tau}\right\rVert$
is the same as the above. The main point is: by the analysis from [BHK+16], we
know that for shapes up to size $\Omega(\log d)$, the sum of these norms is
$o(1)$. Therefore666The log factor is $(\log n)^{O(1)}$ for our norm bound, vs
$(\log d)^{O(1)}$ for $G\sim G_{d,1/2}$, but these are the same up to a
constant for $d\geq n^{\varepsilon}$. our matrices sum to $o(1)$ for SoS
degree $\Omega(\log d)$.

The same phenomenon occurs for the intersection terms. Essentially we are
neglecting the effect of the edges and considering only the vertex factors. By
taking the first two out of three terms used in the proof of Proposition 6.7
we have the bound ($k=\frac{n}{d^{1/2+\varepsilon}}$)

$\displaystyle\left\lvert\lambda_{\gamma\circ\tau\circ\gamma^{\prime\intercal}}\right\rvert\left\lVert
M_{\tau_{P}}\right\rVert$
$\displaystyle\leq\widetilde{O}\left(\left(\frac{1}{d^{\varepsilon}}\right)^{|V(\tau_{P})|+|I_{\beta}|-|S|}\left(\frac{1}{d^{1/2+\varepsilon}}\right)^{|V(\gamma\circ\tau\circ\gamma^{\prime\intercal})|-|V(\tau_{P})|-|I_{\beta}|+|S|-\frac{|U_{\beta}|+|V_{\beta}|}{2}}\right)$
$\displaystyle\leq\widetilde{O}\left(\left(\frac{1}{d^{\varepsilon}}\right)^{|V(\tau_{P})|+|I_{\tau_{P},min}|-|S_{\tau_{P},min}|}\left(\frac{1}{d^{1/2+\varepsilon}}\right)^{|V(\gamma\circ\tau\circ\gamma^{\prime\intercal})|-|V(\tau_{P})|-|I_{\tau_{P},min}|+|S_{\tau_{P},min}|-\frac{|U_{\tau_{P}}|+|V_{\tau_{P}}|}{2}}\right)$

where $S_{\tau_{P},min}$ and $I_{\tau_{P},min}$ are the dense MVS and isolated
vertices respectively in the graph $\tau_{P}$ after deleting all multiedges.
For $G\sim G_{d,1/2}$, the pseudocalibration coefficient and norm bounds are

$\displaystyle\lambda_{\gamma\circ\tau\circ\gamma^{\prime\intercal}}$
$\displaystyle=\left(\frac{1}{d^{1/2+\varepsilon}}\right)^{\left\lvert
V(\gamma\circ\tau\circ\gamma^{\prime\intercal})\right\rvert-\frac{|U_{\gamma}|+|U_{\gamma^{\prime}}|}{2}}$
$\displaystyle\left\lVert M_{\tau_{P}}\right\rVert$ $\displaystyle\leq(\log
d)^{O(1)}\sqrt{d}^{|V(\tau_{P})|-|S_{\tau_{P},min}|+|I_{\tau_{P},min}|}.$

Multiplying these together, one can see that
$\lambda_{\gamma\circ\tau\circ\gamma^{\prime\intercal}}\left\lVert
M_{\tau_{P}}\right\rVert$ is the same. Therefore, the analysis of [BHK+16]
also shows that the sum of all intersection terms is negligible.

By passing to the “dense proxy graph” $G\sim G_{d,1/2}$, we can essentially
use [BHK+16] to deduce a degree-$\Omega(\log d)$ lower bound in the sparse
case just using connected truncation with the sparse norm bounds. The analysis
of [BHK+16] is limited to SoS degree $\Omega(\log d)$ and $d\geq
n^{\varepsilon}$. In order to push the SoS degree up and the graph degree down
in the remaining sections, we need to utilize conditioning and handle the
combinatorial terms more carefully.

###  6.3 Decomposition in terms of ribbons

We now work towards the proof of Theorem 1.4. Recall that our goal is to show
PSD-ness of the matrix
$\sum_{\alpha\in{\mathcal{S}}}\lambda_{\alpha}\frac{M_{\alpha}}{\left\lvert\operatorname{Aut}(\alpha)\right\rvert}$.

######  Definition 6.10 (Properly composable).

Composable ribbons $R_{1},\dots,R_{k}$ are properly composable if there are no
intersections beyond the necessary ones $B_{R_{i}}=A_{R_{i+1}}$.

######  Definition 6.11 (Proper composition).

Given composable ribbons $R_{1},\dots,R_{k}$ which are not necessarily
properly composable, with shapes $\alpha_{1},\dots,\alpha_{k}$, let
$R_{1}\odot R_{2}\odot\cdots\odot R_{k}$ be the shape of
$\alpha_{1}\circ\cdots\circ\alpha_{k}$.

That is, $R_{1}\odot\cdots\odot R_{k}$ is the shape obtained by concatenating
the ribbons but not collapsing vertices which repeat between ribbons, as if
they were properly composable. Compare this with $R_{1}\circ\cdots\circ
R_{k}$, in which repetitions collapse.

######  Definition 6.12 (${\mathcal{L}}$ and ${\mathcal{M}}$).

Let ${\mathcal{L}}$ and ${\mathcal{M}}$ be the set of left and middle shapes
in ${{\mathcal{S}}}$. Shapes in these sets will be denoted
$\sigma,\gamma\in{\mathcal{L}}$ and $\tau\in{\mathcal{M}}$. We abuse notation
and let $L,G\in{\mathcal{L}},T\in{\mathcal{M}}$ denote ribbons of shapes in
${\mathcal{L}},{\mathcal{M}}$ (following the convention of using Greek letters
for shapes and Latin letters for ribbons).

Formalizing the process described in Section 6.1, we have the following lemma.
It is easier to formally manipulate unsymmetrized objects, ribbons, for the
PSD decomposition and switch to symmetrized objects, shapes, only when we need
to invoke norm bounds. The details are carried out in Appendix D.

######  Lemma 6.13.

(Decomposition in terms of ribbons).

$\displaystyle\sum_{\alpha\in{\mathcal{S}}}\lambda_{\alpha}\frac{M_{\alpha}}{\left\lvert\operatorname{Aut}(\alpha)\right\rvert}=\sum_{R\in{{\mathcal{S}}}}{\lambda_{R}M_{R}}=$
$\displaystyle\left(\sum_{L\in{\mathcal{L}}}{{\lambda_{L}}M_{L}}\right)\left(\sum_{j=0}^{2D_{\text{SoS}}}{(-1)^{j}\sum_{G_{j},\ldots,G_{1},T,G^{\prime}_{1},\ldots,G^{\prime}_{j}}{\lambda_{G_{j}\odot\ldots\odot
G_{1}\odot
T\odot{G^{\prime}_{1}}^{\intercal}\odot\ldots\odot{G^{\prime}_{j}}^{\intercal}}M_{G_{j}\circ\ldots\circ
G_{1}\circ
T\circ{G^{\prime}_{1}}^{\intercal}\circ\ldots\circ{G^{\prime}_{j}}^{\intercal}}}}\right)\left(\sum_{L\in{\mathcal{L}}}{{\lambda_{L}}M_{L}}\right)^{\intercal}$
$\displaystyle+{\text{truncation error}}_{\text{too many
vertices}}+{\text{truncation error}}_{\text{too many edges in one part}}$

where

  1. 1.

$\displaystyle{\text{truncation error}}_{\text{too many
vertices}}=-\sum_{\begin{subarray}{c}L,T,L^{\prime}:\\\ |V(L\circ T\circ
L^{\prime\intercal})|>D_{V},\\\ L,T,L^{\prime\intercal}\text{ are properly
composable}\end{subarray}}\lambda_{L\circ T\circ L^{\prime\intercal}}M_{L\circ
T\circ L^{\prime\intercal}}$
$\displaystyle+\sum_{j=1}^{2D_{\text{SoS}}}{(-1)^{j+1}\sum_{\begin{subarray}{c}L,G_{j},\ldots,G_{1},T,G^{\prime}_{1},\ldots,G^{\prime}_{j},L^{\prime}:\\\
|V(L\odot G_{j}\odot\ldots\odot G_{1})|>D_{V}\text{ or}\\\
|V({G^{\prime}_{1}}^{\intercal}\odot\ldots\odot{G^{\prime}_{j}}^{\intercal}\odot{L^{\prime}}^{\intercal})|>D_{V}\end{subarray}}{\lambda_{L\odot
G_{j}\odot\ldots\odot G_{1}\odot
T\odot{G^{\prime}_{1}}^{\intercal}\odot\ldots\odot{G^{\prime}_{j}}^{\intercal}\odot{L^{\prime}}^{\intercal}}M_{L}M_{G_{j}\circ\ldots\circ
G_{1}\circ
T\circ{G^{\prime}_{1}}^{\intercal}\circ\ldots\circ{G^{\prime}_{j}}^{\intercal}}M_{L^{\prime}}^{T}}}$
$\displaystyle{\text{truncation error}}_{\text{too many edges in one
part}}=\sum_{\begin{subarray}{c}L,T,L^{\prime}:\\\ |V(L\circ T\circ
L^{\prime\intercal})|\leq D_{V},\\\ |E_{mid}(T)|-|V(T)|>C{D_{\text{SoS}}}\\\
L,T,{L^{\prime}}^{\intercal}\text{ are properly
composable}\end{subarray}}{\lambda_{L\odot
T\odot{L^{\prime}}^{\intercal}}M_{L\circ T\circ{L^{\prime}}^{T}}}$
$\displaystyle+\sum_{j=1}^{2D_{\text{SoS}}}{(-1)^{j}\sum_{\begin{subarray}{c}L,G_{j},\ldots,G_{1},T,G^{\prime}_{1},\ldots,G^{\prime}_{j},L^{\prime}:\\\
|V(L\odot G_{j}\odot\ldots\odot G_{1})|\leq D_{V}\text{ and
}|V({G^{\prime}_{1}}^{\intercal}\odot\ldots\odot{G^{\prime}_{j}}^{\intercal}\odot{L^{\prime}}^{\intercal})|\leq
D_{V}\\\ |E_{mid}(G_{j})|-|V(G_{j})|>C{D_{\text{SoS}}}\text{ or
}|E_{mid}(G^{\prime}_{j})|-|V(G^{\prime}_{j})|>C{D_{\text{SoS}}}\\\
L,(G_{j}\circ\ldots\circ G_{1}\circ
T\circ{G^{\prime}_{1}}^{\intercal}\circ\ldots\circ{G^{\prime}_{j}}^{\intercal}),{L^{\prime}}^{\intercal}\text{
are properly composable}\end{subarray}}{\lambda_{L\odot
G_{j}\odot\ldots\odot{G^{\prime}_{j}}^{\intercal}\odot{L^{\prime}}^{\intercal}}M_{L\circ
G_{j}\circ\ldots\circ{G^{\prime}_{j}}^{\intercal}\circ{L^{\prime}}^{T}}}}$

where for a ribbon $R$, $E_{mid}(R)$ is the set of edges of $R$ which are not
contained in $A_{R}$, not contained in $B_{R}$, and are not incident to any
vertices in $A_{R}\cap B_{R}$.

  2. 2.

in all of these sums, the ribbons
$L,G_{j},\ldots,G_{1},T,G^{\prime}_{1},\ldots,G^{\prime}_{j},L^{\prime}$
satisfy the following conditions:

    1. (a)

$T\in{\mathcal{M}}$, $L,L^{\prime}\in{\mathcal{L}}$, and each
$G_{i},G_{i}^{\prime}\in{\mathcal{L}}$.

    2. (b)

$L,G_{j},\ldots,G_{1},T,{G^{\prime}_{1}}^{\intercal},\ldots,{G^{\prime}_{j}}^{\intercal},L^{\prime\intercal}$
are composable.

    3. (c)

The intersection pattern induced by
$G_{j},\dots,G_{1},T,G_{1}^{\prime},\dots,G_{j}^{\prime}$ is a middle
intersection pattern.

    4. (d)

$|V(T)|\leq D_{V}$, $|V(G_{j}\odot\ldots\odot G_{1})|\leq D_{V}$, and
$|V({G^{\prime}_{1}}^{\intercal}\odot\ldots\odot{G^{\prime}_{j}}^{\intercal})|\leq
D_{V}$

    5. (e)

Except when noted otherwise (which only happens for ${\text{truncation
error}}_{\text{too many edges in one part}}$), all of the ribbons
$G_{j},\ldots,G_{1},T,G^{\prime}_{1},\ldots,G^{\prime}_{j}$ (but not
necessarily $L,L^{\prime}$) satisfy the constraint that
${|E_{mid}(R)|-|V(R)|\leq C{D_{\text{SoS}}}}$.

###  6.4 Factor out $\Pi$ and edges incident to $U_{\alpha}\cap V_{\alpha}$

We need to augment our graph matrices to include missing edge indicators.
There are two reasons. First, the dominant term in the decomposition is a
projection matrix with these indicators, rather than the identity matrix.
Second, we need to factor out dependence on $U_{\tau}\cap V_{\tau}$. These
vertices do not essentially participate in the graph matrix, since the matrix
is block diagonal with a block for each assignment to $U_{\alpha}\cap
V_{\alpha}$. (When proving things with graph matrices, it is smart to start by
assuming $U_{\alpha}\cap V_{\alpha}=\emptyset$, then handle the case
$U_{\alpha}\cap V_{\alpha}\neq\emptyset$).

For the first issue, define the matrix $\Pi$.

######  Definition 6.14.

Let $\pi\in{\mathbb{R}}^{\binom{n}{\leq D_{\text{SoS}}}\times\binom{n}{\leq
D_{\text{SoS}}}}$ be the projector to the independent set constraints. $\pi$
is a diagonal matrix with entries

$\pi[S,S]=\mathds{1}\left[S\text{ is an independent set in }G\right]$

######  Definition 6.15.

Let $\Pi\in{\mathbb{R}}^{\binom{n}{\leq D_{\text{SoS}}}\times\binom{n}{\leq
D_{\text{SoS}}}}$ be a rescaling of $\pi$ by

$\Pi[S,S]=\left(\frac{1}{1-p}\right)^{\binom{\left\lvert
S\right\rvert}{2}}\mathds{1}\left[S\text{ is an independent set in }G\right]$

The rescaling satisfies ${\mathbb{E}}_{G\sim G_{n,p}}[\Pi[S,S]]=1$. Recall
that in Proposition 2.5, we had the function
$1+\sqrt{\frac{p}{1-p}}\chi_{\\{e\\}}=\frac{1}{1-p}1_{e\notin E(G)}$ which is
$\frac{1}{1-p}$ times the indicator function for $e$ being absent from the
input graph $G$. Since the coefficients $\lambda_{R}$ come with
$\sqrt{\frac{p}{1-p}}$ for each edge, we can group the edges inside
$A_{R},B_{R}$ into missing edge indicators for all edges inside $A_{R},B_{R}$
– that is, independent set indicators on $A_{R},B_{R}$ which form the matrix
$\Pi$. For all the sums of ribbons we consider, after grouping:

$\sum_{R}\lambda_{R}M_{R}=\Pi^{1/2}\left(\sum_{R:\atop
E(A_{R})=E(B_{R})=\emptyset}\left(\frac{1}{1-p}\right)^{\binom{|A_{R}|}{2}/2+\binom{|B_{R}|}{2}/2-\binom{|A_{R}\cap
B_{R}|}{2}}\lambda_{R}M_{R}\right)\Pi^{1/2}.$

For the second issue, consider the function
$1+\sqrt{\frac{p}{1-p}}\chi_{\\{e\\}}=\frac{1}{1-p}1_{e\notin E(G)}$ again.
The magnitude of this function is clearly bounded by $\frac{1}{1-p}$. However,
if we try to bound the magnitude of this function term by term, we instead get
a bound of $2$ because $1$ always has magnitude $1$ and if $e\in E(G)$ then
$\sqrt{\frac{p}{1-p}}\chi_{\\{e\\}}=1$, so the best bound we can give on the
magnitude of $\sqrt{\frac{p}{1-p}}\chi_{\\{e\\}}$ is also $1$.

This can become a problem if $U_{\tau}\cap V_{\tau}$ is large, in which case
there are many possible subsets of edges incident to $U_{\tau}\cap V_{\tau}$
even if the rest of the shape is small. If we try to bound things term by
term, we will get a factor of $2^{|U_{\tau}\cap V_{\tau}|}$ which may be too
large. To handle this, our strategy will be to group terms into missing edge
indicators, which gives a factor of $\left(\frac{1}{1-p}\right)^{|U_{\tau}\cap
V_{\tau}|}$ per vertex instead. This almost works, however due to the
connected truncation there are some edge cases of Proposition 2.5 where we do
not have the term where $T$ is empty. We handle this using the following
lemma.

######  Lemma 6.16.

For any set of potential edges $E$,

$\sum_{E^{\prime}\subseteq
E:E^{\prime}\neq\emptyset}{\left(\sqrt{\frac{p}{1-p}}\right)^{|E^{\prime}|}\chi_{E^{\prime}}}=\sum_{e\in
E}{\left(\sqrt{\frac{p}{1-p}}\right)\chi_{\\{e\\}}\sum_{E^{\prime}\subseteq
E\setminus\\{e\\}}{\frac{1}{|E|\binom{|E|-1}{|E^{\prime}|}}\left(\frac{1}{1-p}\right)^{|E^{\prime}|}1_{\forall
e^{\prime}\in E^{\prime},e^{\prime}\notin E(G)}}}$

###### Proof.

Observe that if we give an ordering to the edges of $E$ then we can write

$\sum_{E^{\prime}\subseteq
E:E^{\prime}\neq\emptyset}{\left(\sqrt{\frac{p}{1-p}}\right)^{|E^{\prime}|}\chi_{E^{\prime}}}=\sum_{e\in
E}{\left(\sqrt{\frac{p}{1-p}}\right)\chi_{\\{e\\}}\left(\prod_{e^{\prime}\in
E:e^{\prime}>e}{\left(\frac{1}{1-p}\right)1_{e^{\prime}\notin E(G)}}\right)}$

Taking the average over all orderings of the edges of $E$ gives the result. To
see this, observe that if we take a random ordering, the probability of having
a term
$\left(\sqrt{\frac{p}{1-p}}\right)\chi_{\\{e\\}}\left(\frac{1}{1-p}\right)^{|E^{\prime}|}1_{\forall
e^{\prime}\in E^{\prime},e^{\prime}\notin E(G)}$ is
$\frac{1}{|E|\binom{|E|-1}{|E^{\prime}|}}$ as there must be exactly
$|E^{\prime}|$ elements after $e$ (so $e$ must be in the correct position) and
these elements must be $E^{\prime}$.

######  Remark 6.17.

We take the average over all orderings of the edges $E$ so that our expression
will be symmetric with respect to permuting the indices in $U_{\tau}\cap
V_{\tau}$.

Based on this lemma, we make the following definition.

######  Definition 6.18 (Quasi-indicator function).

Given a set of edges $E\subseteq\binom{[n]}{2}$, we define the quasi-missing
edge indicator function $q_{E}$ to be

$q_{E}=(1-p)^{|E|+1}\sum_{E^{\prime}\subseteq
E}{\frac{1}{(|E|+1)\binom{|E|}{|E^{\prime}|}}\left(\frac{1}{1-p}\right)^{|E^{\prime}|}1_{\forall
e\in E^{\prime},e\notin E(G)}}$

######  Proposition 6.19.

$\sum_{E^{\prime}\subseteq
E:E^{\prime}\neq\emptyset}{\left(\sqrt{\frac{p}{1-p}}\right)^{|E^{\prime}|}\chi_{E^{\prime}}}=\left(\frac{1}{1-p}\right)^{|E|}\sum_{e\in
E}{\left(\sqrt{\frac{p}{1-p}}\right)\chi_{\\{e\\}}q_{E\setminus\\{e\\}}}$

######  Remark 6.20.

$q_{E}$ is a linear combination of terms where for each edge $e\in E$, either
there is a missing edge indicator for $e$ or $e$ is not mentioned at all.
Moreover, we add the factor of $(1-p)^{|E|+1}$ to $q_{E}$ so that the
coefficients in this linear combination are non-negative and have sum at most
$1$. This is the only fact that we will use about $q_{E}$ when we analyze the
norms of the resulting graph matrices.

######  Definition 6.21 (Augmented ribbon).

An augmented ribbon is a vertex set $V(R)\subseteq[n]$ with two subsets
$A_{R},B_{R}\subseteq V(R)$, as well as a multiset of edge-functions. In our
augmentation, each edge-function is either a (single edge) Fourier character,
a (single edge) missing edge indicator, or a (subset of edges) quasi-missing
edge indicator.

######  Definition 6.22 (Matrix for an augmented ribbon).

The matrix $M_{R}$ has rows and columns indexed by all subsets of $[n]$, with
entries:

$M_{R}[I,J]=\begin{cases}\displaystyle\prod_{\text{edge-functions }f\text{ on
}S\subseteq V(R)}f(G|_{S})&I=A_{R},J=B_{R}\\\ 0&\text{Otherwise}\end{cases}$

Two augmented ribbons are isomorphic if they are in the same $S_{n}$-orbit
(i.e. they are equal after renumbering the vertices), and we define an
augmented shape for each orbit. Equivalently, augmented shapes are equivalence
classes of augmented ribbons under _type-preserving_ multi-hypergraph
isomorphism, where the type of a hyperedge is the associated function. As
before, we can specify the shape by a representative graph with edge-
functions. The graph matrix $M_{\alpha}$ for an augmented shape $\alpha$ is
still defined as the sum of $M_{R}$ over injective embeddings of $\alpha$ into
$[n]$.

######  Definition 6.23 (Permissible).

We say that an augmented ribbon $R$ is permissible if the following conditions
are satisfied:

  1. 1.

All vertices $v\in V(R)$ are reachable from $A_{R}\cup B_{R}$ using the
Fourier character edges.

  2. 2.

There is a missing edge indicator for all edges within $A_{R}$ and a missing
edge indicator for all edges within $B_{R}$.

  3. 3.

For any vertex $v\in V(R)\setminus(A_{R}\cap B_{R})$ which is reachable from
$(A_{R}\cup B_{R})\setminus(A_{R}\cap B_{R})$ without passing through
$(A_{R}\cap B_{R})$, there is a missing edge indicator for all edges between
$(A_{R}\cap B_{R})$ and $v$.

  4. 4.

For each connected component $C$ of $R\setminus(A_{R}\cap B_{R})$ which is
disconnected from $A_{R}\cup B_{R}$, there is precisely one pair of vertices
$u\in A_{R}\cap B_{R}$ and $w\in C$ such that $(u,w)\in E(R)$ and $R$ contains
the quasi-missing edge indicator $q_{\left((A_{R}\cap B_{R})\times
C\right)\setminus\\{u,w\\}}$ for all other edges between $A_{R}\cap B_{R}$ and
$C$.

  5. 5.

There are no other (quasi-)missing edge indicators, and the Fourier character
edges are disjoint from the (quasi-)missing edge indicators.

A shape is permissible if any (equivalently, all) of its ribbons are
permissible.

To explain the conditions, the first condition is the connected truncation.
The second condition follows because we factored out independent set
indicators. The third condition observes that if we have a vertex $v\in
W_{\alpha}$ that is connected to $(U_{\alpha}\cup
V_{\alpha})\setminus(U_{\alpha}\cap V_{\alpha})$, then we can factor out a
missing edge indicator for all edges that go from $v$ to $U_{\alpha}\cap
V_{\alpha}$ because such edges do not affect the connectivity properties of
$\alpha$. The fourth condition picks out components of $W_{\alpha}$ that do
affect the connectivity and handles them via the definition of quasi-missing
edge indicators as explained above.

######  Remark 6.24.

For the remainder of Section 6, ribbon means “augmented ribbon” and shape
means “augmented shape”. $E(\alpha)$ refers to the multiset of Fourier
characters edges in $\alpha$. We will write “permissible $R\in{\mathcal{S}}$”
to mean a permissible ribbon such that the corresponding non-augmented ribbon
that includes all edges involved in any edge function is in ${\mathcal{S}}$
(and similarly for other sets of ribbons/shapes).

######  Lemma 6.25.

If $\alpha$ is permissible, then $\pi M_{\alpha}=M_{\alpha}\pi=M_{\alpha}$.

###### Proof.

$\alpha$ has missing edge indicators for all edges inside $U_{\alpha}$ and
$V_{\alpha}$, hence $M_{\alpha}$ is zero on any rows or columns that are not
independent sets.

We count the extra factors of $1/(1-p)$ with the following definition.

######  Definition 6.26.

For a permissible shape or ribbon $R$, let:

$m(R)=\left(\frac{1}{1-p}\right)^{\binom{|A_{R}|}{2}/2+\binom{|B_{R}|}{2}/2-\binom{|A_{R}\cap
B_{R}|}{2}+|V(R)\setminus(A_{R}\cup B_{R})|\cdot|A_{R}\cap B_{R}|}.$

######  Lemma 6.27.

$\displaystyle\sum_{R\in{{\mathcal{S}}}}{\lambda_{R}M_{R}}=$
$\displaystyle\Pi^{1/2}\left(\sum_{\text{permissible}\atop
L\in{\mathcal{L}}}{m(L){\lambda_{L}}M_{L}}\right)\cdot$
$\displaystyle\left(\sum_{j=0}^{2D_{\text{SoS}}}{(-1)^{j}\sum_{\text{permissible}\atop
G_{j},\ldots,G_{1},T,G^{\prime}_{1},\ldots,G^{\prime}_{j}}m(T)\left(\prod_{i=1}^{j}m(G_{i})m(G_{i}^{\prime})\right){\lambda_{G_{j}\odot\ldots\odot
G_{1}\odot
T\odot{G^{\prime}_{1}}^{\intercal}\odot\ldots\odot{G^{\prime}_{j}}^{\intercal}}M_{G_{j}\circ\ldots\circ
G_{1}\circ
T\circ{G^{\prime}_{1}}^{\intercal}\circ\ldots\circ{G^{\prime}_{j}}^{\intercal}}}}\right)\cdot$
$\displaystyle\left(\sum_{\text{permissible}\atop
L\in{\mathcal{L}}}m(L){{\lambda_{L}}M_{L}}\right)^{\intercal}\Pi^{1/2}$
$\displaystyle+{\text{truncation error}}$

###### Proof.

The factoring process is completely independent of edges inside
$A_{T},B_{T},A_{G_{i}},B_{G_{i}}$ or edges incident to $A_{R}\cap B_{R}$ for
any of these shapes, as noted in Lemma D.4. All subsets of edges inside
$A_{R}$ or $B_{R}$ are present, but not all subsets of edges incident to
$A_{R}\cap B_{R}$ are present; because of the connected truncation, we do not
have the empty set of edges between $A_{R}\cap B_{R}$ and components of
$R\setminus(A_{R}\cap B_{R})$ which are disconnected from $A_{R}\cup B_{R}$.
Now group these Fourier characters into missing edge indicators and quasi-
missing edge indicators as explained above.

We can show the factor $m(R)$ is a negligible constant:

######  Lemma 6.28.

For any ribbon $R$ with degree at most $D_{\text{SoS}}$,

$m(R)\leq\left(\frac{1}{(1-p)^{2D_{\text{SoS}}}}\right)^{|V(R)\setminus(A_{R}\cap
V_{R})|}.$

###### Proof.

The claim follows from the following two inequalities:

$\binom{\left\lvert A_{R}\right\rvert}{2}/2+\binom{\left\lvert
B_{R}\right\rvert}{2}/2-\binom{\left\lvert A_{R}\cap B_{R}\right\rvert}{2}\leq
D_{\text{SoS}}(\left\lvert A_{R}\setminus(A_{R}\cap
B_{R})\right\rvert+\left\lvert B_{R}\setminus(A_{R}\cap B_{R})\right\rvert)$
$\left\lvert A_{R}\cap B_{R}\right\rvert\left\lvert V(R)\setminus(A_{R}\cup
B_{R})\right\rvert\leq D_{\text{SoS}}\left\lvert V(R)\setminus(A_{R}\cap
B_{R})\right\rvert.$

This will be handled later by the vertex decay.

###  6.5 Conditioning I: reduction to sparse shapes

To improve norm bounds for dense shapes, we can replace them by sparse ones.
The replacement of dense ribbons is accomplished by the following lemmas.

######  Lemma 6.29.

$1_{e\in E(G)}\chi_{e}=-\sqrt{p(1-p)}+(1-p)\chi_{e}$

###### Proof.

Follows by explicit computation, as in Proposition 2.5.

######  Lemma 6.30.

Given a set of edges $E$, if we know that not all of the edges of $E$ are in
$E(G)$ then

$\chi_{E}=-\sum_{E^{\prime}\subseteq E:E^{\prime}\neq
E}{\left(-\sqrt{\frac{p}{1-p}}\right)^{|E|-|E^{\prime}|}\chi_{E^{\prime}}}$

###### Proof.

Since not all of the edges of $E$ are in $E(G)$, $(1-1_{E\subseteq
E(G)})\chi_{E}=\chi_{E}$. Now observe that

$1_{E\subseteq E(G)}\chi_{E}=\prod_{e\in E}{(1_{e\in
E(G)}\chi_{e})}=\prod_{e\in E}{(-\sqrt{p(1-p)}+(1-p)\chi_{e})}$

Thus,

$\chi_{E}=(1-1_{E\subseteq
E(G)})\chi_{E}=(1-(1-p)^{|E|})\chi_{E}-\sum_{E^{\prime}\subseteq
E:E^{\prime}\neq
E}{(-\sqrt{p(1-p)})^{|E|-|E^{\prime}|}(1-p)^{|E^{\prime}|}\chi_{E^{\prime}}}$

Solving for $\chi_{E}$ gives

$\chi_{E}=-\sum_{E^{\prime}\subseteq E:E^{\prime}\neq
E}{\left(-\sqrt{\frac{p}{1-p}}\right)^{|E|-|E^{\prime}|}\chi_{E^{\prime}}}$

######  Corollary 6.31.

Given a set of edges $E$, if we know that at most $k<|E|$ of the edges of $E$
are in $E(G)$, then

$\chi_{E}=(-1)^{|E|-k}\sum_{E^{\prime}\subseteq E:|E^{\prime}|\leq
k}\binom{|E|-1-|E^{\prime}|}{|E|-1-k}\left(-\sqrt{\frac{p}{1-p}}\right)^{|E|-|E^{\prime}|}\chi_{E^{\prime}}.$

###### Proof.

Apply Lemma 6.30 repeatedly.

######  Corollary 6.32.

Given a set of edges $E$, if we know that at most $k<|E|$ of the edges of $E$
are in $E(G)$, then

$\chi_{E}=\sum_{E^{\prime}\subseteq E:|E^{\prime}|\leq
k}c_{E^{\prime}}\chi_{E^{\prime}}$

where $\left\lvert
c_{E^{\prime}}\right\rvert\leq(2|E|\sqrt{p})^{|E|-|E^{\prime}|}$.

We can do the replacement if the graph of the shape does not occur in our
random sample of $G\sim G_{n,p}$. We formalize a bound on the density of
subgraphs of $G_{n,p}$. In expectation the number of occurrences of a small
subgraph $H$ is essentially $n^{\left\lvert V(H)\right\rvert}p^{\left\lvert
E(H)\right\rvert}$ and hence $H$ is unlikely to appear in a random graph
sample if it has too many edges (specifically, morally all subgraphs are
sparse, $|E(H)|\leq|V(H)|\log_{1/p}(n)$). To translate from expectation to
concentration, we use a simple first moment calculation to bound the
densest-$k$-subgraph in $G_{n,p}$.

######  Proposition 6.33 (Sparsity of small subgraphs of $G_{n,p}$).

For $G\sim G_{n,p},p\leq\frac{1}{2}$, constant $\eta>0$, with probability at
least $1-O(1/n^{\eta})$, every subgraph $S$ of $G$ such that
$|V(S)|\leq\sqrt[3]{\frac{n}{d}}$ satisfies:

$|E(S)|\leq 3|V(S)|\log_{1/p}(n)+3\eta\log_{1/p}(n).$

###### Proof.

Let $e^{*}(v):=3v\log_{1/p}(n)+3\eta\log_{1/p}(n)$.

$\displaystyle\Pr[\exists\text{too dense subgraph}]$
$\displaystyle\leq\sum_{v=2}^{n}\sum_{e=e^{*}(v)}^{\binom{v}{2}}{\mathbb{E}}[\text{number
of subgraphs with $v$ vertices, $e$ edges}]$
$\displaystyle\leq\sum_{v=2}^{n}\sum_{e=e^{*}(v)}^{\binom{v}{2}}\binom{n}{v}v^{2e}p^{e}$
$\displaystyle\leq\sum_{v=2}^{n}\sum_{e=e^{*}(v)}^{\binom{v}{2}}\frac{n^{v}}{v!}(p^{1/3})^{e}$
$\displaystyle=\sum_{v=2}^{n}\sum_{e=e^{*}(v)}^{\binom{v}{2}}\frac{n^{v}p^{e^{*}(v)/3}}{v!}(p^{1/3})^{e-e^{*}(v)}$
$\displaystyle=\sum_{v=2}^{n}\sum_{e=e^{*}(v)}^{\binom{v}{2}}\frac{1}{n^{\eta}\cdot
v!}(p^{1/3})^{e-e^{*}(v)}$ $\displaystyle\leq O(1/{n^{\eta}}).$

######  Definition 6.34 (Sparse).

A graph $G$ is $C^{\prime}$-sparse if $\left\lvert E(G)\right\rvert\leq
C^{\prime}\left\lvert V(G)\right\rvert$. A shape $\alpha$ is
$C^{\prime}$-sparse if the underlying graph (not multigraph) is. We will
generally say that a graph/shape is sparse if it is $C^{\prime}$-sparse for
some $C^{\prime}$.

######  Corollary 6.35.

For $d\leq n^{0.5}$, w.h.p. every subgraph of $G\sim G_{n,\frac{d}{n}}$ of
size at most $n^{0.16}$ is 7-sparse.

######  Definition 6.36 (Forbidden subgraph).

We call a graph $H$ forbidden if it does not occur as a subgraph of $G$.

The assumptions in Theorem 1.4 ensure that every graph of size at most $D_{V}$
that is not sparse is forbidden per Corollary 6.35. This is the only class of
forbidden graphs that we will need in this work.

######  Remark 6.37.

For $d=n^{1-\varepsilon}$, subgraphs up to size $n^{\Omega(\varepsilon)}$ will
be $O(1/\varepsilon)$-sparse. Using this bound and our techniques, Theorem 1.4
can be extended to show a $n^{\Omega(\varepsilon)}$ SoS-degree lower bound for
$d=n^{1-\varepsilon}$.

######  Remark 6.38.

For $d\ll n^{\varepsilon}$, subgraphs of $G_{n,p}$ will actually be
significantly sparser. For example, it is well-known that $o(\log n)$-radius
neighborhoods in $G_{n,d/n}$ for constant $d$ are trees with at most one extra
cycle.

######  Definition 6.39 (Subshape/subribbon, supershape/superribbon).

We call shape $\beta$ a sub-shape of shape $\alpha$ if $V(\alpha)=V(\beta)$,
$U_{\alpha}=U_{\beta},V_{\alpha}=V_{\beta}$, and $E(\beta)\subseteq
E(\alpha)$. Furthermore, the (quasi-)missing edge indicators of $\beta$ and
$\alpha$ must be equal. Supershapes, subribbons, and superribbons are defined
similarly. We write $\alpha\subseteq\beta$ if $\alpha$ is a subshape of
$\beta$.

######  Definition 6.40.

For a sparse subribbon $R$ of a forbidden ribbon $U$, let $c(R,U)$ be the
coefficient on $R$ after applying conditioning Corollary 6.31 to the non-
reserved edges of $U$.

######  Definition 6.41.

Let $\lambda^{\prime}_{R}$ incorporate the constant factors into
$\lambda_{R}$,777 When $R$ is a left $L$ /middle $T$/intersecting $G$ ribbon,
the sum over $U$ should be restricted to $U$ with the same type, and which
actually appear in the decomposition. The stated sum is an upper bound.

$\displaystyle\lambda^{\prime}_{R}$
$\displaystyle:=m(R)\displaystyle\left(\sum_{U\supseteq
R}c(R,U)\lambda_{U}\right)\lambda_{R},$
$\displaystyle\lambda^{\prime}_{R_{1}\odot\cdots\odot R_{k}}$
$\displaystyle:=\prod_{i=1}^{k}\lambda^{\prime}_{R_{i}}.$

######  Lemma 6.42.

$\displaystyle\sum_{R\in{{\mathcal{S}}}}{\lambda_{R}M_{R}}=$
$\displaystyle\Pi^{1/2}\left(\sum_{\begin{subarray}{c}\text{sparse}\\\
\text{permissible}\\\
L\in{\mathcal{L}}\end{subarray}}{{\lambda_{L}^{\prime}}M_{L}}\right)\cdot$
$\displaystyle\left(\sum_{j=0}^{2D_{\text{SoS}}}{(-1)^{j}\sum_{\begin{subarray}{c}\text{sparse}\\\
\text{permissible}\\\
G_{j},\ldots,G_{1},T,G^{\prime}_{1},\ldots,G^{\prime}_{j}\end{subarray}}{\lambda^{\prime}_{G_{j}\odot\ldots\odot
G_{1}\odot
T\odot{G^{\prime}_{1}}^{\intercal}\odot\ldots\odot{G^{\prime}_{j}}^{\intercal}}M_{G_{j}\circ\ldots\circ
G_{1}\circ
T\circ{G^{\prime}_{1}}^{\intercal}\circ\ldots\circ{G^{\prime}_{j}}^{\intercal}}}}\right)\cdot$
$\displaystyle\left(\sum_{\begin{subarray}{c}\text{sparse}\\\
\text{permissible}\\\
L\in{\mathcal{L}}\end{subarray}}{{\lambda^{\prime}_{L}}M_{L}}\right)^{\intercal}\Pi^{1/2}$
$\displaystyle+{\text{truncation error}}$

The proof follows mostly by definition of $\lambda^{\prime}_{R}$ but there is
an important detail. When we condition a left $L$/middle $T$/intersection $G$
ribbon, the result may no longer be a left/middle/intersection ribbon. For
example, the MVS might change drastically. It turns out that we can avoid this
by “reserving” $O(|V(R)|)$ edges in the ribbon and only allowing the removal
of edges outside of the reserved set. The reserved edges guarantee that the
subribbon will continue to be a left/middle/intersection ribbon, at the cost
of increasing the sparsity. We prove that $O(|V(R)|)$ edges suffice in
Appendix B.

We can show that the conditioning negligibly affects the coefficients of the
ribbons.

######  Lemma 6.43.

Under the conditions of Theorem 1.4, for any ribbon $R\in{\mathcal{S}}$,

$\sum_{U\supset R}\lambda_{U}c(R,U)=o(1)\lambda_{R}.$

###### Proof.

Let $U$ be a superribbon with $k$ more edges than $R$. We have

$\lambda_{U}=\left(\sqrt{\frac{p}{1-p}}\right)^{k}\lambda_{U}\leq(2\sqrt{p})^{k}\lambda_{R}.$
(1)

Using the bound from Corollary 6.32,

$|c(R,U)|\leq(2|E(U)|\sqrt{p})^{k}\leq(2|V(R)|^{2}\sqrt{p})^{k}.$ (2)

The number of ribbons $U$ that are superribbons of $R$ with $k$ extra edges is
at most

$|V(R)|^{2k}$ (3)

because (see Appendix B) due to the connectivity of the reserved set, the
vertex set of $U$ and $R$ is the same. Combining Eq. 1, Eq. 2, Eq. 3, the
change in coefficient is at most

$\sum_{k=1}^{\infty}\lambda_{R}(4|V(R)|^{4}p)^{k}\leq\sum_{k=1}^{\infty}\lambda_{R}\left(\frac{4D_{V}^{4}d}{n}\right)^{k}\leq
o(1)\lambda_{R}.$

The last inequality uses $d\leq n^{0.5}$ and
$D_{V}\leq\widetilde{O}(D_{\text{SoS}})\leq\widetilde{O}(n^{0.1})$.

###  6.6 Shifting to shapes

For a proper middle shape $\tau$ and left shapes
$\gamma_{j},\dots,\gamma_{1},\gamma_{1}^{\prime},\dots,\gamma_{j}^{\prime}$,
recall the notation
${\mathcal{P}}^{mid}_{\gamma_{j},\dots,\gamma_{1},\tau,\gamma_{1}^{\prime},\dots,\gamma_{j}^{\prime}}$
for the set of middle intersection patterns (Definition 6.3 and Remark 6.5).
We also let ${\mathcal{P}}^{mid}_{\tau}$ contain a single term, the non-
intersecting singleton partition.

We now analyze

$\sum_{\begin{subarray}{c}\text{sparse}\\\ \text{permissible}\\\
G_{j},\ldots,G_{1},T,G^{\prime}_{1},\ldots,G^{\prime}_{j}\end{subarray}}{\lambda^{\prime}_{G_{j}\odot\ldots\odot
G_{1}\odot
T\odot{G^{\prime}_{1}}^{\intercal}\odot\ldots\odot{G^{\prime}_{j}}^{\intercal}}M_{G_{j}\circ\ldots\circ
G_{1}\circ
T\circ{G^{\prime}_{1}}^{\intercal}\circ\ldots\circ{G^{\prime}_{j}}^{\intercal}}}$

We first partition this sum based on the shapes
$\gamma_{j},\ldots,\gamma_{1},\tau,\gamma^{\prime}_{1},\ldots,\gamma^{\prime}_{j}$
of $G_{j},\ldots,G_{1},T,G^{\prime}_{1},\ldots,G^{\prime}_{j}$. We then
partition this sum further based on the intersection pattern
$P\in{\mathcal{P}}^{mid}_{\gamma_{j},\dots,\gamma_{1},\tau,\gamma_{1}^{\prime},\dots,\gamma_{j}^{\prime}}$.

######  Definition 6.44.

Define $N_{P}(\tau_{P})$ to be the number of ways to choose ribbons
$G_{j},\ldots,G_{1},T,G^{\prime}_{1},\ldots,G^{\prime}_{j}$ of shapes
$\gamma_{j},\dots,\gamma_{1},\tau,\gamma_{1}^{\prime},\dots,\gamma_{j}^{\prime}$
so that they have intersection pattern $P$ and $G_{j}\circ\ldots\circ
G_{1}\circ
T\circ{G^{\prime}_{1}}^{\intercal}\circ\ldots\circ{G^{\prime}_{j}}^{\intercal}=T_{P}$
for a given ribbon $T_{P}$ of shape $\tau_{P}$.

By symmetry, this is independent of the choice of $T_{P}$.

Recall that an intersection pattern specifies both intersections and how the
shapes should be glued together via bijections between the $V$ of each shape
and the $U$ of the following shape (Definition 5.6).

######  Definition 6.45.

We say that two intersection patterns are equivalent if there is an element of

$Aut(\gamma_{j})\times\ldots\times Aut(\gamma_{j})\times Aut(\tau)\times
Aut({\gamma_{1}^{\prime}}^{\intercal})\times\ldots\times
Aut({\gamma_{j}^{\prime}}^{\intercal})$

which maps one intersection pattern to the other (where the gluing maps are
permuted accordingly).

This gives us the following equation:

$\displaystyle\sum_{\begin{subarray}{c}\text{sparse}\\\ \text{permissible}\\\
G_{j},\ldots,G_{1},T,G^{\prime}_{1},\ldots,G^{\prime}_{j}\end{subarray}}{\lambda^{\prime}_{G_{j}\odot\ldots\odot
G_{1}\odot
T\odot{G^{\prime}_{1}}^{\intercal}\odot\ldots\odot{G^{\prime}_{j}}^{\intercal}}M_{G_{j}\circ\ldots\circ
G_{1}\circ
T\circ{G^{\prime}_{1}}^{\intercal}\circ\ldots\circ{G^{\prime}_{j}}^{\intercal}}}$
$\displaystyle=\sum_{\begin{subarray}{c}\text{sparse}\\\ \text{permissible}\\\
\gamma_{j},\ldots,\gamma_{1},\tau,\gamma^{\prime}_{1},\ldots,\gamma^{\prime}_{j}\end{subarray}}\sum_{\begin{subarray}{c}\text{nonequivalent}\\\
P\in{\mathcal{P}}^{mid}_{\gamma_{j},\dots,\gamma_{1},\tau,\gamma^{\prime}_{1},\dots,\gamma^{\prime}_{j}}\end{subarray}}N_{P}(\tau_{P})\lambda^{\prime}_{\gamma_{j}\circ\cdots\circ\gamma_{1}\circ\tau\circ\gamma_{1}^{\prime\intercal}\circ\cdots\circ\gamma_{j}^{\prime\intercal}}\frac{M_{\tau_{P}}}{|\operatorname{Aut}(\tau_{P})|}$

Grouping into shapes, here is the full decomposition:

######  Lemma 6.46 (Decomposition in terms of shapes).

$\displaystyle\sum_{R\in{{\mathcal{S}}}}{\lambda_{R}M_{R}}=$
$\displaystyle\Pi^{1/2}\left(\sum_{\begin{subarray}{c}\text{sparse}\\\
\text{permissible}\\\
\sigma\in{\mathcal{L}}\end{subarray}}{{\lambda_{\sigma}^{\prime}}\frac{M_{\sigma}}{|\operatorname{Aut}(\sigma)|}}\right)\cdot$
$\displaystyle\left(\sum_{j=0}^{2D_{\text{SoS}}}{(-1)^{j}\sum_{\begin{subarray}{c}\text{sparse}\\\
\text{permissible}\\\
\gamma_{j},\ldots,\gamma_{1},\tau,\gamma^{\prime}_{1},\ldots,\gamma^{\prime}_{j}\end{subarray}}\sum_{\begin{subarray}{c}\text{nonequivalent}\\\
P\in{\mathcal{P}}^{mid}_{\gamma_{j},\dots,\gamma_{1},\tau,\gamma^{\prime}_{1},\dots,\gamma^{\prime}_{j}}\end{subarray}}N_{P}(\tau_{P})\lambda^{\prime}_{\gamma_{j}\circ\cdots\circ\gamma_{1}\circ\tau\circ\gamma_{1}^{\prime\intercal}\circ\cdots\circ\gamma_{j}^{\prime\intercal}}\frac{M_{\tau_{P}}}{|\operatorname{Aut}(\tau_{P})|}}\right)\cdot$
$\displaystyle\left(\sum_{\begin{subarray}{c}\text{sparse}\\\
\text{permissible}\\\