trivial}}{\frac{1}{|Aut(U_{\gamma_{i}})|}}\prod_{i:\gamma^{\prime}_{i}\text{
is non-
trivial}}{\frac{1}{|Aut(U_{\gamma^{\prime}_{i}})|}}}}\sum_{P_{1},\cdots,P_{j}:P_{i}\in\mathcal{P}_{\gamma_{i},\tau_{P_{i-1}},{\gamma^{\prime}_{i}}^{T}}}{\left(\prod_{i=1}^{j}{N(P_{i})}\right)}$
$\displaystyle\leq\frac{N(\gamma)N(\gamma^{\prime})}{(|Aut(U_{\gamma})|)^{1_{\gamma\text{
is non-trivial}}}(|Aut(U_{\gamma^{\prime}})|)^{1_{\gamma^{\prime}\text{ is
non-trivial}}}}$

####  9.1.1 General functions $B_{norm}(\alpha)$, $B(\gamma)$, $N(\gamma)$,
and $c(\alpha)$*

Recall the following definitions from Section 7.10.1.

######  Definition 9.4 ($S_{\alpha,min}$ and $S_{\alpha,max}$).

Given a shape $\alpha\in\mathcal{M}^{\prime}$, define $S_{\alpha,min}$ to be
the leftmost minimum vertex separator of $\alpha$ if all edges with
multiplicity at least $2$ are deleted and define $S_{\alpha,max}$ to be the
leftmost minimum vertex separator of $\alpha$ if all edges with multiplicity
at least $2$ are present.

######  Definition 9.5 (General $I_{\alpha}$).

Given a shape $\alpha$, define $I_{\alpha}$ to be the set of vertices in
$V(\alpha)\setminus(U_{\alpha}\cup V_{\alpha})$ such that all edges incident
with that vertex have multplicity at least $2$.

######  Definition 9.6 ($B_{\Omega}$).

We take $B_{\Omega}(j)$ to be a non-decreasing function such that for all
$j\in\mathbb{N}$, $E_{\Omega}[x^{j}]\leq B_{\Omega}(j)^{j}$

######  Definition 9.7.

For all $i$, we define $h^{+}_{i}$ to be the polynomial $h_{i}$ where we make
all of the coefficients have positive sign.

######  Lemma 9.8.

If $\Omega=N(0,1)$ then we can take $B_{\Omega}(j)=\sqrt{j}$ and we have that

######  Theorem 9.9 (General $B_{norm}(\alpha)$, $B(\gamma)$, $N(\gamma)$, and
$c(\alpha)$).

For all $\varepsilon,\varepsilon^{\prime}>0$ and all
$D_{V},D_{E}\in\mathbb{N}$, if we take

  1. 1.

$q=\left\lceil{3{D_{V}}ln(n)+ln(\frac{1}{\varepsilon})+{(3D_{V})^{k}}ln(D_{E}+1)+3{D_{V}}ln(5)}\right\rceil$

  2. 2.

$B_{vertex}=6q{D_{V}}$

  3. 3.

$B_{edge}(e)=2h^{+}_{l_{e}}(B_{\Omega}(6{D_{V}}D_{E}))\max_{j\in[0,3{D_{V}}D_{E}]}{\left\\{\left(h^{+}_{j}(B_{\Omega}(2qj))\right)^{\frac{l_{e}}{\max{\\{j,l_{e}\\}}}}\right\\}}$

  4. 4.

$B_{norm}(\alpha)=2e{B_{vertex}^{|V(\alpha)\setminus
U_{\alpha}|+|V(\alpha)\setminus V_{\alpha}|}}\left(\prod_{e\in
E(\alpha)}{B_{edge}(e)}\right)n^{\frac{w(V(\alpha))+w(I_{\alpha})-w(S_{\alpha})}{2}}$

  5. 5.

$B(\gamma)=B_{vertex}^{|V(\gamma)\setminus U_{\gamma}|+|V(\gamma)\setminus
V_{\gamma}|}\left(\prod_{e\in
E(\gamma)}{B_{edge}(e)}\right)n^{\frac{w(V(\gamma)\setminus U_{\gamma})}{2}}$

  6. 6.

$N(\gamma)=(3D_{V})^{2|V(\gamma)\setminus V_{\gamma}|+|V(\gamma)\setminus
U_{\gamma}|}$

  7. 7.

$c(\alpha)=\frac{5(3{t_{max}}D_{V})^{|U_{\alpha}\setminus
V_{\alpha}|+|V_{\alpha}\setminus
U_{\alpha}|+k|E(\alpha)|}(2t_{max})^{|V(\alpha)\setminus(U_{\alpha}\cup
V_{\alpha})|}}{\varepsilon^{\prime}}$

then the following conditions hold:

  1. 1.

With probability at least $(1-\varepsilon)$,
$\forall\alpha\in\mathcal{M}^{\prime}$, $||M_{\alpha}||\leq B_{norm}(\alpha)$

  2. 2.

For all $\tau\in\mathcal{M}^{\prime}$,
$\gamma\in\Gamma_{*,U_{\tau}}\cup\\{Id_{U_{\tau}}\\}$,
$\gamma^{\prime}\in\Gamma_{*,V_{\tau}}\cup\\{Id_{V_{\tau}}\\}$, and
intersection patterns $P\in\mathcal{P}_{\gamma,\tau,\gamma^{\prime}}$,

$B_{norm}(\tau_{P})\leq B(\gamma)B(\gamma^{\prime})B_{norm}(\tau)$

  3. 3.

For all composable $\gamma_{1},\gamma_{2}$,
$B(\gamma_{1})B(\gamma_{2})=B(\gamma_{1}\circ\gamma_{2})$.

  4. 4.

$\forall
U\in\mathcal{I}_{mid},\sum_{\gamma\in\Gamma_{U,*}}{\frac{1}{|Aut(U)|c(\gamma)}}<\varepsilon^{\prime}$

  5. 5.

$\forall
V\in\mathcal{I}_{mid},\sum_{\gamma\in\Gamma_{*,V}}{\frac{1}{|Aut(U_{\gamma})|c(\gamma)}}<\varepsilon^{\prime}$

  6. 6.

$\forall
U\in\mathcal{I}_{mid},\sum_{\tau\in\mathcal{M}_{U}}{\frac{1}{|Aut(U)|c(\tau)}}<\varepsilon^{\prime}$

  7. 7.

For all $\tau\in\mathcal{M}^{\prime}$,
$\gamma\in\Gamma_{*,U_{\tau}}\cup\\{Id_{U_{\tau}}\\}$, and
$\gamma^{\prime}\in\Gamma_{*,V_{\tau}}\cup\\{Id_{V_{\tau}}\\}$,

$\displaystyle\sum_{j>0}{\sum_{\gamma_{1},\gamma^{\prime}_{1},\cdots,\gamma_{j},\gamma^{\prime}_{j}\in\Gamma_{\gamma,\gamma^{\prime},j}}{\prod_{i:\gamma_{i}\text{
is non-
trivial}}{\frac{1}{|Aut(U_{\gamma_{i}})|}}\prod_{i:\gamma^{\prime}_{i}\text{
is non-
trivial}}{\frac{1}{|Aut(U_{\gamma^{\prime}_{i}})|}}}}\sum_{P_{1},\cdots,P_{j}:P_{i}\in\mathcal{P}_{\gamma_{i},\tau_{P_{i-1}},{\gamma^{\prime}_{i}}^{T}}}{\left(\prod_{i=1}^{j}{N(P_{i})}\right)}$
$\displaystyle\leq\frac{N(\gamma)N(\gamma^{\prime})}{(|Aut(U_{\gamma})|)^{1_{\gamma\text{
is non-trivial}}}(|Aut(U_{\gamma^{\prime}})|)^{1_{\gamma^{\prime}\text{ is
non-trivial}}}}$

######  Remark 9.10.

Recall that if $\Omega=N(0,1)$ then we may take $B_{\Omega}(j)=\sqrt{j}$ and
we have that

$h^{+}_{j}(x)\leq\frac{1}{\sqrt{j!}}(x^{2}+j)^{\frac{j}{2}}\leq\left(\frac{e}{j}(x^{2}+j)\right)^{\frac{j}{2}}$

Thus, when $\Omega=N(0,1)$ we can take

$B_{edge}(e)=2\left(\frac{e}{l_{e}}(6{D_{V}}D_{E}+l_{e})\right)^{l_{e}}\left(e(6{D_{V}}{D_{E}}q+1)\right)^{l_{e}}\leq\left(400{D^{2}_{V}}{D^{2}_{E}}q\right)^{l_{e}}$

###  9.2 Choosing $B_{norm}(\alpha)$

We need matrix norm bounds which hold for all $\alpha\in\mathcal{M}^{\prime}$.
For convenience, we recall the definition of $\mathcal{M}^{\prime}$ below.

######  Definition 9.11 ($\mathcal{M}^{\prime}$).

We define $\mathcal{M}^{\prime}$ to be the set of all shapes $\alpha$ such
that

  1. 1.

$|V(\alpha)|\leq 3D_{V}$

  2. 2.*

$\forall e\in E(\alpha),l_{e}\leq D_{E}$

  3. 3.*

All edges $e\in E(\alpha)$ have multiplicity at most $3D_{V}$.

To obtain such norm bounds, we start with the norm bounds in the graph matrix
norm bound paper. We then modify these bounds as follows:

  1. 1.

We make the bounds more compatible with the conditions of our machinery. To do
this, we upper bound many of the terms in the norm bound by
$B_{vertex}^{|V(\alpha)\setminus U_{\alpha}|+|V(\alpha)\setminus V_{\alpha}|}$
where $B_{vertex}$ is a function of our parameters. In general, we will also
need to upper bound some of the terms by $\prod_{e\in E(\alpha)}(B_{edge}(e))$
where $B_{edge}(e)$ is a function of $l_{e}$, $\Omega$, and our parameters.

  2. 2.

We generalize the bounds so that they apply to improper shapes as well as
proper shapes. Under our simplifying assumptions, all we need to do here is to
take isolated vertices into account. In general, we also need to handle multi-
edges.

####  9.2.1 Simplified $B_{norm}(\alpha)$

Under our simplifying assumptions, we start with the following norm bound from
the updated graph matrix norm bound paper [AMP20]:

######  Theorem 9.12 (Simplified Graph Matrix Norm Bounds).

Under our simplifying assumptions, for all $\varepsilon>0$ and all proper
shapes $\alpha$, taking $c_{\alpha}=|V(\alpha)\setminus(U_{\alpha}\cup
V_{\alpha})|+|S_{\alpha}\setminus(U_{\alpha}\cap V_{\alpha})|$,

$Pr\left(||M_{\alpha}||>(2|V_{\alpha}\setminus(U_{\alpha}\cap
V_{\alpha})|)^{|V(\alpha)\setminus(U_{\alpha}\cap
V_{\alpha})|}(2eq)^{\frac{c_{\alpha}}{2}}n^{\frac{w(V(\alpha))-w(S_{\alpha})}{2}}\right)<\varepsilon$

where
$q=3\left\lceil\frac{ln(\frac{n^{w(S_{\alpha})}}{\varepsilon})}{3c_{\alpha}}\right\rceil$

######  Corollary 9.13.

For all shapes $\alpha$ and all $\varepsilon>0$,

$Pr\left(||M_{\alpha}||>\left(2|V_{\alpha}|\sqrt[4]{2eq}\right)^{|V(\alpha)\setminus
U_{\alpha}|+|V(\alpha)\setminus
V_{\alpha}|}n^{\frac{w(V(\alpha))+w(I_{\alpha})-w(S_{\alpha})}{2}}\right)<\varepsilon$

where
$q=3\left\lceil\frac{ln(\frac{n^{w(S_{\alpha})}}{\varepsilon})}{3c_{\alpha}}\right\rceil$.

###### Proof.

Observe that adding an isolated vertex to $\alpha$ is equivalent to
multiplying $M_{\alpha}$ by $n-|V(\alpha)|$. Thus, if the bound holds for all
proper $\alpha$ then it will hold for improper $\alpha$ as well.

We now make the following observations:

  1. 1.

$|S_{\alpha}\setminus(U_{\alpha}\cap V_{\alpha})|\leq|U_{\alpha}\setminus
V_{\alpha}|$, so $c_{\alpha}=|W_{\alpha}|+|S_{\alpha}\setminus(U_{\alpha}\cap
V_{\alpha})|\leq|V(\alpha)\setminus V_{\alpha}|$. Similarly,
$|S_{\alpha}\setminus(U_{\alpha}\cap V_{\alpha})|\leq|V_{\alpha}\setminus
U_{\alpha}|$, so $c_{\alpha}\leq|V(\alpha)\setminus U_{\alpha}|$. Thus,
$c_{\alpha}\leq\frac{|V(\alpha)\setminus U_{\alpha}|+|V(\alpha)\setminus
V_{\alpha}|}{2}$.

  2. 2.

$|V(\alpha)\setminus(U_{\alpha}\cap V_{\alpha})|\leq|V(\alpha)\setminus
U_{\alpha}|+|V(\alpha)\setminus V_{\alpha}|$

Thus, by Theorem 9.12, for all proper shapes $\alpha$ and all $\varepsilon>0$,

$Pr\left(||M_{\alpha}||>\left(2|V_{\alpha}|\sqrt[4]{2eq}\right)^{|V(\alpha)\setminus
U_{\alpha}|+|V(\alpha)\setminus
V_{\alpha}|}n^{\frac{w(V(\alpha))+w(I_{\alpha})-w(S_{\alpha})}{2}}\right)<\varepsilon^{\prime\prime}$

where
$q=3\left\lceil\frac{ln(\frac{n^{w(S_{\alpha})}}{\varepsilon})}{3c_{\alpha}}\right\rceil$.

######  Corollary 9.14.

For all $z\in\mathbb{N}$ and all $\varepsilon>0$, taking
$\varepsilon^{\prime\prime}=\frac{\varepsilon}{5^{z}2^{z^{2}}}$, with
probability at least $1-\varepsilon$ we have that for all shapes $\alpha$ such
that $|V(\alpha)|\leq z$,

$||M_{\alpha}||\leq\left(2|V_{\alpha}|\sqrt[4]{2eq}\right)^{|V(\alpha)\setminus
U_{\alpha}|+|V(\alpha)\setminus
V_{\alpha}|}n^{\frac{w(V(\alpha))+w(I_{\alpha})-w(S_{\alpha})}{2}}$

where
$q=3\left\lceil\frac{ln(\frac{n^{w(S_{\alpha})}}{\varepsilon^{\prime\prime}})}{3c_{\alpha}}\right\rceil$.

###### Proof.

This result can be proved from Corollary 9.13 using a union bound and the
following proposition:

######  Proposition 9.15.

Under our simplifying assumptions, for all $z\in\mathbb{N}$, there are at most
$5^{z}2^{z^{2}}$ proper shapes $\alpha$ such that $V(\alpha)\leq z$.

###### Proof.

Observe that we can construct any proper shape $\alpha$ with at most $m$
vertices as follows:

  1. 1.

Start with $z$ vertices $v_{1},\ldots,v_{z}$.

  2. 2.

For each vertex $v_{i}$, choose whether $v_{i}\in V(\alpha)\setminus
U_{\alpha}\setminus V_{\alpha}$, $v_{i}\in U_{\alpha}\setminus V_{\alpha}$,
$v_{i}\in V_{\alpha}\setminus U_{\alpha}$, $v_{i}\in U_{\alpha}\cap
V_{\alpha}$, or $v_{i}\notin V(\alpha)$.

  3. 3.

For each pair of vertices $v_{i},v_{j}\in V(\alpha)$, choose whether or not
$(v_{i},v_{j})\in E(\alpha)$

######  Corollary 9.16.

For all $D_{V}\in\mathbb{N}$ and all $\varepsilon>0$, taking

$q=3\left\lceil\frac{ln(\frac{5^{3D_{V}}2^{9D^{2}_{V}}n^{3D_{V}}}{\varepsilon})}{3}\right\rceil=3\left\lceil{{D_{V}}ln(n)+\frac{ln(\frac{1}{\varepsilon})}{3}+{D_{V}}ln(5)+3{D^{2}_{V}}ln(2)}\right\rceil,$

$B_{vertex}=6{D_{V}}\sqrt[4]{2eq}$, and

$B_{norm}(\alpha)={B_{vertex}^{|V(\alpha)\setminus
U_{\alpha}|+|V(\alpha)\setminus
V_{\alpha}|}}n^{\frac{w(V(\alpha))+w(I_{\alpha})-w(S_{\alpha})}{2}},$

with probability at least $(1-\varepsilon)$ we have that for all shapes
$\alpha\in\mathcal{M}^{\prime}$, $||M_{\alpha}||\leq B_{norm}(\alpha)$

###### Proof.

This follows from Corollary 9.14 and the fact that for all
$\alpha\in\mathcal{M}^{\prime}$, $w(S_{\alpha})\leq|V(\alpha)|\leq 3D_{V}$

####  9.2.2 General $B_{norm}(\alpha)$

In general, we start with the following norm bound from the updated graph
matrix norm bound paper [AMP20]:

######  Theorem 9.17 (General Graph Matrix Norm Bounds).

For all $\varepsilon>0$ and all proper shapes $\alpha$, taking
$q=\lceil{ln(\frac{n^{w(S_{\alpha})}}{\varepsilon})}\rceil$

$P\left(||M_{\alpha}||>2e(2q|V(\alpha)|)^{|V(\alpha)\setminus(U_{\alpha}\cap
V_{\alpha})|}\left(\prod_{e\in
E(\alpha)}{h^{+}_{l_{e}}(B_{\Omega}(2q{l_{e}}))}\right)n^{\frac{(w(V(\alpha))-w(S_{\alpha}))}{2}}\right)<\varepsilon$

######  Corollary 9.18.

For all $\varepsilon>0$, for all $z,l_{max},m\in\mathbb{N}$, taking
$\varepsilon^{\prime\prime}=\frac{\varepsilon}{5^{z}(l_{max}+1)^{z^{k}}}$,
with probability at least $1-\varepsilon$, for all shapes $\alpha$ such that

  1. 1.

$|V(\alpha)|\leq z$.

  2. 2.

All edges in $E(\alpha)$ have label at most $l_{max}$.

  3. 3.

All edges in $E(\alpha)$ have multiplicity at most $m$.

,

$\displaystyle||M_{\alpha}||\leq$ $\displaystyle
2e(2q|V(\alpha)|)^{|V(\alpha)\setminus U_{\alpha}|+|V(\alpha)\setminus
V_{\alpha}|}\left(\prod_{e\in
E(\alpha)}{2h^{+}_{l_{e}}(B_{\Omega}(2ml_{max}))\max_{j\in[0,ml_{max}]}{\left\\{\left(h^{+}_{j}(B_{\Omega}(2qj))\right)^{\frac{l_{e}}{\max{\\{j,l_{e}\\}}}}\right\\}}}\right)$
$\displaystyle n^{\frac{w(V(\alpha))+w(I_{\alpha})-w(S_{\alpha,min})}{2}}$

where
$q=\left\lceil{ln\left(\frac{n^{w(S_{\alpha,max})}}{\varepsilon^{\prime\prime}}\right)}\right\rceil$

###### Proof.

Observe that for each $\alpha$ which has multi-edges, we can write
$M_{\alpha}=\sum_{i}{{c_{i}}M_{\alpha_{i}}}$ where each $\alpha_{i}$ has no
multiple edges. We first upper bound $\sum_{i}{|c_{i}|}$.

######  Lemma 9.19.

For any $a_{1},\ldots,a_{m}\in\mathbb{N}\cup\\{0\\}$, taking
$p_{max}=\sum_{i=1}^{m}{a_{i}}$ and writing
$\prod_{i=1}^{m}{h_{a_{i}}}=\sum_{k=0}^{p_{max}}{{c_{k}}h_{k}}$,

$\sum_{k=0}^{p_{max}}{|c_{k}|}\leq(p_{max}+1)\prod_{i=1}^{m}{h^{+}_{a_{i}}(B_{\Omega}(2p_{max}))}\leq\prod_{i=1}^{m}{2h^{+}_{a_{i}}(B_{\Omega}(2p_{max}))}$

###### Proof.

Suppose $\prod_{i=1}^{m}(h_{a_{i}}(x))^{2}=\sum_{k=0}^{2p_{max}}u_{k}x^{k}$
and $\prod_{i=1}^{m}(h^{+}_{a_{i}}(x))^{2}=\sum_{k=0}^{p_{max}}v_{k}x^{k}$.
Then, note that $|u_{k}|\leq v_{k}$ and so,

$E_{\Omega}[\prod_{i=1}^{m}(h_{a_{i}}(x))^{2}]=\sum_{k=0}^{2p_{max}}u_{k}E_{\Omega}[x^{k}]\leq\sum_{k=0}^{2p_{max}}v_{k}|E_{\Omega}[x^{k}]|\leq\sum_{k=0}^{2p_{max}}v_{k}(B_{\Omega}(2p_{max}))^{k}=\prod_{i=1}^{m}(h_{a_{i}}^{+}(B_{\Omega}(2p_{max}))^{2}$

Therefore, using the fact that $h_{k}$ form an orthonormal basis,

$\sum_{k=0}^{p_{max}}c_{k}^{2}=E_{\Omega}[(\sum_{k=0}^{p_{max}}c_{k}h_{k}(x))^{2}]=E_{\Omega}[\prod_{i=1}^{m}(h_{a_{i}}(x))^{2}]\leq\prod_{i=1}^{m}(h_{a_{i}}^{+}(B_{\Omega}(2p_{max}))^{2}$

This implies

$(\sum_{k=0}^{p_{max}}|c_{k}|)^{2}\leq(p_{max}+1)(\sum_{k=0}^{p_{max}}c_{k}^{2})\leq(p_{max}+1)\prod_{i=1}^{m}(h_{a_{i}}^{+}(B_{\Omega}(2p_{max}))^{2}$

Taking square roots gives the inequality.

######  Corollary 9.20.

For any shape $\alpha$ such that every edge of $\alpha$ has multiplicity at
most $m$ and label at most $l_{max}$, if we write
$M_{\alpha}=\sum_{i}{{c_{i}}M_{\alpha_{i}}}$ where each $\alpha_{i}$ has no
multi-edges then $\sum_{i}{|c_{i}|}\leq\prod_{e\in
E(\alpha)}{2h^{+}_{l_{e}}(B_{\Omega}(2ml_{max}))}$

The result now follows from Theorem 9.17 and the following observations:

  1. 1.

$|V(\alpha)\setminus(U_{\alpha}\cap V_{\alpha})|\leq|V(\alpha)\setminus
U_{\alpha}|+|V(\alpha)\setminus V_{\alpha}|$.

  2. 2.

For any $\alpha$, writing $M_{\alpha}=\sum_{i}{{c_{i}}M_{\alpha_{i}}}$ where
each $\alpha_{i}$ has no multi-edges, for all $\alpha_{i}$,

$w(V(\alpha_{i}))+w(I_{\alpha_{i}})-w(S_{\alpha_{i}})\leq
w(V(\alpha))+w(I_{\alpha})-w(S_{\alpha,min})$

  3. 3.

For any $a_{1},\ldots,a_{m}\in\mathbb{N}\cup\\{0\\}$ such that $\forall
i^{\prime}\in[m],a_{i^{\prime}}\leq l_{max}$, for all $j\in[0,ml_{max}]$

$h^{+}_{j}(B_{\Omega}(2qj))\leq\prod_{i^{\prime}=1}^{m}{\left(h^{+}_{j}(B_{\Omega}(2qj))\right)^{\frac{a_{i^{\prime}}}{\max{\\{j,a_{i^{\prime}}\\}}}}}\leq\prod_{i^{\prime}=1}^{m}{\max_{j^{\prime}\in[0,ml_{max}]}{\left\\{\left(h^{+}_{j^{\prime}}(B_{\Omega}(2qj^{\prime}))\right)^{\frac{a_{i^{\prime}}}{\max{\\{j^{\prime},a_{i^{\prime}}\\}}}}\right\\}}}$

######  Proposition 9.21.

For all $z,l_{max}\in\mathbb{N}$, there are at most $5^{z}(l_{max}+1)^{z^{k}}$
proper shapes $\alpha$ such that $|V(\alpha)|\leq z$ and every edge in
$E(\alpha)$.

###### Proof.

This can be proved in the same way as before. Observe that we can construct
any proper shape $\alpha$ with at most $z$ vertices as follows:

  1. 1.

Start with $z$ vertices $v_{1},\ldots,v_{z}$.

  2. 2.

For each vertex $v_{i}$, choose whether $v_{i}\in V(\alpha)\setminus
U_{\alpha}\setminus V_{\alpha}$, $v_{i}\in U_{\alpha}\setminus V_{\alpha}$,
$v_{i}\in V_{\alpha}\setminus U_{\alpha}$, $v_{i}\in U_{\alpha}\cap
V_{\alpha}$, or $v_{i}\notin V(\alpha)$.

  3. 3.

For each $k$ tuple of vertices in $V(\alpha)$, choose the label of the
hyperedge between these vertices (or $0$ if the hyperedge is not in
$E(\alpha)$).

######  Corollary 9.22.

For all $D_{V},D_{E}\in\mathbb{N}$ and all $\varepsilon>0$, taking

$B_{norm}(\alpha)=2e{B_{vertex}^{|V(\alpha)\setminus
U_{\alpha}|+|V(\alpha)\setminus V_{\alpha}|}}\left(\prod_{e\in
E(\alpha)}{B_{edge}(e)}\right)n^{\frac{w(V(\alpha))+w(I_{\alpha})-w(S_{\alpha})}{2}}$

where

  1. 1.

$q=\left\lceil{ln\left(\frac{n^{3D_{V}}}{\varepsilon^{\prime\prime}}\right)}\right\rceil=\left\lceil{3{D_{V}}ln(n)+ln(\frac{1}{\varepsilon})+{(3D_{V})^{k}}ln(D_{E}+1)+3{D_{V}}ln(5)}\right\rceil$

  2. 2.

$B_{vertex}=6q{D_{V}}$

  3. 3.

$B_{edge}(e)=2h^{+}_{l_{e}}(B_{\Omega}(6{D_{V}}D_{E}))\max_{j\in[0,3{D_{V}}D_{E}]}{\left\\{\left(h^{+}_{j}(B_{\Omega}(2qj))\right)^{\frac{l_{e}}{\max{\\{j,l_{e}\\}}}}\right\\}}$

with probability at least $(1-\varepsilon)$, for all shapes
$\alpha\in\mathcal{M}^{\prime}$, $||M_{\alpha}||\leq B_{norm}(\alpha)$.

###  9.3 Choosing $B(\gamma)$

We now describe how to choose the function $B(\gamma)$. Recall that we want
the following conditions to hold:

  1. 1.

For all $\gamma,\tau,\gamma^{\prime}$ and all intersection patterns
$P\in\mathcal{P}_{\gamma,\tau,\gamma^{\prime}}$,

$B_{norm}(\tau_{P})\leq B(\gamma)B(\gamma^{\prime})B_{norm}(\tau)$

  2. 2.

For all composable $\gamma_{1},\gamma_{2}$,
$B(\gamma_{1})B(\gamma_{2})=B(\gamma_{1}\circ\gamma_{2})$.

The most important part of choosing $B(\gamma)$ is to make sure that the
factors of $n$ are controlled. For this, we use the following intersection
tradeoff lemma. Under our simplifying assumptions, this lemma follows from
[BHK+16, Lemma 7.12]. We defer the general proof of this lemma to the end of
this section.

######  Lemma 9.23 (Intersection Tradeoff Lemma).

For all $\gamma,\tau,\gamma^{\prime}$ and all intersection patterns
$P\in\mathcal{P}_{\gamma,\tau,\gamma^{\prime}}$,

$w(V(\tau_{P}))+w(I_{\tau_{P}})-w(S_{\tau_{P},min})\leq
w(V(\tau))+w(I_{\tau})-w(S_{\tau,min})+w(V(\gamma)\setminus
U_{\gamma})+w(V(\gamma^{\prime})\setminus U_{\gamma^{\prime}})$

Based on this intersection tradeoff lemma, we can choose the function
$B(\gamma)$ as follows.

######  Corollary 9.24.

If we take

$B_{norm}(\alpha)=C\cdot B_{vertex}^{|V(\alpha)\setminus
U_{\alpha}|+|V(\alpha)\setminus V_{\alpha}|}\left(\prod_{e\in
E(\alpha)}{B_{edge}(e)}\right)n^{\frac{w(V(\alpha))+w(I_{\alpha})-w(S_{\alpha})}{2}}$

for some constant $C>0$ and take

$B(\gamma)=B_{vertex}^{|V(\gamma)\setminus U_{\gamma}|+|V(\gamma)\setminus
V_{\gamma}|}\left(\prod_{e\in
E(\gamma)}{B_{edge}(e)}\right)n^{\frac{w(V(\gamma)\setminus U_{\gamma})}{2}}$

then the following conditions hold:

  1. 1.

For all $\gamma,\tau,\gamma^{\prime}$ and all intersection patterns
$P\in\mathcal{P}_{\gamma,\tau,\gamma^{\prime}}$,

$B_{norm}(\tau_{P})\leq B(\gamma)B(\gamma^{\prime})B_{norm}(\tau)$

  2. 2.

For all composable $\gamma_{1},\gamma_{2}$,
$B(\gamma_{1})B(\gamma_{2})=B(\gamma_{1}\circ\gamma_{2})$.

###### Proof.

We have that

$B_{norm}(\tau_{P})=B_{vertex}^{|V(\tau_{P})\setminus
U_{\tau_{P}}|+|V(\tau_{P})\setminus V_{\tau_{P}}|}\left(\prod_{e\in
E(\tau_{P})}{B_{edge}(e)}\right)n^{\frac{w(V(\tau_{P}))+w(I_{\tau_{P}})-w(S_{\tau_{P}})}{2}}$

and

$\displaystyle B(\gamma)B(\gamma^{\prime})B_{norm}(\tau)$
$\displaystyle=B_{vertex}^{|V(\gamma)\setminus U_{\gamma}|+|V(\gamma)\setminus
V_{\gamma}|+|V(\gamma^{\prime})\setminus
U_{\gamma^{\prime}}|+|V(\gamma^{\prime})\setminus
V_{\gamma^{\prime}}|+|V(\tau)\setminus U_{\tau}|+|V(\tau)\setminus V_{\tau}|}$
$\displaystyle\left(\prod_{e\in E(\gamma)\cup E(\gamma^{\prime})\cup
E(\tau)}{B_{edge}(e)}\right)n^{\frac{w(V(\gamma)\setminus
U_{\gamma})+w(V(\gamma^{\prime})\setminus
U_{\gamma^{\prime}})+w(V(\tau))+w(I_{\tau})-w(S_{\tau})}{2}}$

The first condition now follows immediately from the following observations:

  1. 1.

$\displaystyle|V(\gamma)\setminus U_{\gamma}|+|V(\gamma)\setminus
V_{\gamma}|+|V(\gamma^{\prime})\setminus
U_{\gamma^{\prime}}|+|V(\gamma^{\prime})\setminus
V_{\gamma^{\prime}}|+|V(\tau)\setminus U_{\tau}|+|V(\tau)\setminus V_{\tau}|$
$\displaystyle=|V(\gamma\circ\tau\circ{\gamma^{\prime}}^{T})\setminus
U_{\gamma\circ\tau\circ{\gamma^{\prime}}^{T}}|+|V(\gamma\circ\tau\circ{\gamma^{\prime}}^{T})\setminus
V_{\gamma\circ\tau\circ{\gamma^{\prime}}^{T}}|\geq|V(\tau_{P})\setminus
U_{\tau_{P}}|+|V(\tau_{P})\setminus V_{\tau_{P}}|$

  2. 2.

$E(\tau_{P})=E(\gamma)\cup E(\tau)\cup E({\gamma^{\prime}}^{T})$ so
$\prod_{e\in E(\tau_{P})}{B_{edge}(e)}=\prod_{e\in E(\gamma)\cup
E(\gamma^{\prime})\cup E(\tau)}{B_{edge}(e)}$.

  3. 3.

By the intersection tradeoff lemma,

$w(V(\tau_{P}))+w(I_{\tau_{P}})-w(S_{\tau_{P}})\leq
w(V(\tau))+w(I_{\tau})-w(S_{\tau})+w(V(\gamma)\setminus
U_{\gamma})+w(V(\gamma^{\prime})\setminus U_{\gamma^{\prime}})$

The second condition follows from the form of $B(\gamma)$.

###  9.4 Choosing $N(\gamma)$

To choose $N(\gamma)$, we use the following lemma:

######  Lemma 9.25.

For all $D_{V}\in\mathbb{N}$, for all composable
$\gamma,\tau,{\gamma^{\prime}}^{T}$ such that $|V(\gamma)|\leq D_{V}$,
$|V(\tau)|\leq D_{V}$, and $|V(\gamma^{\prime})|\leq D_{V}$,

$\displaystyle\sum_{j>0}{\sum_{\gamma_{1},\gamma^{\prime}_{1},\cdots,\gamma_{j},\gamma^{\prime}_{j}\in\Gamma_{\gamma,\gamma^{\prime},j}}{\prod_{i:\gamma_{i}\text{
is non-
trivial}}{\frac{1}{|Aut(U_{\gamma_{i}})|}}\prod_{i:\gamma^{\prime}_{i}\text{
is non-
trivial}}{\frac{1}{|Aut(U_{\gamma^{\prime}_{i}})|}}}}\sum_{P_{1},\cdots,P_{j}:P_{i}\in\mathcal{P}_{\gamma_{i},\tau_{P_{i-1}},{\gamma^{\prime}_{i}}^{T}}}{\left(\prod_{i=1}^{j}{N(P_{i})}\right)}$
$\displaystyle\leq\frac{{(3D_{V})}^{2(|V(\gamma)\setminus
V_{\gamma}|+|V(\gamma^{\prime})\setminus
V_{\gamma^{\prime}}|)+(|V(\gamma)\setminus
U_{\gamma}|+|V(\gamma^{\prime})\setminus
U_{\gamma^{\prime}}|)}}{(|Aut(U_{\gamma})|)^{1_{\gamma\text{ is non-
trivial}}}(|Aut(U_{\gamma^{\prime}})|)^{1_{\gamma^{\prime}\text{ is non-
trivial}}}}$

###### Proof sketch.

Observe that aside from the orderings (which are canceled out by the
$|Aut(U_{\gamma_{i}})|$ and $|Aut(U_{\gamma^{\prime}_{i}})|$ factors), the
intersection patterns $\\{P_{i}:i\in[j]\\}$ are determined by the following
data on each vertex $v\in(V(\gamma)\setminus
V_{\gamma})\cup(V({\gamma^{\prime}}^{T})\setminus V_{{\gamma^{\prime}}^{T}})$:

  1. 1.

The first $i\in[j]$ such that $v\in(V(\gamma_{i})\setminus
V_{\gamma_{i}})\cup(V({\gamma^{\prime}_{i}}^{T})\setminus
V_{{\gamma^{\prime}_{i}}^{T}})$. There are at most $j$ possibilities for this.

  2. 2.

A vertex $u$ (if one exists) in
$V(\gamma_{i-1}\circ\ldots\circ\gamma_{1}\circ\tau\circ{\gamma^{\prime}_{1}}^{T}\ldots\circ{\gamma^{\prime}_{i-1}}^{T})$
such that $u$ and $v$ are equal. There are at most $3D_{V}$ possibilities for
this.

Using these observations and taking $j_{max}=|V(\gamma)\setminus
V_{\gamma}|+|V(\gamma^{\prime})\setminus V_{\gamma^{\prime}}|$,

$\displaystyle\sum_{j>0}{\sum_{\gamma_{1},\gamma^{\prime}_{1},\cdots,\gamma_{j},\gamma^{\prime}_{j}\in\Gamma_{\gamma,\gamma^{\prime},j}}{\prod_{i:\gamma_{i}\text{
is non-
trivial}}{\frac{1}{|Aut(U_{\gamma_{i}})|}}\prod_{i:\gamma^{\prime}_{i}\text{
is non-
trivial}}{\frac{1}{|Aut(U_{\gamma^{\prime}_{i}})|}}}}\sum_{P_{1},\cdots,P_{j}:P_{i}\in\mathcal{P}_{\gamma_{i},\tau_{P_{i-1}},{\gamma^{\prime}_{i}}^{T}}}{1}$
$\displaystyle\leq\sum_{j=1}^{j_{max}}{\frac{{(3jD_{V})}^{|V(\gamma)\setminus
V_{\gamma}|+|V(\gamma^{\prime})\setminus
V_{\gamma^{\prime}}|}}{(|Aut(U_{\gamma})|)^{1_{\gamma\text{ is non-
trivial}}}(|Aut(U_{\gamma^{\prime}})|)^{1_{\gamma^{\prime}\text{ is non-
trivial}}}}}$ $\displaystyle\leq
j_{max}\left(\frac{2}{3}\right)^{j_{max}}\frac{{(3D_{V})}^{2(|V(\gamma)\setminus
V_{\gamma}|+|V(\gamma^{\prime})\setminus
V_{\gamma^{\prime}}|)}}{(|Aut(U_{\gamma})|)^{1_{\gamma\text{ is non-
trivial}}}(|Aut(U_{\gamma^{\prime}})|)^{1_{\gamma^{\prime}\text{ is non-
trivial}}}}$ $\displaystyle<\frac{{(3D_{V})}^{2(|V(\gamma)\setminus
V_{\gamma}|+|V(\gamma^{\prime})\setminus
V_{\gamma^{\prime}}|)}}{(|Aut(U_{\gamma})|)^{1_{\gamma\text{ is non-
trivial}}}(|Aut(U_{\gamma^{\prime}})|)^{1_{\gamma^{\prime}\text{ is non-
trivial}}}}$

Now recall that by Lemma , for any
$\gamma_{i},\tau_{P_{i-1}},{\gamma^{\prime}_{i}}^{T}$ and any intersection
pattern
$P_{i}\in\mathcal{P}_{\gamma_{i},\tau_{P_{i-1}},{\gamma^{\prime}_{i}}^{T}}$,

$N(P_{i})\leq|V(\tau_{P_{i}})|^{|V(\gamma_{i})\setminus
U_{\gamma_{i}}|+|V(\gamma^{\prime}_{i})\setminus U_{\gamma^{\prime}_{i}}|}$

Thus, for any
$P_{1},\cdots,P_{j}:P_{i}\in\mathcal{P}_{\gamma_{i},\tau_{P_{i-1}},{\gamma^{\prime}_{i}}^{T}}$,
$\prod_{i=1}^{j}{N(P_{i})}\leq(3D_{V})^{|V(\gamma)\setminus
U_{\gamma}|+|V(\gamma^{\prime})\setminus U_{\gamma^{\prime}}|}$. Putting
everything together, the result follows.

######  Corollary 9.26.

For all $D_{V}\in\mathbb{N}$, if we take
$N(\gamma)=(3D_{V})^{2|V(\gamma)\setminus V_{\gamma}|+|V(\gamma)\setminus
U_{\gamma}|}$ then for all composable $\gamma,\tau,{\gamma^{\prime}}^{T}$ such
that $|V(\gamma)|\leq D_{V}$, $|V(\tau)|\leq D_{V}$, and
$|V(\gamma^{\prime})|\leq D_{V}$,

$\displaystyle\sum_{j>0}{\sum_{\gamma_{1},\gamma^{\prime}_{1},\cdots,\gamma_{j},\gamma^{\prime}_{j}\in\Gamma_{\gamma,\gamma^{\prime},j}}{\prod_{i:\gamma_{i}\text{
is non-
trivial}}{\frac{1}{|Aut(U_{\gamma_{i}})|}}\prod_{i:\gamma^{\prime}_{i}\text{
is non-
trivial}}{\frac{1}{|Aut(U_{\gamma^{\prime}_{i}})|}}}}\sum_{P_{1},\cdots,P_{j}:P_{i}\in\mathcal{P}_{\gamma_{i},\tau_{P_{i-1}},{\gamma^{\prime}_{i}}^{T}}}{\left(\prod_{i=1}^{j}{N(P_{i})}\right)}$
$\displaystyle\leq\frac{N(\gamma)N(\gamma^{\prime})}{(|Aut(U_{\gamma})|)^{1_{\gamma\text{
is non-trivial}}}(|Aut(U_{\gamma^{\prime}})|)^{1_{\gamma^{\prime}\text{ is
non-trivial}}}}$

###  9.5 Choosing $c(\alpha)$

In this section, we describe how to choose $c(\alpha)$. For simplicity, we
first describe how to choose $c(\alpha)$ under our simplifying assumptions. We
then describe the minor adjustments that are needed when we have hyperedges
and multiple types of vertices.

######  Lemma 9.27.

Under our simplifying assumptons, for all $U\in\mathcal{I}_{mid}$,

$\sum_{\alpha:U_{\alpha}\equiv U,\alpha\text{ is proper and non-
trivial}}{\frac{1}{|Aut(U_{\alpha}\cap
V_{\alpha})|(3D_{V})^{|U_{\alpha}\setminus V_{\alpha}|+|V_{\alpha}\setminus
U_{\alpha}|+2|E(\alpha)|}2^{|V(\alpha)\setminus(U_{\alpha}\cup
V_{\alpha})|}}}<5$

###### Proof.

In order to choose $\alpha$, it is sufficient to choose the following:

  1. 1.

The number $j_{1}$ of vertices in $U_{\alpha}\setminus V_{\alpha}$, the number
$j_{2}$ of vertices in $V_{\alpha}\setminus U_{\alpha}$, and the number
$j_{3}$ of vertices in $V(\alpha)\setminus(U_{\alpha}\cup V_{\alpha})$.

  2. 2.

A mapping in $Aut(U_{\alpha}\cap V_{\alpha})$ determining how the vertices in
$U_{\alpha}\cap V_{\alpha}$ match up with each other.

  3. 3.

The position of each vertex $u\in U_{\alpha}\setminus V_{\alpha}$ within
$U_{\alpha}$ (there are at most $|U_{\alpha}|\leq D_{V}$ choices for this).

  4. 4.

The position of each vertex $v\in V_{\alpha}\setminus U_{\alpha}$ within
$V_{\alpha}$ (there are at most $|U_{\alpha}|\leq D_{V}$ choices for this).

  5. 5.

The number $j_{4}$ of edges in $E(\alpha)$.

  6. 6.

The endpoints of each edge in $E(\alpha)$.

This implies that for all $j_{1},j_{2},j_{3},j_{4}\geq 0$

$\sum_{\alpha:U_{\alpha}\equiv U,|U_{\alpha}\setminus
V_{\alpha}|=j_{1},|V_{\alpha}\setminus
U_{\alpha}|=j_{2}\atop|V(\alpha)\setminus(U_{\alpha}\cup
V_{\alpha})|=j_{3},|E(\alpha)|=j_{4}}{\frac{1}{|Aut(U_{\alpha}\cap
V_{\alpha})|(D_{V})^{j_{1}+j_{2}}(D_{V})^{2j_{4}}}}\leq 1$

Using this, we have that

$\displaystyle\sum_{\alpha:U_{\alpha}\equiv U,\alpha\text{ is proper and non-
trivial}}{\frac{1}{|Aut(U_{\alpha}\cap
V_{\alpha})|(3D_{V})^{|U_{\alpha}\setminus V_{\alpha}|+|V_{\alpha}\setminus
U_{\alpha}|+2|E(\alpha)|}2^{|V(\alpha)\setminus(U_{\alpha}\cup
V_{\alpha})|}}}$
$\displaystyle\leq\sum_{j_{1},j_{2},j_{3},j_{4}\in\mathbb{N}\cup\\{0\\}:j_{1}+j_{2}+j_{3}+j_{4}\geq
1}{\frac{1}{3^{j_{1}+j_{2}}9^{j_{4}}2^{j_{3}}}}\leq
2\left(\frac{3}{2}\right)^{2}\frac{9}{8}-1<5$

######  Corollary 9.28.

For all $\varepsilon^{\prime}>0$, if we take

$c(\alpha)=\frac{5(3D_{V})^{|U_{\alpha}\setminus
V_{\alpha}|+|V_{\alpha}\setminus
U_{\alpha}|+2|E(\alpha)|}2^{|V(\alpha)\setminus(U_{\alpha}\cup
V_{\alpha})|}}{\varepsilon^{\prime}}$

then

  1. 1.

$\forall
U\in\mathcal{I}_{mid},\sum_{\gamma\in\Gamma_{U,*}}{\frac{1}{|Aut(U)|c(\gamma)}}<\varepsilon^{\prime}$

  2. 2.

$\forall
V\in\mathcal{I}_{mid},\sum_{\gamma\in\Gamma_{*,V}}{\frac{1}{|Aut(U_{\gamma})|c(\gamma)}}<\varepsilon^{\prime}$

  3. 3.

$\forall
U\in\mathcal{I}_{mid},\sum_{\tau\in\mathcal{M}_{U}}{\frac{1}{|Aut(U)|c(\tau)}}<\varepsilon^{\prime}$

####  9.5.1 Choosing $c(\alpha)$ in general*

When we have multiple types of vertices and hyperedges of arity $k$, Lemma
9.27 can be generalized as follows:

######  Lemma 9.29.

Under our simplifying assumptons, for all $U\in\mathcal{I}_{mid}$,

$\sum_{\alpha:U_{\alpha}\equiv U,\alpha\text{ is proper and non-
trivial}}{\frac{1}{|Aut(U_{\alpha}\cap
V_{\alpha})|(3D_{V}{t_{max}})^{|U_{\alpha}\setminus
V_{\alpha}|+|V_{\alpha}\setminus
U_{\alpha}|+k|E(\alpha)|}(2t_{max})^{|V(\alpha)\setminus(U_{\alpha}\cup
V_{\alpha})|}}}<5$

###### Proof sketch.

This can be proved in the same way as Lemma 9.27 with the following
modifications:

  1. 1.

In addition to choosing the number of vertices in $U_{\alpha}\setminus
V_{\alpha}$, $V_{\alpha}\setminus U_{\alpha}$, and
$V(\alpha)\setminus(U_{\alpha}\cap V_{\alpha})$, we also have to choose the
types of these vertices.

  2. 2.

For each hyperedge, we have to choose $k$ endpoints rather than $2$ endpoints.

######  Corollary 9.30.

For all $\varepsilon^{\prime}>0$, if we take

$c(\alpha)=\frac{5(3{t_{max}}D_{V})^{|U_{\alpha}\setminus
V_{\alpha}|+|V_{\alpha}\setminus
U_{\alpha}|+k|E(\alpha)|}(2t_{max})^{|V(\alpha)\setminus(U_{\alpha}\cup
V_{\alpha})|}}{\varepsilon^{\prime}}$

then

  1. 1.

$\forall
U\in\mathcal{I}_{mid},\sum_{\gamma\in\Gamma_{U,*}}{\frac{1}{|Aut(U)|c(\gamma)}}<\varepsilon^{\prime}$

  2. 2.

$\forall
V\in\mathcal{I}_{mid},\sum_{\gamma\in\Gamma_{*,V}}{\frac{1}{|Aut(U_{\gamma})|c(\gamma)}}<\varepsilon^{\prime}$

  3. 3.

$\forall
U\in\mathcal{I}_{mid},\sum_{\tau\in\mathcal{M}_{U}}{\frac{1}{|Aut(U)|c(\tau)}}<\varepsilon^{\prime}$

For technical reasons, we will need a more refined bound when the sum is over
all shapes $\gamma$ of at least a prescribed size.

######  Lemma 9.31.

For all $\varepsilon^{\prime}>0$, for the same choice of $c(\alpha)$ as in
Corollary 9.30, for any $U\in{\mathcal{I}}_{mid}$ and integer $m\geq 1$, we
have

$\sum_{\gamma\in\Gamma_{U,*}:|V(\gamma)|\geq|U|+m}\frac{1}{|Aut(U)|c(\gamma)}\leq\frac{\varepsilon^{\prime}}{5\cdot
2^{m-1}}$

###### Proof sketch.

The proof is similar to the proof of Corollary 9.30, but we now have the extra
condition $j_{2}+j_{3}\geq m$ in the proof of Lemma 9.27. Then,

$\sum_{j_{1},j_{2},j_{3},j_{4}\in\mathbb{N}\cup\\{0\\}:j_{2}+j_{3}\geq
m}\frac{1}{3^{j_{1}+j_{2}}9^{j_{4}}2^{j_{3}}}\leq\sum_{j_{1},j_{4}\in\mathbb{N}\cup\\{0\\}}\frac{1}{2^{m}3^{j_{1}}9^{j_{4}}}=\frac{27}{16\cdot
2^{m}}\leq\frac{1}{2^{m-1}}$

###  9.6 Proof of the Generalized Intersection Tradeoff Lemma

We now prove the generalized intersection tradeoff lemma.

######  Lemma 9.32.

For all $\gamma,\tau,\gamma^{\prime}$ and all intersection patterns
$P\in\mathcal{P}_{\gamma,\tau,\gamma^{\prime}}$,

$w(V(\tau_{P}))+w(I_{\tau_{P}})-w(S_{\tau_{P},min})\leq
w(V(\tau))+w(I_{\tau})-w(S_{\tau,min})+w(V(\gamma)\setminus
U_{\gamma})+w(V(\gamma^{\prime})\setminus U_{\gamma^{\prime}})$

###### Proof.

######  Definition 9.33.

  1. 1.

We define $I_{LM}$ to be the set of vertices which, after intersections, touch
$\gamma$ and $\tau$ but not ${\gamma^{\prime}}^{T}$. In particular, $I_{LM}$
consists of the vertices which result from intersecting a pair of vertices in
$V(\gamma)\setminus V_{\gamma}$ and $V(\tau)\setminus U_{\tau}\setminus
V_{\tau}$ and the vertices which are in $U_{\tau}\setminus V_{\tau}$ and are
not intersected with any other vertex.

  2. 2.

We define $I_{MR}$ to be the set of vertices which, after intersections, touch
$\tau$ and ${\gamma^{\prime}}^{T}$ but not $\gamma$. In particular, $I_{MR}$
consists of the vertices which result from intersecting a pair of vertices in
$V(\tau)\setminus U_{\tau}\setminus V_{\tau}$ and
$V({\gamma^{\prime}}^{T})\setminus U_{{\gamma^{\prime}}^{T}}$ and the vertices
which are in $V_{\tau}\setminus U_{\tau}$ and are not intersected with any
other vertex.

  3. 3.

We define $I_{LR}$ to be the set of vertices which, after intersections, touch
$\gamma$ and ${\gamma^{\prime}}^{T}$ but not $\tau$. In particular, $I_{LR}$
consists of the vertices which result from intersecting a pair of vertices in
$V(\gamma)\setminus V_{\gamma}$ and $V({\gamma^{\prime}}^{T})\setminus
U_{{\gamma^{\prime}}^{T}}$.

  4. 4.

We define $I_{LMR}$ to be the set of vertices which, after intersections,
touch $\gamma$, $\tau$, and ${\gamma^{\prime}}^{T}$. In particular, $I_{LMR}$
consists of the vertices which result from intersecting a triple of vertices
in $V(\gamma)\setminus V_{\gamma}$, $V(\tau)\setminus U_{\tau}\setminus
V_{\tau}$, and $V({\gamma^{\prime}}^{T})\setminus U_{{\gamma^{\prime}}^{T}}$,
intersecting a pair of vertices in $V(\gamma)\setminus V_{\gamma}$ and
$V_{\tau}\setminus U_{\tau}$, intersecting a pair of vertices in
$U_{\tau}\setminus V_{\tau}$ and $V({\gamma^{\prime}}^{T})\setminus
U_{{\gamma^{\prime}}^{T}}$, and single vertices in $U_{\tau}\cap V_{\tau}$.

The main idea is as follows. A priori, any of the vertices in $I_{LM}\cup
I_{MR}\cup I_{LR}\cup I_{LMR}$ could become isolated. We handle this by
keeping track of the following types of flows:

  1. 1.

Flows from $U_{\gamma}$ to $I_{LM}\cup I_{LR}\cup I_{LMR}$

  2. 2.

Flows from $I_{LR}\cup I_{MR}\cup I_{LMR}$ to $V_{{\gamma^{\prime}}^{T}}$

  3. 3.

Flows from $I_{LM}$ to $I_{MR}$. For technical reasons, we also view vertices
in $I_{LMR}$ as having flow to themselves.

We then observe that flows to and from these vertices prevent these vertices
from being isolated and can provide flow from $U_{\gamma}$ to
$V_{{\gamma^{\prime}}^{T}}$, which gives a lower bound on $w(S_{\tau_{P}})$.

We now implement this idea.

######  Definition 9.34 (Flow Graph).

Given a shape $\alpha$, we define the directed graph $H_{\alpha}$ as follows:

  1. 1.

For each vertex $v\in V(\alpha)$, we create two vertices $v_{in}$ and
$v_{out}$. We then create a directed edge from $v_{in}$ to $v_{out}$ with
capacity $w(v)$

  2. 2.

For each pair of vertices $(v,w)$ which is an edge of multiplicity $1$ in
$E(\alpha)$ (or part of a hyperedge of multiplicity $1$ in $E(\alpha)$), we
create a directed edge with infinite capacity from $v_{out}$ to $w_{in}$ and
we create a directed edge with infinite capacity from $w_{out}$ to $v_{in}$.

  3. 3.

We define $U_{H_{\alpha}}$ to be $U_{H_{\alpha}}=\\{u_{in}:u\in U_{\alpha}\\}$
and we define $V_{H_{\alpha}}$ to be $V_{H_{\alpha}}=\\{v_{out}:v\in
V_{\alpha}\\}$

######  Lemma 9.35.

The maximum flow from $U_{H_{\alpha}}$ to $V_{H_{\alpha}}$ is equal to the
minimum weight of a separator between $U_{\alpha}$ and $V_{\alpha}$.

###### Proof.

This can be proved using the max flow min cut theorem.

######  Definition 9.36 (Modified Flow Graph).

Given a shape $\alpha$ together with a set $I_{L}\subseteq V(\alpha)$ of
vertices in $\alpha$ (which will be the vertices in $\alpha$ which are
intersected with a vertex to the left of $\alpha$) and a set $I_{R}\subseteq
V(\alpha)$ of vertices in $\alpha$ (which will be the vertices in $\alpha$
which are intersected with a vertex to the right of $\alpha$), we define the
modified flow graph $H^{I_{L},I_{R}}_{\alpha}$ as follows:

  1. 1.

We start with the flow graph $H_{\alpha}$

  2. 2.

For each vertex $u\in I_{L}$, we delete all of the edges into $u_{in}$ and add
$u_{in}$ to $U_{H_{\alpha}}$

  3. 3.

For each vertex $v\in I_{R}$, we delete all of the edges out of $v_{out}$ and
add $v_{out}$ to $V_{H_{\alpha}}$

  4. 4.

We call the resulting graph $H^{I_{L},I_{R}}_{\alpha}$ and the resulting sets
$U_{H^{I_{L},I_{R}}_{\alpha}}$ and $V_{H^{I_{L},I_{R}}_{\alpha}}$

######  Lemma 9.37.

The maximum flow from $U_{H^{I_{L},I_{R}}_{\alpha}}$ to
$V_{H^{I_{L},I_{R}}_{\alpha}}$ in $H^{I_{L},I_{R}}_{\alpha}$ is at least as
large as the maximum flow from $U_{H_{\alpha}}$ to $V_{H_{\alpha}}$ in
$H_{\alpha}$

###### Proof sketch.

Observe that if we have a cut $C$ in $H^{I_{L},I_{R}}_{\alpha}$ which
separates $U_{H^{I_{L},I_{R}}_{\alpha}}$ and $V_{H^{I_{L},I_{R}}_{\alpha}}$
then $C$ separates $U_{H_{\alpha}}$ and $V_{H_{\alpha}}$ in $H_{\alpha}$

Before the intersections, we have the following flows.

  1. 1.

We take $F_{1}$ to be the maximum flow from $U_{\gamma}$ to $V_{\gamma}$ in
$\gamma$. Note that $F_{1}$ has value $w(V_{\gamma})$

  2. 2.

We take $F_{2}$ to be the maximum flow from $U_{\tau}$ to $V_{\tau}$ in
$\tau$. Note that $F_{2}$ has value $w(S_{\tau,min})$

  3. 3.

We take $F_{3}$ to be the maximum flow from $U_{{\gamma^{\prime}}^{T}}$ to
$V_{{\gamma^{\prime}}^{T}}$ in ${\gamma^{\prime}}^{T}$. Note that $F_{1}$ has
value $w(U_{{\gamma^{\prime}}^{T}})$

After the intersections, we take the following flows:

  1. 1.

We take $F^{\prime}_{1}$ to be the maximum flow from
$U_{H^{\emptyset,I_{LM}\cup I_{LR}\cup I_{LMR}}_{\gamma}}$ to
$V_{H^{\emptyset,I_{LM}\cup I_{LR}\cup I_{LMR}}_{\gamma}}$ in
$H^{\emptyset,I_{LM}\cup I_{LR}\cup I_{LMR}}_{\gamma}$.

  2. 2.

We take $F^{\prime}_{2}$ to be the maximum flow from $U_{H^{I_{LM}\cup
I_{LMR},I_{MR}\cup I_{LMR}}_{\tau}}$ to $V_{H^{I_{LM}\cup I_{LMR},I_{MR}\cup
I_{LMR}}_{\tau}}$ in
$H^{I_{LM}\cup I_{LMR},I_{MR}\cup I_{LMR}}_{\tau}$

  3. 3.

We take $F^{\prime}_{3}$ to be the maximum flow from $U_{H^{I_{MR}\cup
I_{LR}\cup I_{LMR},\emptyset}_{{\gamma^{\prime}}^{T}}}$ to $V_{H^{I_{MR}\cup
I_{LR}\cup I_{LMR},\emptyset}_{{\gamma^{\prime}}^{T}}}$ in
$H^{I_{MR}\cup I_{LR}\cup I_{LMR},\emptyset}_{{\gamma^{\prime}}^{T}}$.

Observe that because of how intersection patterns are defined,
$val(F^{\prime}_{1})=w(U_{\gamma})$ and
$val(F^{\prime}_{3})=w(V_{{\gamma^{\prime}}^{T}})$. By Lemma 9.37, the value
of $F^{\prime}_{2}$ is at least as large as the value of $F_{2}$, so
$val(F^{\prime}_{2})\geq w(S_{\tau,min})$.

We now consider $F^{\prime}_{1}+F^{\prime}_{2}+F^{\prime}_{3}$. As is, this is
not a flow, but we can fix this.

######  Definition 9.38.

For each vertex $v\in V(\tau_{P})$,

  1. 1.

We define $f_{in}(v)$ to be the flow into $v_{in}$ in
$F^{\prime}_{1}+F^{\prime}_{2}+F^{\prime}_{3}$.

  2. 2.

We define $f_{out}(v)$ to be the flow out of $v_{out}$ in
$F^{\prime}_{1}+F^{\prime}_{2}+F^{\prime}_{3}$.

  3. 3.

We define $f_{through}(v)$ to be the flow from $v_{in}$ to $v_{out}$ in
$F^{\prime}_{1}+F^{\prime}_{2}+F^{\prime}_{3}$

  4. 4.

We define $f_{imbalance}(v)$ to be $f_{imbalance}(v)=|f_{in}(v)-f_{out}(v)|$

  5. 5.

We define $f_{excess}(v)$ to be
$f_{excess}(v)=f_{through}(v)-max{\\{f_{in}(v),f_{out}(v)\\}}$

With this information, we fix the flow
$F^{\prime}_{1}+F^{\prime}_{2}+F^{\prime}_{3}$ as follows. For each vertex
$v\in V(\tau_{P})$,

  1. 1.

If $f_{in}(v)>f_{out}(v)$ then we create a vertex $v_{supplemental,out}$ and
an edge from $v_{out}$ to $v_{supplemental,out}$ with capacity
$f_{imbalance}(v)$ and we route $f_{imbalance}(v)$ of flow along this edge. We
then add $v_{supplemental,out}$ to a set of vertices $V_{supplemental}$.

  2. 2.

If $f_{in}(v)<f_{out}(v)$ then we create a vertex $v_{supplemental,in}$ and an
edge from $v_{supplemental,in}$ to $v_{in}$ with capacity $f_{imbalance}(v)$
and we route $f_{imbalance}(v)$ of flow along this edge. We then add
$v_{supplemental,out}$ to a set of vertices $V_{supplemental}$.

  3. 3.

We reduce the flow on the edge from $v_{in}$ to $v_{out}$ by $f_{excess}(v)$

We call the resulting flow $F^{\prime}$

######  Proposition 9.39.

$F^{\prime}$ is a flow from $U_{H^{\emptyset,I_{LM}\cup I_{LR}\cup
I_{LMR}}_{\gamma}}\cup U_{supplemental}$ to $V_{H^{I_{MR}\cup I_{LR}\cup
I_{LMR},\emptyset}_{{\gamma^{\prime}}^{T}}}\cup V_{supplemental}$ with value
$val(F^{\prime})=val(F^{\prime}_{1})+val(F^{\prime}_{2})+val(F^{\prime}_{3})-\sum_{v\in
V(\tau)}{f_{excess}(v)}$

######  Corollary 9.40.

There exists a flow $F^{\prime\prime}$ from $U_{H^{\emptyset,I_{LM}\cup
I_{LR}\cup I_{LMR}}_{\gamma}}$ to $V_{H^{I_{MR}\cup I_{LR}\cup
I_{LMR},\emptyset}_{{\gamma^{\prime}}^{T}}}$ with value
$val(F^{\prime\prime})\geq
val(F^{\prime}_{1})+val(F^{\prime}_{2})+val(F^{\prime}_{3})-\sum_{v\in
V(\tau)}{(f_{excess}(v)+f_{imbalance}(v))}$

###### Proof.

Consider the minimum cut $C$ between $U_{H^{\emptyset,I_{LM}\cup I_{LR}\cup
I_{LMR}}_{\gamma}}$ and $V_{H^{I_{MR}\cup I_{LR}\cup
I_{LMR},\emptyset}_{{\gamma^{\prime}}^{T}}}$. If we add all of the
supplemental edges to $C$ then this gives a cut $C^{\prime}$ between
$U_{H^{\emptyset,I_{LM}\cup I_{LR}\cup I_{LMR}}_{\gamma}}$ and
$V_{H^{I_{MR}\cup I_{LR}\cup I_{LMR},\emptyset}_{{\gamma^{\prime}}^{T}}}$ with
capacity

$capacity(C^{\prime})=capacity(C)+\sum_{v\in V(\tau)}{f_{imbalance}(v)}\geq
val(F^{\prime})$

Thus, $capacity(C)\geq val(F^{\prime})-\sum_{v\in V(\tau)}{f_{imbalance}(v)}$
so there exists a flow $F^{\prime\prime}$ from $U_{H^{\emptyset,I_{LM}\cup
I_{LR}\cup I_{LMR}}_{\gamma}}$ to $V_{H^{I_{MR}\cup I_{LR}\cup
I_{LMR},\emptyset}_{{\gamma^{\prime}}^{T}}}$ with value

$val(F^{\prime\prime})=capacity(C)\geq
val(F^{\prime}_{1})+val(F^{\prime}_{2})+val(F^{\prime}_{3})-\sum_{v\in
V(\tau)}{(f_{excess}(v)+f_{imbalance}(v))}$

We now make the following observations:

######  Lemma 9.41.

  1. 1.

For all vertices $v\notin I_{LM}\cup I_{MR}\cup I_{LR}\cup I_{LMR}$,
$f_{excess}(v)=f_{imbalance}(v)=0$ (and these vertices can never be isolated).

  2. 2.

For all vertices $v\in I_{LM}$, $f_{excess}(v)+f_{imbalance}(v)\leq w(v)$.
Moreover, for all vertices $v\in I_{LM}$ which are isolated,
$f_{excess}(v)=f_{imbalance}(v)=0$.

  3. 3.

For all vertices $v\in I_{MR}$, $f_{excess}(v)+f_{imbalance}(v)\leq w(v)$.
Moreover, for all vertices $v\in I_{LM}$ which are isolated,
$f_{excess}(v)=f_{imbalance}(v)=0$.

  4. 4.

For all vertices $v\in I_{LR}$, $f_{excess}(v)+f_{imbalance}(v)\leq w(v)$.
Moreover, for all vertices $v\in I_{LM}$ which are isolated,
$f_{excess}(v)=f_{imbalance}(v)=0$.

  5. 5.

For all vertices $v\in I_{LMR}$, $f_{excess}(v)+f_{imbalance}(v)\leq 2w(v)$.
Moreover, for all vertices $v\in I_{LMR}$ which are isolated,
$f_{excess}(v)=w(v)$ and $f_{imbalance}(v)=0$.

###### Proof.

For the first statement, observe that for vertices $v\notin I_{LM}\cup
I_{MR}\cup I_{LR}\cup I_{LMR}$, neither $v_{in}$ nor $v_{out}$ is ever a sink
or source so the flow into these vertices must equal the flow out of these
vertices and thus $f_{in}(v)=f_{out}(v)=f_{through}(v)$.

For the second statement, observe that for a vertex $v\in I_{LM}$,

  1. 1.

$F^{\prime}_{1}$ will have a flow of $f_{in}(v)$ into $v_{in}$ and along the
edge from $v_{in}$ to $v_{out}$

  2. 2.

$F^{\prime}_{2}$ will have a flow of $f_{out}(v)$ along the edge from $v_{in}$
to $v_{out}$ and out of $v_{out}$.

Thus, $f_{excess}(v)=f_{in}(v)+f_{out}(v)-\max\\{f_{in}(v),f_{out}(v)\\}$.
Since $f_{imbalance}(v)=|f_{in}(v)-f_{out}(v)|$,
$f_{excess}(v)+f_{imbalance}(v)=f_{in}(v)+f_{out}(v)-\min\\{f_{in}(v),f_{out}(v)\\}\leq
w(v)$.

If $v$ is isolated then neither $F^{\prime}_{1}$ nor $F^{\prime}_{2}$ can have
any flow to $v_{in}$ or out of $v_{out}$ so
$f_{in}(v)=f_{through}(v)=f_{out}(v)=0$

The third and fourth statements can be proved in the same way as the second
statement.

For the fifth statement, observe that for a vertex $v\in I_{LMR}$,

  1. 1.

$F^{\prime}_{1}$ will have a flow of $f_{in}(v)$ into $v_{in}$ and along the
edge from $v_{in}$ to $v_{out}$.

  2. 2.

$F^{\prime}_{2}$ will have a flow of $w(v)$ along the edge from $v_{in}$ to
$v_{out}$

  3. 3.

$F^{\prime}_{3}$ will have a flow of $f_{out}(v)$ along the edge from $v_{in}$
to $v_{out}$ and out of $v_{out}$.

Thus,
$f_{excess}(v)=w(v)+f_{in}(v)+f_{out}(v)-\max\\{f_{in}(v),f_{out}(v)\\}$.
Since $f_{imbalance}(v)=|f_{in}(v)-f_{out}(v)|$,
$f_{excess}(v)+f_{imbalance}(v)=w(v)+f_{in}(v)+f_{out}(v)-\min\\{f_{in}(v),f_{out}(v)\\}\leq
2w(v)$.

If $v$ is isolated then neither $F^{\prime}_{1}$ nor $F^{\prime}_{3}$ can have
any flow to $v_{in}$ or out of $v_{out}$ so $f_{in}(v)=f_{out}(v)=0$ and
$f_{through}(v)=w(v)$.

Putting everything together, we have the following corollary:

######  Corollary 9.42.

$\sum_{v\in V(\tau_{P})}{(f_{excess}(v)+f_{imbalance}(v))}\leq
w(I_{LM})+w(I_{LR})+w(I_{MR})+2w(I_{LMR})-(w(I_{\tau_{P}})-w(I_{\tau}))$

Combining this with Corollary 9.40,

$\displaystyle w(S_{\tau_{P},min})$ $\displaystyle\geq
val(F^{\prime}_{1})+val(F^{\prime}_{2})+val(F^{\prime}_{3})-\sum_{v\in
V(\tau_{P})}{(f_{excess}(v)+f_{imbalance}(v))}$ $\displaystyle\geq
w(U_{\gamma})+w(S_{\tau,min})+w(V_{{\gamma^{\prime}}^{T}})-w(I_{LM})-w(I_{LR})-w(I_{MR})-2w(I_{LMR})+(w(I_{\tau_{P}})-w(I_{\tau}))$

Since
$w(V(\tau_{P}))=w(V(\tau))+w(V(\gamma))+w(V(\gamma^{\prime}))-w(I_{LM})-w(I_{LR})-w(I_{MR})-2w(I_{LMR})$,

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

Rearranging this gives

$w(V(\tau_{P}))-w(S_{\tau_{P},min})+w(I_{\tau_{P}})\leq
w(V(\tau))-w(S_{\tau,min})+w(I_{\tau})+w(V(\gamma)\setminus
U_{\gamma})+w(V(\gamma^{\prime})\setminus U_{\gamma^{\prime}})$

which is the generalized intersection tradeoff lemma.

##  10 Showing Positivity

###  10.1 General strategy to lower bound
$\sum_{V\in\mathcal{I}_{mid}}{M^{fact}(H_{Id_{V}})}$

In this section, we describe how to show that
$\sum_{V\in\mathcal{I}_{mid}}{M^{fact}(H_{Id_{V}})}\succeq{\delta}Id_{Sym}$
for some $\delta>0$ where $\delta$ will depend on $n$ and other parameters.
For now, we assume that the indices of $\Lambda$ are multilinear monomials. We
will then describe the adjustments that are needed to handle non-multilinear
matrix indices.

We start with a few more definitions.

######  Definition 10.1.

For all $V\in\mathcal{I}_{mid}$ we define $Id_{Sym,V}$ to be the matrix such
that

  1. 1.

$Id_{Sym,V}(A,B)=1$ if $A$ and $B$ both have index shape $V$.

  2. 2.

Otherwise, $Id_{Sym,V}(A,B)=0$.

######  Proposition 10.2.

$Id_{Sym}=\sum_{V\in\mathcal{I}_{mid}}{Id_{Sym,V}}$

######  Definition 10.3.

For all $V\in\mathcal{I}_{mid}$ we define
$\lambda_{V}=|Aut(V)|H_{Id_{V}}(Id_{V},Id_{V})$

We now describe our strategy for showing
$\sum_{V\in\mathcal{I}_{mid}}{M^{fact}(H_{Id_{V}})}\succeq{\delta}Id_{Sym}$.
The idea is as follows. We will consider the index shapes
$V\in\mathcal{I}_{mid}$ from largest weight to smallest weight and we will
show that for each $V\in\mathcal{I}_{mid}$, there exists a $\delta_{V}>0$ such
that
$\sum_{V\in\mathcal{I}_{mid}}{M^{fact}(H_{Id_{V}})}\succeq\delta_{V}\sum_{U\in\mathcal{I}_{mid}:w(U)\geq
w(V)}{Id_{Sym,U}}$.

For the first step, letting $V_{max}$ be the maximum weight index shape in
$\mathcal{I}_{mid}$,
$M^{fact}(H_{Id_{V_{max}}})=\lambda_{V_{max}}Id_{Sym,V_{max}}$ because there
are no non-trivial left shapes $\sigma$ such that $V_{\sigma}=V_{max}$. For
other $V\in\mathcal{I}_{mid}$, $\lambda_{V}Id_{Sym,V}$ is a part of
$M^{fact}(H_{Id_{V}})$ but $M^{fact}(H_{Id_{V}})$ will also contain terms of
the form
$H_{Id_{V}}(\sigma,\sigma^{\prime})M_{\sigma}M_{{\sigma^{\prime}}^{T}}$ where
$U_{\sigma}\neq V$ or $U_{\sigma^{\prime}}\neq V$.

We can handle the terms
$H_{Id_{V}}(\sigma,\sigma^{\prime})M_{\sigma}M_{{\sigma^{\prime}}^{T}}$ where
$U_{\sigma}\neq V$ and $U_{\sigma^{\prime}}\neq V$ by bounding these terms in
terms of $Id_{Sym,U_{\sigma}}$ and $Id_{Sym,U_{\sigma^{\prime}}}$. Since
$w(U_{\sigma})>w(V)$ and $w(U_{\sigma^{\prime}})>w(V)$, $Id_{Sym,U_{\sigma}}$
and $Id_{Sym,U_{\sigma^{\prime}}}$ are already available to us. To handle the
terms $H_{Id_{V}}(\sigma,\sigma^{\prime})M_{\sigma}M_{{\sigma^{\prime}}^{T}}$
where exactly one of $U_{\sigma}$ and $U_{\sigma^{\prime}}$ are equal to $V$,
we use the following trick.

######  Definition 10.4.

Given $V\in\mathcal{I}_{mid}$, define $H^{\prime\prime}_{Id_{V}}$ to be the
coefficient matrix such that

  1. 1.

If $U_{\sigma}=U_{\sigma^{\prime}}=V$ then
$H^{\prime\prime}_{Id_{V}}(\sigma,\sigma^{\prime})=\frac{1}{2}H_{Id_{V}}(\sigma,\sigma^{\prime})$

  2. 2.

If exactly one of $U_{\sigma}$ and $U_{\sigma^{\prime}}$ are equal to $V$ then
$H^{\prime\prime}_{Id_{V}}(\sigma,\sigma^{\prime})=H_{Id_{V}}(\sigma,\sigma^{\prime})$

  3. 3.

If $U_{\sigma}\neq V$ and $U_{\sigma^{\prime}}\neq V$ then
$H^{\prime\prime}_{Id_{V}}(\sigma,\sigma^{\prime})=2H_{Id_{V}}(\sigma,\sigma^{\prime})$

######  Proposition 10.5.

$M^{fact}(H^{\prime\prime}_{Id_{V}})\succeq 0$

###### Proof.

Since $H_{Id_{V}}\succeq 0$, $H^{\prime\prime}_{Id_{V}}\succeq 0$ and thus
$M^{fact}(H^{\prime\prime}_{Id_{V}})\succeq 0$.

######  Corollary 10.6.

For all $V\in\mathcal{I}_{mid}$,

$M^{fact}(H_{Id_{V}})+\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}_{V}:U_{\sigma}\neq
V,U_{\sigma^{\prime}}\neq
V}{H_{Id_{V}}(\sigma,\sigma^{\prime})M_{\sigma}M_{{\sigma^{\prime}}^{T}}}\succeq\frac{\lambda_{V}}{2}Id_{Sym,V}$

###### Proof.

Observe that

$M^{fact}(H_{Id_{V}})-\frac{\lambda_{V}}{2}Id_{Sym,V}+\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}_{V}:U_{\sigma}\neq
V,U_{\sigma^{\prime}}\neq
V}{H_{Id_{V}}(\sigma,\sigma^{\prime})M_{\sigma}M_{{\sigma^{\prime}}^{T}}}=M^{fact}(H^{\prime\prime}_{Id_{V}})\succeq
0$

We now analyze the terms
$\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}_{V}:U_{\sigma}\neq
V,U_{\sigma^{\prime}}\neq
V}{H_{Id_{V}}(\sigma,\sigma^{\prime})M_{\sigma}M_{{\sigma^{\prime}}^{T}}}$.

######  Definition 10.7.

Given $U,V\in\mathcal{I}$ with $w(U)>w(V)$, we define $W(U,V)$ to be

$W(U,V)=\frac{1}{|Aut(U)|}\sum_{\sigma\in\mathcal{L}_{V}:U_{\sigma}=U}{\sum_{\sigma^{\prime}\in\mathcal{L}_{V}:U_{\sigma^{\prime}}\neq
V}{B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{V}}(\sigma,\sigma^{\prime})}}$

######  Lemma 10.8.

For all $V\in\mathcal{I}_{mid}$,

$\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}_{V}:U_{\sigma}\neq
V,U_{\sigma^{\prime}}\neq
V}{H_{Id_{V}}(\sigma,\sigma^{\prime})M_{\sigma}M_{{\sigma^{\prime}}^{T}}}\preceq\sum_{U\in\mathcal{I}_{mid}:w(U)>w(V)}{W(U,V)Id_{Sym,U}}$

###### Proof.

Observe that for all $\sigma,\sigma^{\prime}\in\mathcal{L}_{V}$ such that
$U_{\sigma}\neq V$ and $U_{\sigma^{\prime}}\neq V$,
$||M_{\sigma}M_{{\sigma^{\prime}}^{T}}||\leq
B_{norm}(\sigma)B_{norm}(\sigma^{\prime})$ and thus

$\frac{1}{2}\left(M_{\sigma}M_{{\sigma^{\prime}}^{T}}+M_{\sigma^{\prime}}M_{{\sigma}^{T}}\right)\preceq\frac{1}{2}B_{norm}(\sigma)B_{norm}(\sigma^{\prime})\left(M_{Id_{U_{\sigma}}}+M_{Id_{U_{\sigma^{\prime}}}}\right)$

Summing this equation over all $\sigma,\sigma^{\prime}\in\mathcal{L}_{V}$ such
that $U_{\sigma}\neq V$ and $U_{\sigma^{\prime}}\neq V$,

$\displaystyle\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}_{V}:U_{\sigma}\neq
V,U_{\sigma^{\prime}}\neq
V}{H_{Id_{U}}(\sigma,\sigma^{\prime})M_{\sigma}M_{{\sigma^{\prime}}^{T}}}\preceq\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}_{V}:U_{\sigma}\neq
V,U_{\sigma^{\prime}}\neq
V}{B_{norm}(\sigma)B_{norm}(\sigma^{\prime})M_{Id_{U_{\sigma}}}}$
$\displaystyle\preceq\sum_{U\in\mathcal{I}_{mid}:w(U)>w(V)}{\sum_{\sigma\in\mathcal{L}_{V}:U_{\sigma}=U}{\sum_{\sigma^{\prime}\in\mathcal{L}_{V}:V_{\sigma}\neq
V}{B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{U}}(\sigma,\sigma^{\prime})M_{Id_{U}}}}}$
$\displaystyle\preceq\sum_{U\in\mathcal{I}_{mid}:w(U)>w(V)}|Aut(U)|W(U,V)M_{Id_{U}}$

Since all of the coefficient matrices have SOS-symmetry, we can replace
$M_{Id_{U}}$ by $\frac{1}{|Aut(U)|}Id_{Sym,U}$ and this completes the proof.

Using this lemma, we can show the following theorem:

######  Theorem 10.9.

Let $G$ be the following directed graph:

  1. 1.

The vertices of $G$ are the index shapes $V\in\mathcal{I}_{mid}$

  2. 2.

For each $U,V\in\mathcal{I}_{mid}$ such that $w(U)>w(V)$, we have an edge
$e=(V,U)$ with weight $w(e)=\frac{2W(U,V)}{\lambda_{V}}$

For all $V\in\mathcal{I}_{mid}$,

$Id_{Sym,V}\preceq 2\sum_{U\in\mathcal{I}_{mid}:w(U)\geq
w(V)}{\left(\sum_{P:P\text{ is a path from V to U in }G}{\prod_{e\in
E(P)}{w(e)}}\right)\frac{1}{{\lambda_{U}}}M^{fact}(H_{Id_{U}})}$

###### Proof sketch.

This can be proved by starting with Corollary 10.6 and iteratively applying
Lemma 10.8 and Corollary 10.6.

####  10.1.1 Handling Non-multilinear Matrix Indices*

In order to handle non-multilinear matrix indices, we need to make a few
adjustments. First, we need to modify the definition of $Id_{Sym,V}$.

######  Definition 10.10.

For all $V\in\mathcal{I}_{mid}$ we define $Id_{Sym,V}$ to be the matrix such
that

  1. 1.

$Id_{Sym,V}(A,B)=1$ if $A$ and $B$ have the same index shape $U$ and $U$ has
the same number of each type of vertex as $V$. Note that $B$ may be a
permutation of $A$ and $U$ may have different powers than $V$.

  2. 2.

Otherwise, $Id_{Sym,V}(A,B)=0$.

Observe that with this modified definition, we will still have
$Id_{Sym}=\sum_{V\in\mathcal{I}_{mid}}{Id_{Sym,V}}$.

We also need to adjust how we define $\lambda_{V}$ as there are left shapes
$\sigma$ such that $U_{\sigma}$ and $V_{\sigma}$ have the same numbers and
types of vertices but $U_{\sigma}$ has different powers.

######  Definition 10.11.

Given $V\in\mathcal{I}_{mid}$, we define
$\mathcal{T}_{V}\subseteq\mathcal{L}_{V}$ to be the set of left shapes
$\sigma\in\mathcal{L}_{V}$ such that $U_{\sigma}$ has the same numbers and
types of vertices as $V$ (which automatically implies that
$E(\sigma)=\emptyset$).

######  Definition 10.12.

Define $Id^{*}_{Sym,V}$ to be the matrix indexed by left shapes
$\sigma,\sigma^{\prime}\in\mathcal{T}_{V}$ such that
$Id^{*}_{Sym,V}(\sigma,\sigma^{\prime})=\frac{1}{|Aut(V)|}$ if
$U_{\sigma}\equiv U_{\sigma^{\prime}}$ and
$Id^{*}_{Sym,V}(\sigma,\sigma^{\prime})=0$ otherwise.

######  Proposition 10.13.

$M^{fact}(Id^{*}_{Sym,V})=Id_{Sym,V}$

######  Definition 10.14.

Let $H^{\prime}_{Id_{V}}$ be the matrix $H_{Id_{V}}$ restricted to rows and
columns $\sigma,\sigma^{\prime}$ where
$\sigma,\sigma^{\prime}\in\mathcal{T}_{V}$. We define $\lambda_{V}$ to be the
largest constant $\lambda$ such that
$H^{\prime}_{Id_{V}}\succeq{\lambda}Id^{*}_{Sym,V}$

Finally, whenever we have the condition that $U_{\sigma}\neq V$, it should
instead be the condition that $U_{\sigma}$ does not have the same number of
each type of vertex as $V$. With these adjustments, the same arguments go
through.

###  10.2 Strategy to prove positivity in our applications

Now, we will illustrate the final ingredients needed to show positivity for
our applications.

To use Theorem 7.101, we would need to prove a statement of the form: Whenever
$\left\lVert M_{\alpha}\right\rVert\leq B_{norm}(\alpha)$ for all
$\alpha\in\mathcal{M}^{\prime}$,

$\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}{(H_{Id_{U}})}}\succeq
6\left(\sum_{U\in\mathcal{I}_{mid}}{\sum_{\gamma\in\Gamma_{U,*}}{\frac{d_{Id_{U}}(H^{\prime}_{\gamma},H_{Id_{U}})}{|Aut(U)|c(\gamma)}}}\right)Id_{sym}$

We will sketch the strategy we use to prove this. Let $D_{sos}$ be the degree
of the SoS program.

For the left hand side, we will prove a lower bound of the form: Whenever
$\left\lVert M_{\alpha}\right\rVert\leq B_{norm}(\alpha)$ for all
$\alpha\in{\mathcal{M}}^{\prime}$,

$\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}{(H_{Id_{U}})}}\succeq\frac{1}{n^{K_{1}D_{sos}^{2}}}Id_{sym}$

for a constant $K_{1}>0$. For this, we use the strategy from Section 10.1.
Then, we prove an upper bound on the right hand side of the form

$\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\gamma\in\Gamma_{U,*}}\frac{d_{Id_{U}}(H_{Id_{U}},H^{\prime}_{\gamma})}{|Aut(U)|c(\gamma)}\leq\frac{n^{K_{2}D_{sos}}}{2^{D_{V}}}$

for a constant $K_{2}>0$.

Now, we put these two together. Using the fact that $Id_{Sym}\succeq 0$, by
simply setting
$\frac{1}{n^{K_{1}D_{sos}^{2}}}>\frac{n^{K_{2}D_{sos}}}{2^{D_{V}}}$ which can
be obtained by choosing $D_{sos}$ small enough, we obtain the desired result.

We will also need the following bound that says that that lets us sum over all
shapes if we have sufficient decay for each vertex, then, the sum of this
decay, over all shapes $\sigma\circ\sigma^{\prime}$ for
$\sigma,\sigma^{\prime}\in{\mathcal{L}}_{U}^{\prime}$, is bounded.

######  Definition 10.15.

For $U\in{\mathcal{I}}_{mid}$, let
${\mathcal{L}}_{U}^{\prime}\subset{\mathcal{L}}_{U}$ be the set of non-trivial
shapes in ${\mathcal{L}}_{U}$.

######  Lemma 10.16.

Suppose $D_{V}=n^{C_{V}\varepsilon},D_{E}=n^{C_{E}\varepsilon}$ for constants
$C_{V},C_{E}>0$, are the truncation parameters for our shapes. For any
$U\in{\mathcal{I}}_{mid}$,

$\displaystyle\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in{\mathcal{L}}^{\prime}_{U}}\frac{1}{D_{sos}^{D_{sos}}n^{F\varepsilon|V(\sigma\circ\sigma^{\prime})|}}\leq
1$

for a constant $F>0$ that depends only on $C_{V},C_{E}$. In particular, by
setting $C_{V},C_{E}$ small enough, we can make this constant arbitrarily
small.

###### Proof.

For a given $j=|U|$, the number of ways to choose $U$ is at most
$t_{max}^{j}$. For a given $U\in{\mathcal{I}}_{mid}$, we will bound the number
of ways to choose $\sigma,\sigma^{\prime}\in{\mathcal{L}}_{U}^{\prime}$. To
choose $\sigma,\sigma^{\prime}\in{\mathcal{L}}^{\prime}_{U}$, it is sufficient
to choose

  * -

The number of vertices $j_{1}\geq 1$ (resp. $j_{1}^{\prime}\geq 1$) in
$U_{\sigma}\setminus V_{\sigma}$ (resp. $U_{\sigma^{\prime}}\setminus
V_{\sigma^{\prime}}$), their types of which there are at most $t_{max}$, and
their powers which have at most $D_{sos}$ choices.

  * -

The number of vertices $j_{2}$ (resp. $j_{2}^{\prime}$) in
$V(\sigma)\setminus(U_{\sigma}\cup V_{\sigma})$ (resp.
$V(\sigma^{\prime})\setminus(U_{\sigma^{\prime}}\cup V_{\sigma^{\prime}})$)
and also their types, of which there are at most $t_{max}$.

  * -

The position of each vertex $i$ in $U_{\sigma}\setminus V_{\sigma}$ (resp.
$U_{\sigma^{\prime}}\setminus V_{\sigma^{\prime}}$) within $U_{\sigma}$ (resp.
$U_{\sigma^{\prime}}$). There are at most $D_{V}$ choices for each vertex.

  * -

The subset of $U_{\sigma}$ (resp. $U_{\sigma^{\prime}}$) that is in
$V_{\sigma}$ (resp. $V_{\sigma^{\prime}}$) and a mapping in
$Aut(U_{\sigma}\cap V_{\sigma})$ (resp. $Aut(U_{\sigma^{\prime}}\cap
V_{\sigma^{\prime}})$) that determines the matching between the vertices in
$U_{\sigma}\cap V_{\sigma}$ (resp. $U_{\sigma^{\prime}}\cap
V_{\sigma^{\prime}}$).

  * -

The number $j_{3}$ (resp. $j_{3}^{\prime}$) of edges in $E(\sigma)$ (resp.
$E(\sigma^{\prime})$). and the $k$ endpoints of each edge. Each endpoint has
at most $D_{V}$ choices.

Therefore, for all $j\geq 0,j_{1},j_{1}^{\prime}\geq
1,j_{2},j_{2}^{\prime},j_{3},j_{3}^{\prime}\geq 0$, we have

$\displaystyle\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\begin{subarray}{c}\sigma,\sigma^{\prime}\in{\mathcal{L}}^{\prime}_{U}\\\
|U_{\sigma}\setminus V_{\sigma}|=j_{1},|U_{\sigma^{\prime}}\setminus
V_{\sigma^{\prime}}|=j_{1}^{\prime}\\\ |V(\sigma)\setminus(U_{\sigma}\cup
V_{\sigma})|=j_{2},|V(\sigma^{\prime})\setminus(U_{\sigma^{\prime}}\cup
V_{\sigma^{\prime}})|=j_{2}^{\prime}\\\
|E(\sigma)|=j_{3},|E(\sigma^{\prime})|=j_{3}^{\prime}\end{subarray}}\frac{1}{|Aut(U_{\sigma^{\prime}}\cap
V_{\sigma^{\prime}})||Aut(U_{\sigma}\cap
V_{\sigma})|(2t_{max})^{j+j_{2}+j_{2}^{\prime}}(D_{V}t_{max}D_{sos})^{j_{1}+j_{1}^{\prime}}(D_{V})^{kj_{3}}}\leq
1$

This implies that

$\displaystyle\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in{\mathcal{L}}^{\prime}_{U}}\frac{1}{D_{sos}^{D_{sos}}n^{F\varepsilon|V(\sigma\circ\sigma^{\prime})|}}\leq
1$

for a constant $F>0$ that only depends on $C_{V},C_{E}$.

##  11 Planted slightly denser subgraph: Full verification

In this section, we will prove all the required bounds to prove Theorem 1.1.

See 1.1

In particular, we will use Theorem 7.95 where we choose $\varepsilon$ in the
theorem, not to be confused with the $\varepsilon$ in Theorem 1.1, to be an
arbitrarily small constant.

######  Lemma 11.1.

For all $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$,

$\begin{bmatrix}\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}&B_{norm}(\tau)H_{\tau}\\\
B_{norm}(\tau)H_{\tau}^{T}&\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}\end{bmatrix}\succeq
0$

######  Lemma 11.2.

For all $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$ and all
$\gamma\in\Gamma_{U,V}$,

$c(\gamma)^{2}N(\gamma)^{2}B(\gamma)^{2}H_{Id_{V}}^{-\gamma,\gamma}\preceq
H_{\gamma}^{\prime}$

######  Lemma 11.3.

Whenever $\left\lVert M_{\alpha}\right\rVert\leq B_{norm}(\alpha)$ for all
$\alpha\in\mathcal{M}^{\prime}$,

$\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}{(H_{Id_{U}})}}\succeq
6\left(\sum_{U\in\mathcal{I}_{mid}}{\sum_{\gamma\in\Gamma_{U,*}}{\frac{d_{Id_{U}}(H^{\prime}_{\gamma},H_{Id_{U}})}{|Aut(U)|c(\gamma)}}}\right)Id_{sym}$

######  Corollary 11.4.

With constant probability, $\Lambda\succeq 0$.

###### Proof.

This follows by invoking Theorem 7.95 whose conditions follow from Lemma 4.7,
Lemma 11.1, Lemma 11.2 and Lemma 11.3.

###  11.1 Proof of Lemma 11.1

######  Lemma 11.5.

Suppose $k\leq n^{1/2-\varepsilon}$. For all $U\in{\mathcal{I}}_{mid}$ and
$\tau\in{\mathcal{M}}_{U}$,

$\sqrt{n}^{|V(\tau)|-|U_{\tau}|}S(\tau)\leq\frac{1}{n^{C_{p}\varepsilon|E(\tau)|}}$

###### Proof.

This result follows by plugging in the value of $S(\tau)$. Using $k\leq
n^{1/2-\varepsilon}$,

$\displaystyle\sqrt{n}^{|V(\tau)|-|U_{\tau}|}S(\tau)$
$\displaystyle=\sqrt{n}^{|V(\tau)|-|U_{\tau}|}\left(\frac{k}{n}\right)^{|V(\tau)|-|U_{\tau}|}(2(\frac{1}{2}+\frac{1}{2n^{C_{p}\varepsilon}})-1)^{|E(\tau)|}$
$\displaystyle\leq\frac{1}{n^{C_{p}\varepsilon|E(\tau)|}}$

######  Corollary 11.6.

For all $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$, we have

$c(\tau)B_{norm}(\tau)S(\tau)\leq 1$

###### Proof.

Since $\tau$ is a proper middle shape, we have $w(I_{\tau})=0$ and
$w(S_{\tau})=w(U_{\tau})$. This implies

$n^{\frac{w(V(\tau))+w(I_{\tau})-w(S_{\tau})}{2}}=\sqrt{n}^{|V(\tau)|-|U_{\tau}|}$

Since $\tau$ is proper, every vertex $i\in V(\tau)\setminus U_{\tau}$ or $i\in
V(\tau)\setminus V_{\tau}$ has $deg^{\tau}(i)\geq 1$ and hence,
$|V(\tau)\setminus U_{\tau}|+|V(\tau)\setminus V_{\tau}|\leq 4|E(\tau)|$.
Also, $q=n^{O(1)\cdot\varepsilon C_{V}}$. We can set $C_{V}$ sufficiently
small so that, using Lemma 11.5,

$\displaystyle c(\tau)B_{norm}(\tau)S(\tau)$
$\displaystyle=100(3D_{V})^{|U_{\tau}\setminus V_{\tau}|+|V_{\tau}\setminus
U_{\tau}|+2|E(\tau)|}2^{|V(\tau)\setminus(U_{\tau}\cup V_{\tau})|}$
$\displaystyle\quad\cdot(6D_{V}\sqrt[4]{2eq})^{|V(\tau)\setminus
U_{\tau}|+|V(\tau)\setminus V_{\tau}|}\sqrt{n}^{|V(\tau)|-|U_{\tau}|}S(\tau)$
$\displaystyle\leq n^{O(1)\cdot\varepsilon
C_{V}\cdot|E(\tau)|}\cdot\sqrt{n}^{|V(\tau)|-|U_{\tau}|}S(\tau)$
$\displaystyle\leq n^{O(1)\cdot\varepsilon
C_{V}\cdot|E(\tau)|}\cdot\frac{1}{n^{C_{p}\varepsilon|E(\tau)|}}$
$\displaystyle\leq 1$

We can now prove Lemma 11.1.

See 11.1

###### Proof.

We have

$\displaystyle\begin{bmatrix}\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}&B_{norm}(\tau)H_{\tau}\\\
B_{norm}(\tau)H_{\tau}^{T}&\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}\end{bmatrix}=$
$\displaystyle\begin{bmatrix}\left(\frac{1}{|Aut(U)|c(\tau)}-\frac{S(\tau)B_{norm}(\tau)}{|Aut(U)|}\right)H_{Id_{U}}&0\\\
0&\left(\frac{1}{|Aut(U)|c(\tau)}-\frac{S(\tau)B_{norm}(\tau)}{|Aut(U)|}\right)H_{Id_{U}}\end{bmatrix}$
$\displaystyle+B_{norm}(\tau)\begin{bmatrix}\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}&H_{\tau}\\\
H_{\tau}^{T}&\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}\end{bmatrix}$

By Lemma 4.9, $\begin{bmatrix}\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}&H_{\tau}\\\
H_{\tau}^{T}&\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}\end{bmatrix}\succeq 0$, so the
second term above is positive semidefinite. For the first term, by Lemma 4.7,
$H_{Id_{U}}\succeq 0$ and by Corollary 11.6,
$\frac{1}{|Aut(U)|c(\tau)}-\frac{S(\tau)B_{norm}(\tau)}{|Aut(U)|}\geq 0$,
which proves that the first term is also positive semidefinite.

###  11.2 Proof of Lemma 11.2

######  Lemma 11.7.

Suppose $k\leq n^{1/2-\varepsilon}$. For all $U,V\in{\mathcal{I}}_{mid}$ where
$w(U)>w(V)$ and for all $\gamma\in\Gamma_{U,V}$,

$n^{w(V(\gamma)\setminus
U_{\gamma})}S(\gamma)^{2}\leq\frac{1}{n^{B\varepsilon(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|+|E(\gamma)|)}}$

for some constant $B$ that depends only on $C_{p}$. In particular, it is
independent of $C_{V}$.

###### Proof.

Since $\gamma$ is a left shape, we have $|U_{\gamma}|\geq|V_{\gamma}|$ as
$V_{\gamma}$ is the unique minimum vertex separator of $\gamma$ and so,
$n^{w(V(\gamma)\setminus U_{\gamma})}=n^{|V(\gamma)|-|U_{\gamma}|}\leq
n^{|V(\gamma)|-\frac{|U_{\gamma}|+|V_{\gamma}|}{2}}$. Also, note that
$2|V(\gamma)|-|U_{\gamma}|-|V_{\gamma}|=|U_{\gamma}\setminus
V_{\gamma}|+|V_{\gamma}\setminus U_{\gamma}|+2|V(\gamma)\setminus
U_{\gamma}\setminus V_{\gamma}|\geq|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|$. Therefore,

$\displaystyle n^{w(V(\gamma)\setminus U_{\gamma})}S(\gamma)^{2}$
$\displaystyle=n^{|V(\gamma)\setminus
U_{\gamma})|}\left(\frac{k}{n}\right)^{2|V(\gamma)|-|U_{\gamma}|-|V_{\gamma}|}(2(\frac{1}{2}+\frac{1}{2n^{C_{p}\varepsilon}})-1)^{2|E(\gamma)|}$
$\displaystyle\leq
n^{|V(\gamma)|-\frac{|U_{\gamma}|+|V_{\gamma}|}{2}}\left(\frac{1}{n^{1/2+\varepsilon}}\right)^{2|V(\gamma)|-|U_{\gamma}|-|V_{\gamma}|}\left(\frac{1}{n^{2C_{p}\varepsilon}}\right)^{|E(\gamma)|}$
$\displaystyle\leq\left(\frac{1}{n^{\varepsilon}}\right)^{2|V(\gamma)|-|U_{\gamma}|-|V_{\gamma}|}\left(\frac{1}{n^{2C_{p}\varepsilon}}\right)^{|E(\gamma)|}$
$\displaystyle\leq\frac{1}{n^{B\varepsilon(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|+\sum_{e\in E(\gamma)}l_{e})}}$

for a constant $B$ that depends only on $C_{p}$.

We can now prove Lemma 11.2.

See 11.2

###### Proof.

By Lemma 4.11, we have

$\displaystyle
c(\gamma)^{2}N(\gamma)^{2}B(\gamma)^{2}H_{Id_{V}}^{-\gamma,\gamma}$
$\displaystyle\preceq
c(\gamma)^{2}N(\gamma)^{2}B(\gamma)^{2}S(\gamma)^{2}\frac{|Aut(U)|}{|Aut(V)|}H^{\prime}_{\gamma}$

Using the same proof as in Lemma 4.7, we can see that
$H^{\prime}_{\gamma}\succeq 0$. Therefore, it suffices to prove that

$c(\gamma)^{2}N(\gamma)^{2}B(\gamma)^{2}S(\gamma)^{2}\frac{|Aut(U)|}{|Aut(V)|}\leq
1$

Since $U,V\in{\mathcal{I}}_{mid}$, $|Aut(U)|=|U|!,|Aut(V)|=|V|!$. Therefore,
$\frac{|Aut(U)|}{|Aut(V)|}=\frac{|U|!}{|V|!}\leq D_{V}^{|U_{\gamma}\setminus
V_{\gamma}|}$. Also, $q=n^{O(1)\cdot\varepsilon C_{V}}$. Let $B$ be the
constant from Lemma 11.7. We can set $C_{V}$ sufficiently small so that, using
Lemma 11.7,

$\displaystyle
c(\gamma)^{2}N(\gamma)^{2}B(\gamma)^{2}S(\gamma)^{2}\frac{|Aut(U)|}{|Aut(V)|}$
$\displaystyle\leq 100^{2}(3D_{V})^{2|U_{\gamma}\setminus
V_{\gamma}|+2|V_{\gamma}\setminus
U_{\gamma}|+4|E(\alpha)|}4^{|V(\gamma)\setminus(U_{\gamma}\cup V_{\gamma})|}$
$\displaystyle\quad\cdot(3D_{V})^{4|V(\gamma)\setminus
V_{\gamma}|+2|V(\gamma)\setminus
U_{\gamma}|}(6D_{V}\sqrt[4]{2eq})^{2|V(\gamma)\setminus
U_{\gamma}|+2|V(\gamma)\setminus V_{\gamma}|}$ $\displaystyle\quad\cdot
n^{w(V(\gamma)\setminus U_{\gamma})}S(\gamma)^{2}\cdot
D_{V}^{|U_{\gamma}\setminus V_{\gamma}|}$ $\displaystyle\leq
n^{O(1)\cdot\varepsilon C_{V}\cdot(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|+\sum_{e\in E(\gamma)}l_{e})}\cdot n^{w(V(\gamma)\setminus
U_{\gamma})}S(\gamma)^{2}$ $\displaystyle\leq n^{O(1)\cdot\varepsilon
C_{V}\cdot(|V(\gamma)\setminus(U_{\gamma}\cap V_{\gamma})|+\sum_{e\in
E(\gamma)}l_{e})}\cdot\frac{1}{n^{B\varepsilon(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|+\sum_{e\in E(\gamma)}l_{e})}}$ $\displaystyle\leq 1$

###  11.3 Proof of Lemma 11.3

In this section, we will prove Lemma 11.3.

See 11.3

We use the strategy from Section 10. We will prove the following lemmas.

######  Lemma 11.8.

Whenever $\left\lVert M_{\alpha}\right\rVert\leq B_{norm}(\alpha)$ for all
$\alpha\in{\mathcal{M}}^{\prime}$,

$\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}{(H_{Id_{U}})}}\succeq\frac{1}{n^{K_{1}D_{sos}^{2}}}Id_{sym}$

for a constant $K_{1}>0$.

######  Lemma 11.9.

$\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\gamma\in\Gamma_{U,*}}\frac{d_{Id_{U}}(H_{Id_{U}},H^{\prime}_{\gamma})}{|Aut(U)|c(\gamma)}\leq\frac{n^{K_{2}D_{sos}}}{2^{D_{V}}}$

for a constant $K_{2}>0$.

If we assume these, we can conclude the following.

See 11.3

###### Proof.

Let $\left\lVert M_{\alpha}\right\rVert\leq B_{norm}(\alpha)$ for all
$\alpha\in{\mathcal{M}}^{\prime}$. By Lemma 11.8,

$\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}{(H_{Id_{U}})}}\succeq\frac{1}{n^{K_{1}D_{sos}^{2}}}Id_{sym}$

for a constant $K_{1}>0$. By Lemma 11.9,

$\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\gamma\in\Gamma_{U,*}}\frac{d_{Id_{U}}(H_{Id_{U}},H^{\prime}_{\gamma})}{|Aut(U)|c(\gamma)}\leq\frac{n^{K_{2}D_{sos}}}{2^{D_{V}}}$

for a constant $K_{2}>0$.

We choose $C_{sos}$ sufficiently small so that
$\frac{1}{n^{K_{1}D_{sos}^{2}}}\geq 6\frac{n^{K_{2}D_{sos}}}{2^{D_{V}}}$ which
can be satisfied by setting $C_{sos}<K_{3}C_{V}$ for a sufficiently small
constant $K_{3}>0$. Then, since $Id_{Sym}\succeq 0$, using Lemma 11.8 and
Lemma 11.9,

$\displaystyle\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}{(H_{Id_{U}})}}$
$\displaystyle\succeq\frac{1}{n^{K_{1}D_{sos}^{2}}}Id_{sym}$
$\displaystyle\succeq 6\frac{n^{K_{2}D_{sos}}}{2^{D_{V}}}Id_{sym}$
$\displaystyle\succeq
6\left(\sum_{U\in\mathcal{I}_{mid}}{\sum_{\gamma\in\Gamma_{U,*}}{\frac{d_{Id_{U}}(H^{\prime}_{\gamma},H_{Id_{U}})}{|Aut(U)|c(\gamma)}}}\right)Id_{sym}$

The rest of the section is devoted to proving Lemma 11.8 and Lemma 11.9.

In the proofs of both these lemmas, we will need a bound on
$B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{U}}(\sigma,\sigma^{\prime})$
that is obtained below.

######  Lemma 11.10.

Suppose $k\leq n^{1/2-\varepsilon}$. For all $U\in{\mathcal{I}}_{mid}$ and
$\sigma,\sigma^{\prime}\in{\mathcal{L}}_{U}$,

$B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{U}}(\sigma,\sigma^{\prime})\leq\frac{1}{n^{0.5\varepsilon|V(\alpha)|}}$

###### Proof.

Let $\alpha=\sigma\circ\sigma^{\prime}$. Observe that
$|V(\sigma)|+|V(\sigma^{\prime})|=|V(\alpha)|+|U|$. By choosing $C_{V}$
sufficiently small,

$\displaystyle
B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{U}}(\sigma,\sigma^{\prime})$
$\displaystyle=(6D_{V}\sqrt[4]{2eq})^{|V(\sigma)\setminus
U_{\sigma}|+|V(\sigma)\setminus V_{\sigma}|}n^{\frac{w(V(\sigma))-w(U)}{2}}$
$\displaystyle\quad\cdot(6D_{V}\sqrt[4]{2eq})^{|V(\sigma^{\prime})\setminus
U_{\sigma^{\prime}}|+|V(\sigma^{\prime})\setminus
V_{\sigma^{\prime}}|}n^{\frac{w(V(\sigma^{\prime}))-w(U)}{2}}$
$\displaystyle\quad\cdot\frac{1}{|Aut(U)|}\left(\frac{k}{n}\right)^{|V(\alpha)|}(2(\frac{1}{2}+\frac{1}{2n^{C_{p}\varepsilon}})-1)^{|E(\alpha)|}$
$\displaystyle\leq n^{O(1)\cdot\varepsilon
C_{V}\cdot|V(\alpha)|}\sqrt{n}^{|V(\sigma)|-|U|}\sqrt{n}^{|V(\sigma^{\prime})|-|U|}\left(\frac{k}{n}\right)^{|V(\alpha)|}\frac{1}{n^{C_{p}\varepsilon|E(\alpha)|}}$
$\displaystyle\leq n^{O(1)\cdot\varepsilon
C_{V}\cdot|V(\alpha)|}\sqrt{n}^{|V(\alpha)|-|U|}\left(\frac{1}{n^{1/2+\varepsilon}}\right)^{|V(\alpha)|}\frac{1}{n^{C_{p}\varepsilon|E(\alpha)|}}$
$\displaystyle\leq n^{O(1)\cdot\varepsilon
C_{V}\cdot|V(\alpha)|}\cdot\frac{1}{n^{\varepsilon|V(\alpha)|}}\cdot\frac{1}{n^{C_{p}\varepsilon|E(\alpha)|}}$
$\displaystyle\leq\frac{1}{n^{0.5\varepsilon|V(\alpha)|}}$

####  11.3.1 Proof of Lemma 11.8

To prove Lemma 11.8, we will use the strategy from Section 10.1. We will also
use the notation from that section. We recall that for
$U\in{\mathcal{I}}_{mid}$,
${\mathcal{L}}_{U}^{\prime}\subset{\mathcal{L}}_{U}$ was the set of non-
trivial shapes in ${\mathcal{L}}_{U}$.

######  Proposition 11.11.

For $V\in{\mathcal{I}}_{mid}$, $\lambda_{V}=\left(\frac{k}{n}\right)^{|V|}$.

###### Proof.

We have
$\lambda_{V}=|Aut(V)|H_{Id_{V}}(Id_{V},Id_{V})=\left(\frac{k}{n}\right)^{|V|}$.

######  Corollary 11.12.

$\lambda_{V}\geq\frac{1}{n^{O(1)D_{sos}}}$

######  Lemma 11.13.

For any edge $e=(V,U)$ in $G$, we have

$w(e)\leq\frac{n^{O(1)D_{sos}}}{n^{0.1\varepsilon|U|}}$

###### Proof.

Let $e=(V,U)$ be an edge in $G$. Then, $w(U)>w(V)$ and
$w(e)=\frac{2W(U,V)}{\lambda_{V}}$. Using Lemma 11.10, we have

$\displaystyle 2W(U,V)$
$\displaystyle=\frac{2}{|Aut(U)|}\sum_{\sigma\in{\mathcal{L}}_{V},U_{\sigma}=U}\sum_{\sigma^{\prime}\in{\mathcal{L}}_{V},U_{\sigma^{\prime}}\neq
V}B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{U}}(\sigma,\sigma^{\prime})$
$\displaystyle\leq\frac{2}{|Aut(U)|}\sum_{\sigma\in{\mathcal{L}}_{V},U_{\sigma}=U}\sum_{\sigma^{\prime}\in{\mathcal{L}}_{V},U_{\sigma^{\prime}}\neq
V}\frac{1}{n^{0.5\varepsilon|V(\sigma\circ\sigma^{\prime})|}}$
$\displaystyle\leq\sum_{\sigma,\sigma^{\prime}\in{\mathcal{L}}_{V}^{\prime}}\frac{2}{n^{0.5\varepsilon|V(\sigma\circ\sigma^{\prime})|}}$
$\displaystyle\leq\sum_{\sigma,\sigma^{\prime}\in{\mathcal{L}}_{V}^{\prime}}\frac{D_{sos}^{D_{sos}}}{n^{0.1\varepsilon|V(\sigma\circ\sigma^{\prime})|}D_{sos}^{D_{sos}}n^{F\varepsilon|V(\sigma\circ\sigma^{\prime})|}}$
$\displaystyle\leq\frac{D_{sos}^{D_{sos}}}{n^{0.1\varepsilon|U|}}\sum_{\sigma,\sigma^{\prime}\in{\mathcal{L}}_{V}^{\prime}}\frac{1}{D_{sos}^{D_{sos}}n^{F\varepsilon|V(\sigma\circ\sigma^{\prime})|}}$
$\displaystyle\leq\frac{D_{sos}^{D_{sos}}}{n^{0.1\varepsilon|U|}}$
$\displaystyle\leq\frac{\lambda_{V}n^{O(1)D_{sos}}}{n^{0.1\varepsilon|U|}}$

where we set $C_{V}$ small enough so that $0.4\geq F$ and invoked Lemma 10.16.
This proves the lemma.

######  Corollary 11.14.

For any $U,V\in{\mathcal{I}}_{mid}$ such that $w(U)>w(V)$,

$\displaystyle\sum_{P:P\text{ is a path from V to U in G}}\prod_{e\in
E(P)}w(e)\leq n^{O(1)D_{sos}^{2}}$

###### Proof.

The total number of vertices in $G$ is at most $D_{sos}+1$ since each
$U\in{\mathcal{I}}_{mid}$ has at most $D_{sos}$ vertices. Therefore, for any
fixed integer $j\geq 1$, the number of paths from $V$ to $U$ of length $j$ is
at most $(D_{sos}+1)^{j}$. Take any path $P$ from $V$ to $U$. Suppose it has
length $j\geq 1$. Note that for all edges $e=(V^{\prime},U^{\prime})$ in
$E(P)$, since $|U^{\prime}|\geq 1$, we have

$w(e)\leq\frac{n^{O(1)D_{sos}}}{n^{0.1\varepsilon|U^{\prime}|}}\leq\frac{n^{O(1)D_{sos}}}{n^{0.1\varepsilon}}$

So, $\prod_{e\in
E(P)}w(e)\leq\left(\frac{n^{O(1)D_{sos}}}{n^{0.1\varepsilon}}\right)^{j}$.
Therefore, by setting $C_{sos}$ small enough,

$\displaystyle\sum_{P:P\text{ is a path from V to U in G}}\prod_{e\in
E(P)}w(e)$
$\displaystyle\leq\sum_{j=1}^{D_{sos}}(D_{sos}+1)^{j}\left(\frac{n^{O(1)D_{sos}}}{n^{0.1\varepsilon}}\right)^{j}$
$\displaystyle\leq n^{O(1)D_{sos}^{2}}$

We can now prove Lemma 11.8.

See 11.8

###### Proof.

For all $V\in{\mathcal{I}}_{mid}$, we have

$\displaystyle Id_{Sym,V}\preceq 2\sum_{U\in\mathcal{I}_{mid}:w(U)\geq
w(V)}{\left(\sum_{P:P\text{ is a path from V to U in }G}{\prod_{e\in
E(P)}{w(e)}}\right)\frac{1}{{\lambda_{U}}}M^{fact}(H_{Id_{U}})}$

Summing this over all $V\in{\mathcal{I}}_{mid}$, we get

$\displaystyle Id_{Sym}$
$\displaystyle\preceq\sum_{U\in{\mathcal{I}}_{mid}}\frac{2}{\lambda_{U}}\left(\sum_{V\in{\mathcal{I}}_{mid}:w(U)\geq
w(V)}\sum_{P:P\text{ is a path from V to U in G}}\prod_{e\in
E(P)}w(e)\right)M^{fact}(H_{Id_{U}})$
$\displaystyle\preceq\sum_{U\in{\mathcal{I}}_{mid}}\frac{2}{\lambda_{U}}\left(\sum_{V\in{\mathcal{I}}_{mid}:w(U)\geq
w(V)}n^{O(1)D_{sos}^{2}}\right)M^{fact}(H_{Id_{U}})$

For any fixed $U\in{\mathcal{I}}_{mid}$, the number of
$V\in{\mathcal{I}}_{mid}$ such that $w(U)\geq w(V)$ is at most $D_{sos}+1$.
Also, $\lambda_{U}\geq\frac{1}{d^{O(1)D_{sos}}}$ for all
$U\in{\mathcal{I}}_{mid}$. Therefore,

$\displaystyle Id_{Sym}$
$\displaystyle\preceq\sum_{U\in{\mathcal{I}}_{mid}}\frac{2}{\lambda_{U}}(D_{sos}+1)n^{O(1)D_{sos}^{2}}M^{fact}(H_{Id_{U}})$
$\displaystyle\preceq\sum_{U\in{\mathcal{I}}_{mid}}n^{O(1)D_{sos}^{2}}M^{fact}(H_{Id_{U}})$

where we used the fact that for all $U\in{\mathcal{I}}_{mid}$,
$M^{fact}(H_{Id_{U}})\succeq 0$.

####  11.3.2 Proof of Lemma 11.9

We restate the lemma for convenience.

See 11.9

###### Proof.

We have

$\displaystyle\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\gamma\in\Gamma_{U,*}}\frac{d_{Id_{U}}(H_{Id_{U}},H^{\prime}_{\gamma})}{|Aut(U)|c(\gamma)}=\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\gamma\in\Gamma_{U,*}}\frac{1}{|Aut(U)|c(\gamma)}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}_{U_{\gamma}}:|V(\sigma)|\leq
D_{V},|V(\sigma^{\prime})|\leq D_{V},\atop|V(\sigma\circ\gamma)|>D_{V}\text{
or
}|V(\sigma^{\prime}\circ\gamma)|>D_{V}}{B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{U_{\gamma}}}(\sigma,\sigma^{\prime})}$

The set of $\sigma,\sigma^{\prime}$ that could appear in the above sum must
necessarily be non-trivial and hence,
$\sigma,\sigma^{\prime}\in{\mathcal{L}}_{U}^{\prime}$. Then,

$\displaystyle\sum_{U\in{\mathcal{I}}_{mid}}$
$\displaystyle\sum_{\gamma\in\Gamma_{U,*}}\frac{d_{Id_{U}}(H_{Id_{U}},H^{\prime}_{\gamma})}{|Aut(U)|c(\gamma)}$
$\displaystyle=\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}{B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{U}}(\sigma,\sigma^{\prime})}\sum_{\gamma\in\Gamma_{U,*}:|V(\sigma\circ\gamma)|>D_{V}\text{
or }|V(\sigma^{\prime}\circ\gamma)|>D_{V}}\frac{1}{|Aut(U)|c(\gamma)}$

For $\sigma\in{\mathcal{L}}^{\prime}_{U}$, define
$m_{\sigma}=D_{V}+1-|V(\sigma)|\geq 1$. This is precisely set so that for all
$\gamma\in\Gamma_{U,*}$, we have $|V(\sigma\circ\gamma)|>D_{V}$ if and only if
$|V(\gamma)|\geq|U|+m_{\sigma}$. So, for
$\sigma,\sigma^{\prime}\in{\mathcal{L}}^{\prime}_{U}$, using Lemma 9.31

$\displaystyle\sum_{\gamma\in\Gamma_{U,*}:|V(\sigma\circ\gamma)|>D_{V}\text{
or }|V(\sigma^{\prime}\circ\gamma)|>D_{V}}\frac{1}{|Aut(U)|c(\gamma)}$
$\displaystyle=\sum_{\gamma\in\Gamma_{U,*}:|V(\gamma)|\geq|U|+\min(m_{\sigma},m_{\sigma^{\prime}})}\frac{1}{|Aut(U)|c(\gamma)}$
$\displaystyle\leq\frac{1}{2^{\min(m_{\sigma},m_{\sigma^{\prime}})-1}}$

Also, for $\sigma,\sigma^{\prime}\in{\mathcal{L}}_{U}^{\prime}$, we have
$|V(\sigma\circ\sigma^{\prime})|+min(m_{\sigma},m_{\sigma^{\prime}})-1\geq
D_{V}$. Therefore,

$\displaystyle\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\gamma\in\Gamma_{U,*}}\frac{d_{Id_{U}}(H_{Id_{U}},H^{\prime}_{\gamma})}{|Aut(U)|c(\gamma)}$
$\displaystyle\leq\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}{B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{U}}(\sigma,\sigma^{\prime})\frac{1}{2^{\min(m_{\sigma},m_{\sigma^{\prime}})-1}}}$
$\displaystyle\leq\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}\frac{n^{O(1)D_{sos}}}{n^{0.5\varepsilon|V(\sigma\circ\sigma^{\prime})|}2^{\min(m_{\sigma},m_{\sigma^{\prime}})-1}}$

where we used Lemma 11.10. Using
$n^{0.5\varepsilon|V(\sigma\circ\sigma^{\prime})|}\geq
n^{0.1\varepsilon|V(\sigma\circ\sigma^{\prime})|}2^{|V(\sigma\circ\sigma^{\prime})|}$,

$\displaystyle\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\gamma\in\Gamma_{U,*}}\frac{d_{Id_{U}}(H_{Id_{U}},H^{\prime}_{\gamma})}{|Aut(U)|c(\gamma)}$
$\displaystyle\leq\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}\frac{n^{O(1)D_{sos}}}{n^{0.1\varepsilon|V(\sigma\circ\sigma^{\prime})|}2^{|V(\sigma\circ\sigma^{\prime})|}2^{\min(m_{\sigma},m_{\sigma^{\prime}})-1}}$
$\displaystyle\leq\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}\frac{n^{O(1)D_{sos}}}{n^{0.1\varepsilon|V(\sigma\circ\sigma^{\prime})|}2^{D_{V}}}$
$\displaystyle\leq\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}\frac{n^{O(1)D_{sos}}}{D_{sos}^{D_{sos}}n^{0.1\varepsilon|V(\sigma\circ\sigma^{\prime})|}2^{D_{V}}}$

The final step will be to argue that
$\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}\frac{1}{D_{sos}^{D_{sos}}n^{0.1\varepsilon|V(\sigma\circ\sigma^{\prime})|}}\leq
1$ which will complete the proof. But this will follow from Lemma 10.16 if we
set $C_{V}$ small enough.

##  12 Tensor PCA: Full verification

In this section, we will prove all the bounds required to prove Theorem 1.3.

See 1.3

In particular, we will use Theorem 7.101 where we choose $\varepsilon$ in the
theorem, not to be confused with the $\varepsilon$ in Theorem 1.3, to be an
arbitrarily small constant.

######  Lemma 12.1.

For all $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$,

$\begin{bmatrix}\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}&B_{norm}(\tau)H_{\tau}\\\
B_{norm}(\tau)H_{\tau}^{T}&\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}\end{bmatrix}\succeq
0$

######  Lemma 12.2.

For all $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$ and all
$\gamma\in\Gamma_{U,V}$,

$c(\gamma)^{2}N(\gamma)^{2}B(\gamma)^{2}H_{Id_{V}}^{-\gamma,\gamma}\preceq
H_{\gamma}^{\prime}$

######  Lemma 12.3.

Whenever $\left\lVert M_{\alpha}\right\rVert\leq B_{norm}(\alpha)$ for all
$\alpha\in\mathcal{M}^{\prime}$,

$\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}{(H_{Id_{U}})}}\succeq
6\left(\sum_{U\in\mathcal{I}_{mid}}{\sum_{\gamma\in\Gamma_{U,*}}{\frac{d_{Id_{U}}(H^{\prime}_{\gamma},H_{Id_{U}})}{|Aut(U)|c(\gamma)}}}\right)Id_{sym}$

######  Corollary 12.4.

With constant probability, $\Lambda\succeq 0$.

###### Proof.

This follows by invoking Theorem 7.101 whose conditions follow from Lemma
5.10, Lemma 12.1, Lemma 12.2 and Lemma 12.3.

###  12.1 Proof of Lemma 12.1

######  Lemma 12.5.

Suppose $\lambda\leq n^{\frac{k}{4}-\varepsilon}$. For all
$U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$, suppose
$deg^{\tau}(i)$ is even for all $i\in V(\tau)\setminus U_{\tau}\setminus
V_{\tau}$, then

$\sqrt{n}^{|V(\tau)|-|U_{\tau}|}S(\tau)\leq\frac{1}{n^{0.5\varepsilon\sum_{e\in
E(\tau)}l_{e}}}$

###### Proof.

Firstly, we claim that $\sum_{e\in E(\tau)}kl_{e}\geq
2(|V(\tau)|-|U_{\tau}|)$. For any vertex $i\in V(\tau)\setminus
U_{\tau}\setminus V_{\tau}$, $deg^{\tau}(i)$ is even and is not $0$, hence,
$deg^{\tau}(i)\geq 2$. Any vertex $i\in U_{\tau}\setminus V_{\tau}$ cannot
have $deg^{\tau}(i)=0$ otherwise $U_{\tau}\setminus\\{i\\}$ is a vertex
separator of strictly smaller weight than $U_{\tau}$, which is not possible,
hence, $deg^{\tau}(i)\geq 1$. Therefore,

$\displaystyle\sum_{e\in E(\tau)}kl_{e}$ $\displaystyle=\sum_{i\in
V(\tau)}deg^{\tau}(i)$ $\displaystyle\geq\sum_{i\in V(\tau)\setminus
U_{\tau}\setminus V_{\tau}}deg^{\tau}(i)+\sum_{i\in U_{\tau}\setminus
V_{\tau}}deg^{\tau}(i)+\sum_{i\in V_{\tau}\setminus U_{\tau}}deg^{\tau}(i)$
$\displaystyle\geq 2|V(\tau)\setminus U_{\tau}\setminus
V_{\tau}|+|U_{\tau}\setminus V_{\tau}|+|V_{\tau}\setminus U_{\tau}|$
$\displaystyle=2(|V(\tau)|-|U_{\tau}|)$

By choosing $C_{\Delta}$ sufficiently small, we have

$\displaystyle\sqrt{n}^{|V(\tau)|-|U_{\tau}|}S(\tau)$
$\displaystyle=\sqrt{n}^{|V(\tau)|-|U_{\tau}|}\Delta^{|V(\tau)|-|U_{\tau}|}\prod_{e\in
E(\tau)}\left(\frac{\lambda}{(\Delta n)^{\frac{k}{2}}}\right)^{l_{e}}$
$\displaystyle\leq\sqrt{n}^{|V(\tau)|-|U_{\tau}|}\Delta^{|V(\tau)|-|U_{\tau}|}\prod_{e\in
E(\tau)}n^{(-\frac{k}{4}-0.5\varepsilon)l_{e}}$
$\displaystyle=\sqrt{n}^{|V(\tau)|-|U_{\tau}|-\frac{\sum_{e\in
E(\tau)}kl_{e}}{2}}\Delta^{|V(\tau)|-|U_{\tau}|}\prod_{e\in
E(\tau)}n^{-0.5\varepsilon l_{e}}$
$\displaystyle=\Delta^{|V(\tau)|-|U_{\tau}|}\prod_{e\in
E(\tau)}n^{-0.5\varepsilon l_{e}}$
$\displaystyle\leq\frac{1}{n^{0.5\varepsilon\sum_{e\in E(\tau)}l_{e}}}$

######  Corollary 12.6.

For all $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$, we have

$c(\tau)B_{norm}(\tau)S(\tau)\leq 1$

###### Proof.

Since $\tau$ is a proper middle shape, we have $w(I_{\tau})=0$ and
$w(S_{\tau,min})=w(U_{\tau})$. This implies

$n^{\frac{w(V(\tau))+w(I_{\tau})-w(S_{\tau,min})}{2}}=\sqrt{n}^{|V(\tau)|-|U_{\tau}|}$

If $deg^{\tau}(i)$ is odd for any vertex $i\in V(\tau)\setminus
U_{\tau}\setminus V_{\tau}$, then $S(\tau)=0$ and the inequality is true. So,
assume $deg^{\tau}(i)$ is even for all $i\in V(\tau)\setminus
U_{\tau}\setminus V_{\tau}$. As was observed in the proof of Lemma 12.5, every
vertex $i\in V(\tau)\setminus U_{\tau}$ or $i\in V(\tau)\setminus V_{\tau}$
has $deg^{\tau}(i)\geq 1$ and hence, $|V(\tau)\setminus
U_{\tau}|+|V(\tau)\setminus V_{\tau}|\leq 4\sum_{e\in E(\tau)}l_{e}$. Also,
$|E(\tau)|\leq\sum_{e\in E(\tau)}l_{e}$ and
$q=n^{O(1)\cdot\varepsilon(C_{V}+C_{E})}$. We can set $C_{V},C_{E}$
sufficiently small so that, using Lemma 12.5,

$\displaystyle c(\tau)B_{norm}(\tau)S(\tau)$
$\displaystyle=100(3D_{V})^{|U_{\tau}\setminus V_{\tau}|+|V_{\tau}\setminus
U_{\tau}|+k|E(\tau)|}2^{|V(\tau)\setminus(U_{\tau}\cup V_{\tau})|}$
$\displaystyle\quad\cdot 2e(6qD_{V})^{|V(\tau)\setminus
U_{\tau}|+|V(\tau)\setminus V_{\tau}|}\prod_{e\in
E(\tau)}(400D_{V}^{2}D_{E}^{2}q)^{l_{e}}\sqrt{n}^{|V(\tau)|-|U_{\tau}|}S(\tau)$
$\displaystyle\leq n^{O(1)\cdot\varepsilon(C_{V}+C_{E})\cdot\sum_{e\in
E(\tau)}l_{e}}\cdot\sqrt{n}^{|V(\tau)|-|U_{\tau}|}S(\tau)$ $\displaystyle\leq
n^{O(1)\cdot\varepsilon(C_{V}+C_{E})\cdot\sum_{e\in
E(\tau)}l_{e}}\cdot\frac{1}{n^{0.5\varepsilon\sum_{e\in E(\tau)}l_{e}}}$
$\displaystyle\leq 1$

We can now prove Lemma 12.1.

See 12.1

###### Proof.

We have

$\displaystyle\begin{bmatrix}\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}&B_{norm}(\tau)H_{\tau}\\\
B_{norm}(\tau)H_{\tau}^{T}&\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}\end{bmatrix}=$
$\displaystyle\begin{bmatrix}\left(\frac{1}{|Aut(U)|c(\tau)}-\frac{S(\tau)B_{norm}(\tau)}{|Aut(U)|}\right)H_{Id_{U}}&0\\\
0&\left(\frac{1}{|Aut(U)|c(\tau)}-\frac{S(\tau)B_{norm}(\tau)}{|Aut(U)|}\right)H_{Id_{U}}\end{bmatrix}$
$\displaystyle+B_{norm}(\tau)\begin{bmatrix}\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}&H_{\tau}\\\
H_{\tau}^{T}&\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}\end{bmatrix}$

By Lemma 5.12, $\begin{bmatrix}\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}&H_{\tau}\\\
H_{\tau}^{T}&\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}\end{bmatrix}\succeq 0$, so the
second term above is positive semidefinite. For the first term, by Lemma 5.10,
$H_{Id_{U}}\succeq 0$ and by Corollary 12.6,
$\frac{1}{|Aut(U)|c(\tau)}-\frac{S(\tau)B_{norm}(\tau)}{|Aut(U)|}\geq 0$,
which proves that the first term is also positive semidefinite.

###  12.2 Proof of Lemma 12.2

######  Lemma 12.7.

Suppose $\lambda\leq n^{\frac{k}{4}-\varepsilon}$. For all
$U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$ and for all
$\gamma\in\Gamma_{U,V}$,

$n^{w(V(\gamma)\setminus
U_{\gamma})}S(\gamma)^{2}\leq\frac{1}{n^{B\varepsilon(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|+\sum_{e\in E(\gamma)}l_{e})}}$

for some constant $B$ that depends only on $C_{\Delta}$. In particular, it is
independent of $C_{V}$ and $C_{E}$.

###### Proof.

Suppose there is a vertex $i\in V(\gamma)\setminus U_{\gamma}\setminus
V_{\gamma}$ such that $deg^{\gamma}(i)$ is odd, then $S(\gamma)=0$ and the
inequality is true. So, assume $deg^{\gamma}(i)$ is even for all vertices
$i\in V(\gamma)\setminus U_{\gamma}\setminus V_{\gamma}$.

We first claim that $k\sum_{e\in E(\gamma)}l_{e}\geq 2|V(\gamma)\setminus
U_{\gamma}|$. Since $\gamma$ is a left shape, all vertices $i$ in
$V(\gamma)\setminus U_{\gamma}$ have $deg^{\gamma}(i)\geq 1$. In particular,
all vertices $i\in V_{\gamma}\setminus U_{\gamma}$ have $deg^{\gamma}(i)\geq
1$. Moreover, if $i\in V(\gamma)\setminus U_{\gamma}\setminus V_{\gamma}$,
since $deg^{\gamma}(i)$ is even, we must have $deg^{\gamma}(i)\geq 2$.

Let $S^{\prime}$ be the set of vertices $i\in U_{\gamma}\setminus V_{\gamma}$
that have $deg^{\gamma}(i)\geq 1$. Then, note that
$|S^{\prime}|+|U_{\gamma}\cap
V_{\gamma}|\geq|V_{\gamma}|\Longrightarrow|S^{\prime}|\geq|V_{\gamma}\setminus
U_{\gamma}|$ since otherwise $S^{\prime}\cup(U_{\gamma}\cap V_{\gamma})$ will
be a vertex separator of $\gamma$ of weight strictly less than $V_{\gamma}$,
which is not possible. Then,

$\displaystyle\sum_{e\in E(\gamma)}kl_{e}$ $\displaystyle=\sum_{i\in
V(\gamma)}deg^{\gamma}(i)$ $\displaystyle\geq\sum_{i\in V(\gamma)\setminus
U_{\gamma}\setminus V_{\gamma}}deg^{\gamma}(i)+\sum_{i\in U_{\gamma}\setminus
V_{\gamma}}deg^{\gamma}(i)+\sum_{i\in V_{\gamma}\setminus
U_{\gamma}}deg^{\gamma}(i)$ $\displaystyle\geq 2|V(\gamma)\setminus
U_{\gamma}\setminus V_{\gamma}|+|S^{\prime}|+|V_{\gamma}\setminus U_{\gamma}|$
$\displaystyle\geq 2|V(\gamma)\setminus U_{\gamma}\setminus
V_{\gamma}|+2|V_{\gamma}\setminus U_{\gamma}|$
$\displaystyle=2|V(\gamma)\setminus U_{\gamma}|$

Finally, note that
$2|V(\gamma)|-|U_{\gamma}|-|V_{\gamma}|=|U_{\gamma}\setminus
V_{\gamma}|+|V_{\gamma}\setminus U_{\gamma}|+2|V(\gamma)\setminus
U_{\gamma}\setminus V_{\gamma}|\geq|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|$. By choosing $C_{\Delta}$ sufficiently small, we have

$\displaystyle n^{w(V(\gamma)\setminus U_{\gamma})}S(\gamma)^{2}$
$\displaystyle=n^{|V(\gamma)\setminus
U_{\gamma})|}\Delta^{2|V(\gamma)|-|U_{\gamma}|-|V_{\gamma}|}\prod_{e\in
E(\gamma)}\left(\frac{\lambda^{2}}{(\Delta n)^{k}}\right)^{l_{e}}$
$\displaystyle\leq n^{|V(\gamma)\setminus
U_{\gamma})|}\Delta^{2|V(\gamma)|-|U_{\gamma}|-|V_{\gamma}|}\prod_{e\in
E(\gamma)}n^{-(\frac{k}{2}+\varepsilon)l_{e}}$
$\displaystyle\leq\Delta^{2|V(\gamma)|-|U_{\gamma}|-|V_{\gamma}|}\prod_{e\in
E(\gamma)}n^{-\varepsilon l_{e}}$
$\displaystyle\leq\frac{1}{n^{B\varepsilon(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|+\sum_{e\in E(\gamma)}l_{e})}}$

for a constant $B$ that depends only on $C_{\Delta}$.

######  Remark 12.8.

In the above bounds, note that there is a decay of $n^{B\varepsilon}$ for each
vertex in $V(\gamma)\setminus(U_{\gamma}\cap V_{\gamma})$. One of the main
technical reasons for introducing the slack parameter $C_{\Delta}$ in the
planted distribution was to introduce this decay, which is needed in the
current machinery.

We can now prove Lemma 12.2.

See 12.2

###### Proof.

By Lemma 5.14, we have

$\displaystyle
c(\gamma)^{2}N(\gamma)^{2}B(\gamma)^{2}H_{Id_{V}}^{-\gamma,\gamma}$
$\displaystyle\preceq
c(\gamma)^{2}N(\gamma)^{2}B(\gamma)^{2}S(\gamma)^{2}\frac{|Aut(U)|}{|Aut(V)|}H^{\prime}_{\gamma}$

Using the same proof as in Lemma 5.10, we can see that
$H^{\prime}_{\gamma}\succeq 0$. Therefore, it suffices to prove that

$c(\gamma)^{2}N(\gamma)^{2}B(\gamma)^{2}S(\gamma)^{2}\frac{|Aut(U)|}{|Aut(V)|}\leq
1$

Since $U,V\in{\mathcal{I}}_{mid}$, $|Aut(U)|=|U|!,|Aut(V)|=|V|!$. Therefore,
$\frac{|Aut(U)|}{|Aut(V)|}=\frac{|U|!}{|V|!}\leq D_{V}^{|U_{\gamma}\setminus
V_{\gamma}|}$. Also, $|E(\gamma)|\leq\sum_{e\in E(\gamma)}l_{e}$ and
$q=n^{O(1)\cdot\varepsilon(C_{V}+C_{E})}$. Let $B$ be the constant from Lemma
12.7. We can set $C_{V},C_{E}$ sufficiently small so that, using Lemma 12.7,

$\displaystyle
c(\gamma)^{2}N(\gamma)^{2}B(\gamma)^{2}S(\gamma)^{2}\frac{|Aut(U)|}{|Aut(V)|}$
$\displaystyle\leq 100^{2}(3D_{V})^{2|U_{\gamma}\setminus
V_{\gamma}|+2|V_{\gamma}\setminus
U_{\gamma}|+2k|E(\alpha)|}4^{|V(\gamma)\setminus(U_{\gamma}\cup V_{\gamma})|}$
$\displaystyle\quad\cdot(3D_{V})^{4|V(\gamma)\setminus
V_{\gamma}|+2|V(\gamma)\setminus U_{\gamma}|}(6qD_{V})^{2|V(\gamma)\setminus
U_{\gamma}|+2|V(\gamma)\setminus V_{\gamma}|}\prod_{e\in
E(\gamma)}(400D_{V}^{2}D_{E}^{2}q)^{2l_{e}}$ $\displaystyle\quad\cdot
n^{w(V(\gamma)\setminus U_{\gamma})}S(\gamma)^{2}\cdot
D_{V}^{|U_{\gamma}\setminus V_{\gamma}|}$ $\displaystyle\leq
n^{O(1)\cdot\varepsilon(C_{V}+C_{E})\cdot(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|+\sum_{e\in E(\gamma)}l_{e})}\cdot n^{w(V(\gamma)\setminus
U_{\gamma})}S(\gamma)^{2}$ $\displaystyle\leq
n^{O(1)\cdot\varepsilon(C_{V}+C_{E})\cdot(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|+\sum_{e\in
E(\gamma)}l_{e})}\cdot\frac{1}{n^{B\varepsilon(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|+\sum_{e\in E(\gamma)}l_{e})}}$ $\displaystyle\leq 1$

###  12.3 Proof of Lemma 12.3

In this section, we will prove Lemma 12.3 using the strategy sketched in
Section 10.

See 12.3

In particular, we prove the following lemmas.

######  Lemma 12.9.

Whenever $\left\lVert M_{\alpha}\right\rVert\leq B_{norm}(\alpha)$ for all
$\alpha\in{\mathcal{M}}^{\prime}$,

$\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}{(H_{Id_{U}})}}\succeq\frac{\Delta^{2D_{sos}^{2}}}{n^{D_{sos}}}Id_{sym}$

######  Lemma 12.10.

$\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\gamma\in\Gamma_{U,*}}\frac{d_{Id_{U}}(H_{Id_{U}},H^{\prime}_{\gamma})}{|Aut(U)|c(\gamma)}\leq\frac{1}{\Delta^{2D_{sos}}2^{D_{V}}}$

Assuming these, we can conclude the following.

See 12.3

###### Proof.

We choose $C_{sos}$ sufficiently small so that
$\frac{\Delta^{2D_{sos}^{2}}}{n^{D_{sos}}}\geq\frac{6}{\Delta^{2D_{sos}}2^{D_{V}}}$
which is satisfied by setting $C_{sos}<0.5C_{V}$. Then, since $Id_{Sym}\succeq
0$, using Lemma 12.9 and Lemma 12.10,

$\displaystyle\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}{(H_{Id_{U}})}}$
$\displaystyle\succeq\frac{\Delta^{2D_{sos}^{2}}}{n^{D_{sos}}}Id_{sym}$
$\displaystyle\succeq\frac{6}{\Delta^{2D_{sos}}2^{D_{V}}}Id_{sym}$
$\displaystyle\succeq
6\left(\sum_{U\in\mathcal{I}_{mid}}{\sum_{\gamma\in\Gamma_{U,*}}{\frac{d_{Id_{U}}(H^{\prime}_{\gamma},H_{Id_{U}})}{|Aut(U)|c(\gamma)}}}\right)Id_{sym}$

The rest of the section is devoted to proving Lemma 12.9 and Lemma 12.10.

In the proofs of both these lemmas, we will need a bound on
$B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{U}}(\sigma,\sigma^{\prime})$
that is obtained below.

######  Lemma 12.11.

Suppose $\lambda=n^{\frac{k}{4}-\varepsilon}$. For all
$U\in{\mathcal{I}}_{mid}$ and $\sigma,\sigma^{\prime}\in{\mathcal{L}}_{U}$,

$B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{U}}(\sigma,\sigma^{\prime})\leq\frac{1}{n^{0.5\varepsilon
C_{\Delta}|V(\sigma\circ\sigma^{\prime})|}\Delta^{D_{sos}}n^{|U|}}$

###### Proof.

Suppose there is a vertex $i\in V(\sigma)\setminus V_{\sigma}$ such that
$deg^{\sigma}(i)+deg^{U_{\sigma}}(i)$ is odd, then
$H_{Id_{U}}(\sigma,\sigma^{\prime})=0$ and the inequality is true. So, assume
that $deg^{\sigma}(i)+deg^{U_{\sigma}}(i)$ is even for all $i\in
V(\sigma)\setminus V_{\sigma}$. Similarly, assume that
$deg^{\sigma^{\prime}}(i)+deg^{U_{\sigma^{\prime}}}(i)$ is even for all $i\in
V(\sigma^{\prime})\setminus V_{\sigma^{\prime}}$. Also, if
$\rho_{\sigma}\neq\rho_{\sigma^{\prime}}$, we will have
$H_{Id_{U}}(\sigma,\sigma^{\prime})=0$ and we’d be done. So, assume
$\rho_{\sigma}=\rho_{\sigma^{\prime}}$.

Let $\alpha=\sigma\circ\sigma^{\prime}$. We will first prove that $\sum_{e\in
E(\alpha)}kl_{e}+2deg(\alpha)\geq 2|V(\alpha)|+2|U|$. Firstly, note that all
vertices $i\in V(\alpha)\setminus(U_{\alpha}\cup V_{\alpha})$ have
$deg^{\alpha}(i)$ to be even and nonzero, and hence at least $2$. Moreover, in
both the sets $U_{\alpha}\setminus(U_{\alpha}\cap V_{\alpha})$ and
$V_{\alpha}\setminus(U_{\alpha}\cap V_{\alpha})$, there are at least
$|U|-|U_{\alpha}\cap V_{\alpha}|$ vertices of degree at least $1$, because $U$
is a minimum vertex separator. Also, note that
$deg(\alpha)\geq|U_{\alpha}|+|V_{\alpha}|$. This implies that

$\displaystyle\sum_{e\in E(\alpha)}kl_{e}+2deg(\alpha)$ $\displaystyle\geq
2|V(\alpha)\setminus(U_{\alpha}\cup V_{\alpha})|+2(|U|-|U_{\alpha}\cap
V_{\alpha}|)+2(|U_{\alpha}|+|V_{\alpha}|)$
$\displaystyle=2(|V(\alpha)|-|U_{\alpha}\cup
V_{\alpha}|)+2(|U|-|U_{\alpha}\cap V_{\alpha}|)+2(|U_{\alpha}\cup
V_{\alpha}|+|U_{\alpha}\cap V_{\alpha}|)$ $\displaystyle=2|V(\alpha)|+2|U|$

where we used the fact that $U_{\alpha}\cap V_{\alpha}\subseteq U$. Finally,
by choosing $C_{V},C_{E}$ sufficiently small,

$\displaystyle
B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{U}}(\sigma,\sigma^{\prime})$
$\displaystyle=2e(6qD_{V})^{|V(\sigma)\setminus
U_{\sigma}|+|V(\sigma)\setminus V_{\sigma}|}\prod_{e\in
E(\sigma)}(400D_{V}^{2}D_{E}^{2}q)^{l_{e}}n^{\frac{w(V(\sigma))-w(U)}{2}}$
$\displaystyle\quad\cdot 2e(6qD_{V})^{|V(\sigma^{\prime})\setminus
U_{\sigma^{\prime}}|+|V(\sigma^{\prime})\setminus
V_{\sigma^{\prime}}|}\prod_{e\in
E(\sigma^{\prime})}(400D_{V}^{2}D_{E}^{2}q)^{l_{e}}n^{\frac{w(V(\sigma^{\prime}))-w(U)}{2}}$
$\displaystyle\quad\cdot\frac{1}{|Aut(U)|}\Delta^{|V(\alpha)|}\left(\frac{1}{\sqrt{\Delta
n}}\right)^{deg(\alpha)}\prod_{e\in E(\alpha)}\left(\frac{\lambda}{(\Delta
n)^{\frac{k}{2}}}\right)^{l_{e}}$ $\displaystyle\leq
n^{O(1)\cdot\varepsilon(C_{V}+C_{E})\cdot(|V(\alpha)|+\sum_{e\in
E(\alpha)}l_{e})}\Delta^{|V(\alpha)|}\left(\frac{1}{\sqrt{\Delta}}\right)^{deg(\alpha)}$
$\displaystyle\quad\cdot\sqrt{n}^{|V(\alpha)|-|U|}\left(\frac{1}{\sqrt{n}}\right)^{deg(\alpha)}\prod_{e\in
E(\alpha)}n^{(-\frac{k}{4}-0.5\varepsilon)l_{e}}$
$\displaystyle\leq\frac{n^{O(1)\cdot\varepsilon(C_{V}+C_{E})\cdot(|V(\alpha)|+\sum_{e\in
E(\alpha)}l_{e})}}{n^{\varepsilon
C_{\Delta}|V(\alpha)|}n^{0.5\varepsilon\sum_{e\in
E(\alpha)}l_{e}}}\cdot\frac{1}{\Delta^{D_{sos}}n^{|U|}}\sqrt{n}^{|V(\alpha)|+|U|-deg(\alpha)-\frac{1}{2}\sum_{e\in
E(\alpha)}kl_{e}}$ $\displaystyle\leq\frac{1}{n^{0.5\varepsilon
C_{\Delta}|V(\alpha)|}\Delta^{D_{sos}}n^{|U|}}$

where we used the facts $\Delta\leq 1,deg(\alpha)\leq 2D_{sos}$.

####  12.3.1 Proof of Lemma 12.9

To prove Lemma 12.9, we will use the strategy from Section 10.1. We will also
use the notation from that section. We recall that for
$U\in{\mathcal{I}}_{mid}$,
${\mathcal{L}}_{U}^{\prime}\subset{\mathcal{L}}_{U}$ was the set of non-
trivial shapes in ${\mathcal{L}}_{U}$.

######  Proposition 12.12.

For $V\in{\mathcal{I}}_{mid}$, $\lambda_{V}=\frac{1}{n^{|V|}}$.

###### Proof.

We have
$\lambda_{V}=|Aut(V)|H_{Id_{V}}(Id_{V},Id_{V})=\Delta^{|V|}\left(\frac{1}{\sqrt{\Delta
n}}\right)^{2|V|}=\frac{1}{n^{|V|}}$.

######  Lemma 12.13.

For any edge $e=(V,U)$ in $G$, we have

$w(e)\leq\frac{1}{n^{0.1C_{\Delta}\varepsilon|U|}\Delta^{2D_{sos}}}$

###### Proof.

Let $e=(V,U)$ be an edge in $G$. Then, $w(U)>w(V)$ and
$w(e)=\frac{2W(U,V)}{\lambda_{V}}$. Using Lemma 12.11, we have

$\displaystyle 2W(U,V)$
$\displaystyle=\frac{2}{|Aut(U)|}\sum_{\sigma\in{\mathcal{L}}_{V},U_{\sigma}=U}\sum_{\sigma^{\prime}\in{\mathcal{L}}_{V},U_{\sigma^{\prime}}\neq
V}B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{U}}(\sigma,\sigma^{\prime})$
$\displaystyle\leq\frac{2}{|Aut(U)|}\sum_{\sigma\in{\mathcal{L}}_{V},U_{\sigma}=U}\sum_{\sigma^{\prime}\in{\mathcal{L}}_{V},U_{\sigma^{\prime}}\neq
V}\frac{1}{n^{0.5\varepsilon
C_{\Delta}|V(\sigma\circ\sigma^{\prime})|}\Delta^{D_{sos}}n^{|V|}}$
$\displaystyle\leq\sum_{\sigma,\sigma^{\prime}\in{\mathcal{L}}_{V}^{\prime}}\frac{2}{n^{0.5\varepsilon
C_{\Delta}|V(\sigma\circ\sigma^{\prime})|}\Delta^{D_{sos}}n^{|V|}}$
$\displaystyle\leq\sum_{\sigma,\sigma^{\prime}\in{\mathcal{L}}_{V}^{\prime}}\frac{1}{n^{0.1C_{\Delta}\varepsilon|V(\sigma\circ\sigma^{\prime})|}D_{sos}^{D_{sos}}n^{F\varepsilon|V(\sigma\circ\sigma^{\prime})|}\Delta^{2D_{sos}}n^{|V|}}$
$\displaystyle\leq\frac{1}{n^{0.1C_{\Delta}\varepsilon|U|}\Delta^{2D_{sos}}n^{|V|}}\sum_{\sigma,\sigma^{\prime}\in{\mathcal{L}}_{V}^{\prime}}\frac{1}{D_{sos}^{D_{sos}}n^{F\varepsilon|V(\sigma\circ\sigma^{\prime})|}}$
$\displaystyle\leq\frac{1}{n^{0.1C_{\Delta}\varepsilon|U|}\Delta^{2D_{sos}}n^{|V|}}$
$\displaystyle=\frac{\lambda_{V}}{n^{0.1\varepsilon
C_{\Delta}|U|}\Delta^{2D_{sos}}}$

where we set $C_{V},C_{E}$ small enough so that $0.4C_{\Delta}\geq F$ and
invoked Lemma 10.16. This proves the lemma.

######  Corollary 12.14.

For any $U,V\in{\mathcal{I}}_{mid}$ such that $w(U)>w(V)$,

$\displaystyle\sum_{P:P\text{ is a path from V to U in G}}\prod_{e\in
E(P)}w(e)\leq\frac{1}{2D_{sos}}$

###### Proof.

The total number of vertices in $G$ is at most $D_{sos}+1$ since each
$U\in{\mathcal{I}}_{mid}$ has at most $D_{sos}$ vertices. Therefore, for any
fixed integer $j\geq 1$, the number of paths from $V$ to $U$ of length $j$ is
at most $(D_{sos}+1)^{j}$. Take any path $P$ from $V$ to $U$. Suppose it has
length $j\geq 1$. Note that for all edges $e=(V^{\prime},U^{\prime})$ in
$E(P)$, since $|U^{\prime}|\geq 1$, we have

$w(e)\leq\frac{1}{n^{0.1C_{\Delta}\varepsilon|U^{\prime}|}\Delta^{2D_{sos}}}\leq\frac{1}{n^{0.1C_{\Delta}\varepsilon}\Delta^{2D_{sos}}}$

So, $\prod_{e\in
E(P)}w(e)\leq\left(\frac{1}{n^{0.1C_{\Delta}\varepsilon}\Delta^{2D_{sos}}}\right)^{j}$.
Therefore, by setting $C_{sos}$ small enough,

$\displaystyle\sum_{P:P\text{ is a path from V to U in G}}\prod_{e\in
E(P)}w(e)$
$\displaystyle\leq\sum_{j=1}^{D_{sos}}(D_{sos}+1)^{j}\left(\frac{1}{n^{0.1C_{\Delta}\varepsilon}\Delta^{2D_{sos}}}\right)^{j}$
$\displaystyle\leq\frac{1}{2D_{sos}\Delta^{2D_{sos}^{2}}}$

We can now prove Lemma 12.9.

See 12.9

###### Proof.

For all $V\in{\mathcal{I}}_{mid}$, we have

$\displaystyle Id_{Sym,V}\preceq 2\sum_{U\in\mathcal{I}_{mid}:w(U)\geq
w(V)}{\left(\sum_{P:P\text{ is a path from V to U in }G}{\prod_{e\in
E(P)}{w(e)}}\right)\frac{1}{{\lambda_{U}}}M^{fact}(H_{Id_{U}})}$

Summing this over all $V\in{\mathcal{I}}_{mid}$, we get

$\displaystyle Id_{Sym}$
$\displaystyle\preceq\sum_{U\in{\mathcal{I}}_{mid}}\frac{2}{\lambda_{U}}\left(\sum_{V\in{\mathcal{I}}_{mid}:w(U)\geq
w(V)}\sum_{P:P\text{ is a path from V to U in G}}\prod_{e\in
E(P)}w(e)\right)M^{fact}(H_{Id_{U}})$
$\displaystyle\preceq\sum_{U\in{\mathcal{I}}_{mid}}\frac{2}{\lambda_{U}}\left(\sum_{V\in{\mathcal{I}}_{mid}:w(U)\geq
w(V)}\frac{1}{2D_{sos}\Delta^{2D_{sos}^{2}}}\right)M^{fact}(H_{Id_{U}})$

For any fixed $U\in{\mathcal{I}}_{mid}$, the number of
$V\in{\mathcal{I}}_{mid}$ such that $w(U)\geq w(V)$ is at most $D_{sos}$.
Therefore,

$\displaystyle Id_{Sym}$
$\displaystyle\preceq\sum_{U\in{\mathcal{I}}_{mid}}\frac{1}{\lambda_{U}\Delta^{2D_{sos}^{2}}}M^{fact}(H_{Id_{U}})$
$\displaystyle=\sum_{U\in{\mathcal{I}}_{mid}}\frac{1}{\Delta^{2D_{sos}^{2}}}n^{|U|}M^{fact}(H_{Id_{U}})$
$\displaystyle\preceq\sum_{U\in{\mathcal{I}}_{mid}}\frac{1}{\Delta^{2D_{sos}^{2}}}n^{D_{sos}}M^{fact}(H_{Id_{U}})$

where we used the fact that for all $U\in{\mathcal{I}}_{mid}$, we have
$|U|\leq D_{sos}$ and $M^{fact}(H_{Id_{U}})\succeq 0$.

####  12.3.2 Proof of Lemma 12.10

We restate the lemma for convenience.

See 12.10

###### Proof.

We have

$\displaystyle\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\gamma\in\Gamma_{U,*}}\frac{d_{Id_{U}}(H_{Id_{U}},H^{\prime}_{\gamma})}{|Aut(U)|c(\gamma)}=\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\gamma\in\Gamma_{U,*}}\frac{1}{|Aut(U)|c(\gamma)}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}_{U_{\gamma}}:|V(\sigma)|\leq
D_{V},|V(\sigma^{\prime})|\leq D_{V},\atop|V(\sigma\circ\gamma)|>D_{V}\text{
or
}|V(\sigma^{\prime}\circ\gamma)|>D_{V}}{B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{U_{\gamma}}}(\sigma,\sigma^{\prime})}$

The set of $\sigma,\sigma^{\prime}$ that could appear in the above sum must
necessarily be non-trivial and hence,
$\sigma,\sigma^{\prime}\in{\mathcal{L}}_{U}^{\prime}$. Then,

$\displaystyle\sum_{U\in{\mathcal{I}}_{mid}}$
$\displaystyle\sum_{\gamma\in\Gamma_{U,*}}\frac{d_{Id_{U}}(H_{Id_{U}},H^{\prime}_{\gamma})}{|Aut(U)|c(\gamma)}$
$\displaystyle=\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}{B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{U}}(\sigma,\sigma^{\prime})}\sum_{\gamma\in\Gamma_{U,*}:|V(\sigma\circ\gamma)|>D_{V}\text{
or }|V(\sigma^{\prime}\circ\gamma)|>D_{V}}\frac{1}{|Aut(U)|c(\gamma)}$

For $\sigma\in{\mathcal{L}}^{\prime}_{U}$, define
$m_{\sigma}=D_{V}+1-|V(\sigma)|\geq 1$. This is precisely set so that for all
$\gamma\in\Gamma_{U,*}$, we have $|V(\sigma\circ\gamma)|>D_{V}$ if and only if
$|V(\gamma)|\geq|U|+m_{\sigma}$. So, for
$\sigma,\sigma^{\prime}\in{\mathcal{L}}^{\prime}_{U}$, using Lemma 9.31

$\displaystyle\sum_{\gamma\in\Gamma_{U,*}:|V(\sigma\circ\gamma)|>D_{V}\text{
or }|V(\sigma^{\prime}\circ\gamma)|>D_{V}}\frac{1}{|Aut(U)|c(\gamma)}$
$\displaystyle=\sum_{\gamma\in\Gamma_{U,*}:|V(\gamma)|\geq|U|+\min(m_{\sigma},m_{\sigma^{\prime}})}\frac{1}{|Aut(U)|c(\gamma)}$
$\displaystyle\leq\frac{1}{2^{\min(m_{\sigma},m_{\sigma^{\prime}})-1}}$

Also, for $\sigma,\sigma^{\prime}\in{\mathcal{L}}_{U}^{\prime}$, we have
$|V(\sigma\circ\sigma^{\prime})|+min(m_{\sigma},m_{\sigma^{\prime}})-1\geq
D_{V}$. Therefore,

$\displaystyle\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\gamma\in\Gamma_{U,*}}\frac{d_{Id_{U}}(H_{Id_{U}},H^{\prime}_{\gamma})}{|Aut(U)|c(\gamma)}$
$\displaystyle\leq\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}{B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{U}}(\sigma,\sigma^{\prime})\frac{1}{2^{\min(m_{\sigma},m_{\sigma^{\prime}})-1}}}$
$\displaystyle\leq\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}\frac{1}{n^{0.5\varepsilon
C_{\Delta}|V(\sigma\circ\sigma^{\prime})|}\Delta^{D_{sos}}n^{|U|}2^{\min(m_{\sigma},m_{\sigma^{\prime}})-1}}$
$\displaystyle\leq\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}\frac{1}{n^{0.5\varepsilon
C_{\Delta}|V(\sigma\circ\sigma^{\prime})|}\Delta^{D_{sos}}2^{\min(m_{\sigma},m_{\sigma^{\prime}})-1}}$

where we used Lemma 12.11. Using
$n^{0.5C_{\Delta}|V(\sigma\circ\sigma^{\prime})|}\geq n^{0.1\varepsilon
C_{\Delta}|V(\sigma\circ\sigma^{\prime})|}2^{|V(\sigma\circ\sigma^{\prime})|}$,

$\displaystyle\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\gamma\in\Gamma_{U,*}}\frac{d_{Id_{U}}(H_{Id_{U}},H^{\prime}_{\gamma})}{|Aut(U)|c(\gamma)}$
$\displaystyle\leq\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}\frac{1}{n^{0.1\varepsilon
C_{\Delta}|V(\sigma\circ\sigma^{\prime})|}\Delta^{D_{sos}}2^{|V(\sigma\circ\sigma^{\prime})|}2^{\min(m_{\sigma},m_{\sigma^{\prime}})-1}}$
$\displaystyle\leq\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}\frac{1}{n^{0.1\varepsilon
C_{\Delta}|V(\sigma\circ\sigma^{\prime})|}\Delta^{D_{sos}}2^{D_{V}}}$
$\displaystyle\leq\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}\frac{1}{D_{sos}^{D_{sos}}n^{0.1\varepsilon
C_{\Delta}|V(\sigma\circ\sigma^{\prime})|}\Delta^{2D_{sos}}2^{D_{V}}}$

where we set $C_{sos}$ small enough so that $D_{sos}=n^{\varepsilon
C_{sos}}\leq n^{c\varepsilon C_{\Delta}}=\frac{1}{\Delta}$. The final step
will be to argue that
$\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}\frac{1}{D_{sos}^{D_{sos}}n^{0.1C_{\Delta}\varepsilon|V(\sigma\circ\sigma^{\prime})|}}\leq
1$ which will complete the proof. But this will follow from Lemma 10.16 if we
set $C_{V},C_{E}$ small enough.

##  13 Sparse PCA: Full verification

In this section, we will prove all the bounds required to prove Theorem 1.5.

See 1.5

In particular, we will use Theorem 7.101 where we choose $\varepsilon$ in the
theorem, not to be confused with the $\varepsilon$ in Theorem 1.5, to be an
arbitrarily small constant.

######  Definition 13.1.

Define $n=\max(d,m)$.

######  Remark 13.2.

The above definition conforms with the notation used in Theorem 7.101. So, we
can use the bounds as stated there.

######  Lemma 13.3.

For all $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$,

$\begin{bmatrix}\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}&B_{norm}(\tau)H_{\tau}\\\
B_{norm}(\tau)H_{\tau}^{T}&\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}\end{bmatrix}\succeq
0$

######  Lemma 13.4.

For all $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$ and all
$\gamma\in\Gamma_{U,V}$,

$c(\gamma)^{2}N(\gamma)^{2}B(\gamma)^{2}H_{Id_{V}}^{-\gamma,\gamma}\preceq
H_{\gamma}^{\prime}$

######  Lemma 13.5.

Whenever $\left\lVert M_{\alpha}\right\rVert\leq B_{norm}(\alpha)$ for all
$\alpha\in\mathcal{M}^{\prime}$,

$\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}{(H_{Id_{U}})}}\succeq
6\left(\sum_{U\in\mathcal{I}_{mid}}{\sum_{\gamma\in\Gamma_{U,*}}{\frac{d_{Id_{U}}(H^{\prime}_{\gamma},H_{Id_{U}})}{|Aut(U)|c(\gamma)}}}\right)Id_{sym}$

######  Corollary 13.6.

With high probability, $\Lambda\succeq 0$.

###### Proof.

This follows by invoking Theorem 7.101 whose conditions follow from Lemma
6.11, Lemma 13.3, Lemma 13.4, and Lemma 13.5.

###  13.1 Proof of Lemma 13.3

######  Lemma 13.7.

Suppose $0<A<\frac{1}{4}$ is a constant such that
$\frac{\sqrt{\lambda}}{\sqrt{k}}\leq d^{-A\varepsilon}$ and
$\frac{1}{\sqrt{k}}\leq d^{-2A}$. For all $m$ such that
$m\leq\frac{d^{1-\varepsilon}}{\lambda^{2}},m\leq\frac{k^{2-\varepsilon}}{\lambda^{2}}$,
for all $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$, suppose
$deg^{\tau}(i)$ is even for all $i\in V(\tau)\setminus U_{\tau}\setminus
V_{\tau}$, then

$\sqrt{d}^{|\tau|_{1}-|U_{\tau}|_{1}}\sqrt{m}^{|\tau|_{2}-|U_{\tau}|_{2}}S(\tau)\leq\prod_{j\in
V_{2}(\tau)\setminus U_{\tau}\setminus
V_{\tau}}(deg^{\tau}(j)-1)!!\cdot\frac{1}{d^{A\varepsilon\sum_{e\in
E(\tau)}l_{e}}}$

###### Proof.

Let $r_{1}=|\tau|_{1}-|U_{\tau}|_{1},r_{2}=|\tau|_{2}-|U_{\tau}|_{2}$. Since
$\Delta\leq 1$, it suffices to prove

$E:=\sqrt{d}^{r_{1}}\sqrt{m}^{r_{2}}\left(\frac{k}{d}\right)^{r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{\sum_{e\in
E(\tau)}l_{e}}\leq\frac{1}{d^{A\varepsilon\sum_{e\in E(\tau)}l_{e}}}$

We will need the following claim.

######  Claim 13.8.

$\sum_{e\in E(\tau)}l_{e}\geq 2\max(r_{1},r_{2})$.

###### Proof.

We will first prove $\sum_{e\in E(\tau)}l_{e}\geq 2r_{1}$. For any vertex
$i\in V_{1}(\tau)\setminus U_{\tau}\setminus V_{\tau}$, $deg^{\tau}(i)$ is
even and is not $0$, hence, $deg^{\tau}(i)\geq 2$. Any vertex $i\in
U_{\tau}\setminus V_{\tau}$ cannot have $deg^{\tau}(i)=0$ otherwise
$U_{\tau}\setminus\\{i\\}$ is a vertex separator of strictly smaller weight
than $U_{\tau}$, which is not possible, hence, $deg^{\tau}(i)\geq 1$.
Similarly, for $i\in V_{\tau}\setminus U_{\tau}$, $deg^{\tau}(i)\geq 1$. Also,
since $H_{\tau}$ is bipartite, we have $\sum_{i\in
V_{1}(\tau)}deg^{\tau}(i)=\sum_{j\in V_{2}(\tau)}deg^{\tau}(j)=\sum_{e\in
E(\tau)}l_{e}$. Consider

$\displaystyle\sum_{e\in E(\tau)}l_{e}$ $\displaystyle=\sum_{i\in
V_{1}(\tau)}deg^{\tau}(i)$ $\displaystyle\geq\sum_{i\in V_{1}(\tau)\setminus
U_{\tau}\setminus V_{\tau}}deg^{\tau}(i)+\sum_{i\in(U_{\tau})_{1}\setminus
V_{\tau}}deg^{\tau}(i)+\sum_{i\in(V_{\tau})_{1}\setminus
U_{\tau}}deg^{\tau}(i)$ $\displaystyle\geq 2|V_{1}(\tau)\setminus
U_{\tau}\setminus V_{\tau}|+|(U_{\tau})_{1}\setminus
V_{\tau}|+|(V_{\tau})_{1}\setminus U_{\tau}|$ $\displaystyle=2r_{1}$

We can similarly prove $\sum_{e\in E(\tau)}l_{e}\geq 2r_{2}$

To illustrate the main idea, we will start by proving the weaker bound $E\leq
1$. Observe that our assumptions imply
$m\leq\frac{d}{\lambda^{2}},m\leq\frac{k^{2}}{\lambda^{2}}$ and also,
$E\leq\sqrt{d}^{r_{1}}\sqrt{m}^{r_{2}}\left(\frac{k}{d}\right)^{r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{2\max(r_{1},r_{2})}$
where we used the fact that $\frac{\sqrt{\lambda}}{\sqrt{k}}\leq
d^{-A\varepsilon}\leq 1$.

######  Claim 13.9.

For integers $r_{1},r_{2}\geq 0$, if $m\leq\frac{d}{\lambda^{2}}$ and
$m\leq\frac{k^{2}}{\lambda^{2}}$, then,

$\sqrt{d}^{r_{1}}\sqrt{m}^{r_{2}}\left(\frac{k}{d}\right)^{r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{2\max(r_{1},r_{2})}\leq
1$

###### Proof.

We will consider the cases $r_{1}\geq r_{2}$ and $r_{1}<r_{2}$ separately. If
$r_{1}\geq r_{2}$, we have

$\displaystyle\sqrt{d}^{r_{1}}\sqrt{m}^{r_{2}}\left(\frac{k}{d}\right)^{r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{2r_{1}}$
$\displaystyle\leq\sqrt{d}^{r_{1}}\left(\frac{\sqrt{d}}{\lambda}\right)^{r_{2}}\left(\frac{k}{d}\right)^{r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{2r_{1}}$
$\displaystyle=\left(\frac{\lambda}{\sqrt{d}}\right)^{r_{1}-r_{2}}$
$\displaystyle\leq\left(\frac{1}{\sqrt{m}}\right)^{r_{1}-r_{2}}$
$\displaystyle\leq 1$

And if $r_{1}<r_{2}$, we have

$\displaystyle\sqrt{d}^{r_{1}}\sqrt{m}^{r_{2}}\left(\frac{k}{d}\right)^{r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{2r_{2}}$
$\displaystyle=\sqrt{d}^{r_{1}}\sqrt{m}^{r_{2}-r_{1}}\sqrt{m}^{r_{1}}\left(\frac{k}{d}\right)^{r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{2r_{2}}$
$\displaystyle\leq\sqrt{d}^{r_{1}}\left(\frac{k}{\lambda}\right)^{r_{2}-r_{1}}\left(\frac{\sqrt{d}}{\lambda}\right)^{r_{1}}\left(\frac{k}{d}\right)^{r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{2r_{2}}$
$\displaystyle=1$

For the desired bounds, we mimic this argument while carefully keeping track
of factors of $d^{\varepsilon}$.

######  Claim 13.10.

For integers $r_{1},r_{2}\geq 0$ and an integer $r\geq 2\max(r_{1},r_{2})$, if
$m\leq\frac{d^{1-\varepsilon}}{\lambda^{2}}$ and
$m\leq\frac{k^{2-\varepsilon}}{\lambda^{2}}$, then,

$\sqrt{d}^{r_{1}}\sqrt{m}^{r_{2}}\left(\frac{k}{d}\right)^{r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{r}\leq\left(\frac{1}{d^{A\varepsilon}}\right)^{r}$

###### Proof.

If $r_{1}\geq r_{2}$,

$\displaystyle E$
$\displaystyle=\sqrt{d}^{r_{1}}\sqrt{m}^{r_{2}}\left(\frac{k}{d}\right)^{r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{2r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{r-2r_{1}}$
$\displaystyle\leq\sqrt{d}^{r_{1}}\left(\frac{\sqrt{d}^{1-\varepsilon}}{\lambda}\right)^{r_{2}}\left(\frac{k}{d}\right)^{r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{2r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{r-2r_{1}}$
$\displaystyle=\left(\frac{\lambda}{\sqrt{d}^{1-\varepsilon}}\right)^{r_{1}-r_{2}}\left(\frac{1}{\sqrt{d}}\right)^{\varepsilon
r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{r-2r_{1}}$
$\displaystyle\leq\left(\frac{1}{\sqrt{m}}\right)^{r_{1}-r_{2}}\left(\frac{1}{\sqrt{d}}\right)^{\varepsilon
r_{1}}\left(\frac{1}{d^{A\varepsilon}}\right)^{r-2r_{1}}$
$\displaystyle\leq\left(\frac{1}{d^{2A}}\right)^{\varepsilon
r_{1}}\left(\frac{1}{d^{A\varepsilon}}\right)^{r-2r_{1}}$
$\displaystyle=\left(\frac{1}{d^{A\varepsilon}}\right)^{r}$

And if $r_{1}<r_{2}$,

$\displaystyle E$
$\displaystyle=\sqrt{d}^{r_{1}}\sqrt{m}^{r_{2}-r_{1}}\sqrt{m}^{r_{1}}\left(\frac{k}{d}\right)^{r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{2r_{2}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{r-2r_{2}}$
$\displaystyle\leq\sqrt{d}^{r_{1}}\left(\frac{\sqrt{k}^{2-\varepsilon}}{\lambda}\right)^{r_{2}-r_{1}}\left(\frac{\sqrt{d}^{1-\varepsilon}}{\lambda}\right)^{r_{1}}\left(\frac{k}{d}\right)^{r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{2r_{2}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{r-2r_{2}}$
$\displaystyle=\left(\frac{\sqrt{k}}{\sqrt{d}}\right)^{\varepsilon
r_{1}}\left(\frac{1}{\sqrt{k}}\right)^{\varepsilon
r_{2}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{r-2r_{2}}$
$\displaystyle\leq\left(\frac{1}{\sqrt{k}}\right)^{\varepsilon
r_{2}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{r-2r_{2}}$
$\displaystyle\leq\left(\frac{1}{d^{2A}}\right)^{\varepsilon
r_{2}}\left(\frac{1}{d^{A\varepsilon}}\right)^{r-2r_{2}}$
$\displaystyle\leq\left(\frac{1}{d^{A\varepsilon}}\right)^{\sum_{e\in
E(\tau)}l_{e}}$

The result follows by setting $r=\sum_{e\in E(\tau)}l_{e}$ in the above claim.

######  Corollary 13.11.

For all $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$, we have

$c(\tau)B_{norm}(\tau)S(\tau)R(\tau)\leq 1$

###### Proof.

First, note that if $deg^{\tau}(i)$ is odd for any vertex $i\in
V(\tau)\setminus U_{\tau}\setminus V_{\tau}$, then $S(\tau)=0$ and the
inequality is true. So, assume that $deg^{\tau}(i)$ is even for all $i\in
V(\tau)\setminus U_{\tau}\setminus V_{\tau}$.

Since $\tau$ is a proper middle shape, we have $w(I_{\tau})=0$ and
$w(S_{\tau,min})=w(U_{\tau})$. This implies

$n^{\frac{w(V(\tau))+w(I_{\tau})-w(S_{\tau,min})}{2}}=\sqrt{d}^{|\tau|_{1}-|U_{\tau}|_{1}}\sqrt{m}^{|\tau|_{2}-|U_{\tau}|_{2}}$

As was observed in the proof of Lemma 13.7, every vertex $i\in
V(\tau)\setminus U_{\tau}$ or $i\in V(\tau)\setminus V_{\tau}$ has
$deg^{\tau}(i)\geq 1$ and hence, $|V(\tau)\setminus
U_{\tau}|+|V(\tau)\setminus V_{\tau}|\leq 4\sum_{e\in E(\tau)}l_{e}$. Also,
$q=d^{O(1)\cdot\varepsilon(C_{V}+C_{E})}$. We can set $C_{V},C_{E}$
sufficiently small so that

$\displaystyle c(\tau)B_{norm}(\tau)S(\tau)R(\tau)$
$\displaystyle=100(6D_{V})^{|U_{\tau}\setminus V_{\tau}|+|V_{\tau}\setminus
U_{\tau}|+2|E(\tau)|}4^{|V(\tau)\setminus(U_{\tau}\cup V_{\tau})|}$
$\displaystyle\cdot 2e(6qD_{V})^{|V(\tau)\setminus U_{\tau}|+|V(\tau)\setminus
V_{\tau}|}\prod_{e\in E(\tau)}(400D_{V}^{2}D_{E}^{2}q)^{l_{e}}$
$\displaystyle\cdot\sqrt{d}^{|\tau|_{1}-|U_{\tau}|_{1}}\sqrt{m}^{|\tau|_{2}-|U_{\tau}|_{2}}S(\tau)(C_{disc}\sqrt{D_{E}})^{\sum_{j\in(U_{\tau})_{2}\cup(V_{\tau})_{2}}deg^{\tau}(j)}$
$\displaystyle\leq d^{O(1)\cdot(C_{V}+C_{E})\cdot\varepsilon\sum_{e\in
E(\tau)}l_{e}}\cdot\prod_{j\in V_{2}(\tau)\setminus V_{2}(U_{\tau})\setminus
V_{2}(V_{\tau})}(deg^{\tau}(j)-1)!!\cdot\frac{1}{d^{A\varepsilon\sum_{e\in
E(\tau)}l_{e}}}$ $\displaystyle\leq
d^{O(1)\cdot(C_{V}+C_{E})\cdot\varepsilon\sum_{e\in
E(\tau)}l_{e}}\cdot(D_{V}D_{E})^{\sum_{e\in
E(\tau)}l_{e}}\cdot\frac{1}{d^{A\varepsilon\sum_{e\in E(\tau)}l_{e}}}$
$\displaystyle\leq 1$

We can now prove Lemma 13.3.

See 13.3

###### Proof.

We have

$\displaystyle\begin{bmatrix}\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}&B_{norm}(\tau)H_{\tau}\\\
B_{norm}(\tau)H_{\tau}^{T}&\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}\end{bmatrix}$
$\displaystyle\qquad=\begin{bmatrix}\left(\frac{1}{|Aut(U)|c(\tau)}-\frac{S(\tau)R(\tau)B_{norm}(\tau)}{|Aut(U)|}\right)H_{Id_{U}}&0\\\
0&\left(\frac{1}{|Aut(U)|c(\tau)}-\frac{S(\tau)R(\tau)B_{norm}(\tau)}{|Aut(U)|}\right)H_{Id_{U}}\end{bmatrix}$
$\displaystyle\qquad\quad+B_{norm}(\tau)\begin{bmatrix}\frac{S(\tau)R(\tau)}{|Aut(U)|}H_{Id_{U}}&H_{\tau}\\\
H_{\tau}^{T}&\frac{S(\tau)R(\tau)}{|Aut(U)|}H_{Id_{U}}\end{bmatrix}$

By Lemma 6.15,
$\begin{bmatrix}\frac{S(\tau)R(\tau)}{|Aut(U)|}H_{Id_{U}}&H_{\tau}\\\
H_{\tau}^{T}&\frac{S(\tau)R(\tau)}{|Aut(U)|}H_{Id_{U}}\end{bmatrix}\succeq 0$,
so the second term above is positive semidefinite. For the first term, by
Lemma 6.11, $H_{Id_{U}}\succeq 0$ and by Corollary 13.11,
$\frac{1}{|Aut(U)|c(\tau)}-\frac{S(\tau)R(\tau)B_{norm}(\tau)}{|Aut(U)|}\geq
0$, which proves that the first term is also positive semidefinite.

###  13.2 Proof of Lemma 13.4

######  Lemma 13.12.

Suppose $0<A<\frac{1}{4}$ is a constant such that
$\frac{\sqrt{\lambda}}{\sqrt{k}}\leq d^{-A\varepsilon},\frac{1}{\sqrt{k}}\leq
d^{-2A}$ and $\frac{k}{d}\leq d^{-A\varepsilon}$. For all $m$ such that
$m\leq\frac{d^{1-\varepsilon}}{\lambda^{2}},m\leq\frac{k^{2-\varepsilon}}{\lambda^{2}}$,
for all $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$ and for all
$\gamma\in\Gamma_{U,V}$,

$n^{w(V(\gamma)\setminus U_{\gamma})}S(\gamma)^{2}\leq\left(\prod_{j\in
V_{2}(\gamma)\setminus U_{\gamma}\setminus
V_{\gamma}}(deg^{\gamma}(j)-1)!!\right)^{2}\frac{1}{d^{B\varepsilon(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|+\sum_{e\in E(\gamma)}l_{e})}}$

for some constant $B>0$ that depends only on $C_{\Delta}$. In particular, it
is independent of $C_{V}$ and $C_{E}$.

###### Proof.

Suppose there is a vertex $i\in V(\gamma)\setminus U_{\gamma}\setminus
V_{\gamma}$ such that $deg^{\gamma}(i)$ is odd, then $S(\gamma)=0$ and the
inequality is true. So, assume $deg^{\gamma}(i)$ is even for all vertices
$i\in V(\gamma)\setminus U_{\gamma}\setminus V_{\gamma}$. We have
$n^{w(V(\gamma)\setminus
U_{\gamma})}=d^{|\gamma|_{1}-|U_{\gamma}|_{1}}m^{|\gamma|_{2}-|U_{\gamma}|_{2}}$.
Plugging in $S(\gamma)$, we get that we have to prove

$\displaystyle
E:=d^{|\gamma|_{1}-|U_{\gamma}|_{1}}m^{|\gamma|_{2}-|U_{\gamma}|_{2}}\left(\frac{k}{d}\right)^{2|\gamma|_{1}-|U_{\gamma}|_{1}-|V_{\gamma}|_{1}}\Delta^{2|\gamma|_{2}-|U_{\gamma}|_{2}-|V_{\gamma}|_{2}}\prod_{e\in
E(\gamma)}\frac{\lambda^{l_{e}}}{k^{l_{e}}}\leq\frac{1}{d^{B\varepsilon(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|+\sum_{e\in E(\gamma)}l_{e})}}$

Let $S^{\prime}$ be the set of vertices $i\in U_{\gamma}\setminus V_{\gamma}$
that have $deg^{\gamma}(i)\geq 1$. Let $e,f$ be the number of type $1$
vertices and the number of type $2$ vertices in $S^{\prime}$ respectively.
Observe that $S^{\prime}\cup(U_{\gamma}\cap V_{\gamma})$ is a vertex separator
of $\gamma$.

Let $g=|V_{\gamma}\setminus U_{\gamma}|_{1}$ (resp. $h=|V_{\gamma}\setminus
U_{\gamma}|_{2}$) be the number of type $1$ vertices (resp. type $2$ vertices)
in $V_{\gamma}\setminus U_{\gamma}$.

We first claim that $d^{e}m^{f}\geq d^{g}m^{h}$. To see this, note that the
vertex separator $S^{\prime}\cup(U_{\gamma}\cap V_{\gamma})$ has weight
$\sqrt{d}^{e+|U_{\gamma}\cap V_{\gamma}|_{1}}\sqrt{m}^{f+|U_{\gamma}\cap
V_{\gamma}|_{2}}$. On the other hand, $V_{\gamma}$ has weight
$\sqrt{d}^{g+|U_{\gamma}\cap V_{\gamma}|_{1}}\sqrt{m}^{h+|U_{\gamma}\cap
V_{\gamma}|_{2}}$. Since $\gamma$ is a left shape, $V_{\gamma}$ is the unique
minimum vertex separator and hence, $\sqrt{d}^{e+|U_{\gamma}\cap
V_{\gamma}|_{1}}\sqrt{m}^{f+|U_{\gamma}\cap
V_{\gamma}|_{2}}\geq\sqrt{d}^{g+|U_{\gamma}\cap
V_{\gamma}|_{1}}\sqrt{m}^{h+|U_{\gamma}\cap V_{\gamma}|_{2}}$ which implies
$d^{e}m^{f}\geq d^{g}m^{h}$.

Let $p=|V(\gamma)\setminus(U_{\gamma}\cup V_{\gamma})|_{1}$ (resp.
$q=|V(\gamma)\setminus(U_{\gamma}\cup V_{\gamma})|_{2}$) be the number of type
$1$ vertices (resp. type $2$ vertices) in $V(\gamma)\setminus(U_{\gamma}\cup
V_{\gamma})$.

To illustrate the main idea, we will first prove the weaker inequality $E\leq
1$. Since $\Delta\leq 1$, it suffices to prove

$\displaystyle
d^{|\gamma|_{1}-|U_{\gamma}|_{1}}m^{|\gamma|_{2}-|U_{\gamma}|_{2}}\left(\frac{k}{d}\right)^{2|\gamma|_{1}-|U_{\gamma}|_{1}-|V_{\gamma}|_{1}}\prod_{e\in
E(\gamma)}\frac{\lambda^{l_{e}}}{k^{l_{e}}}\leq 1$

We have

$d^{|\gamma|_{1}-|U_{\gamma}|_{1}}m^{|\gamma|_{2}-|U_{\gamma}|_{2}}=d^{p+g}m^{q+h}\leq
n^{p+\frac{e+g}{2}}m^{q+\frac{f+h}{2}}$

since $d^{e}m^{f}\geq d^{g}m^{h}$. Also,
$2|\gamma|_{1}-|U_{\gamma}|_{1}-|V_{\gamma}|_{1}=2p+e+g$. So, it suffices to
prove

$\displaystyle
n^{p+\frac{e+g}{2}}m^{q+\frac{f+h}{2}}\left(\frac{k}{d}\right)^{2p+e+g}\prod_{e\in
E(\gamma)}\left(\frac{\lambda}{k}\right)^{l_{e}}\leq 1$

We will need the following claim.

######  Claim 13.13.

$\sum_{e\in E(\gamma)}l_{e}\geq\max(2p+e+g,2q+f+h)$

###### Proof.

Since $H_{\gamma}$ is bipartite, we have $\sum_{e\in
E(\gamma)}l_{e}=\sum_{i\in V_{1}(\gamma)}deg^{\gamma}(i)=\sum_{i\in
V_{2}(\gamma)}deg^{\gamma}(i)$. Observe that all vertices $i\in
V(\gamma)\setminus U_{\gamma}\setminus V_{\gamma}$ have $deg^{\gamma}(i)$
nonzero and even, and hence, $deg^{\gamma}(i)\geq 2$. Then,

$\displaystyle\sum_{e\in E(\gamma)}l_{e}$ $\displaystyle=\sum_{i\in
V_{1}(\gamma)}deg^{\gamma}(i)$ $\displaystyle\geq\sum_{i\in
V_{1}(\gamma)\setminus U_{\gamma}\setminus
V_{\gamma}}deg^{\gamma}(i)+\sum_{i\in(U_{\gamma})_{1}\setminus
V_{\gamma}}deg^{\gamma}(i)+\sum_{i\in(V_{\gamma})_{1}\setminus
U_{\gamma}}deg^{\gamma}(i)$ $\displaystyle\geq 2p+e+g$

Similarly,

$\displaystyle\sum_{e\in E(\gamma)}l_{e}$ $\displaystyle=\sum_{i\in
V_{2}(\gamma)}deg^{\gamma}(i)$ $\displaystyle\geq\sum_{i\in
V_{2}(\gamma)\setminus U_{\gamma}\setminus
V_{\gamma}}deg^{\gamma}(i)+\sum_{i\in(U_{\gamma})_{2}\setminus
V_{\gamma}}deg^{\gamma}(i)+\sum_{i\in(V_{\gamma})_{2}\setminus
U_{\gamma}}deg^{\gamma}(i)$ $\displaystyle\geq 2q+f+h$

Therefore, $\sum_{e\in E(\gamma)}l_{e}\geq\max(2p+e+g,2q+f+h)$.

Now, let $r_{1}=p+\frac{e+g}{2},r_{2}=q+\frac{f+h}{2}$. Then, $\sum_{e\in
E(\gamma)}l_{e}\geq 2\max(r_{1},r_{2})$ and we wish to prove

$\displaystyle
d^{r_{1}}m^{r_{2}}\left(\frac{k}{d}\right)^{2r_{1}}\left(\frac{\lambda}{k}\right)^{2\max(r_{1},r_{2})}\leq
1$

This expression simply follows by squaring 13.9.

Now, to prove that
$E\leq\frac{1}{d^{B\varepsilon(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|+\sum_{e\in E(\gamma)}l_{e})}}$, we mimic this argument while
carefully keeping track of factors of $d^{\varepsilon}$. Again, using
$d^{e}m^{f}\geq d^{g}m^{h}$, it suffices to prove that

$\displaystyle
d^{p+\frac{e+g}{2}}m^{q+\frac{f+h}{2}}\left(\frac{k}{d}\right)^{2|\gamma|_{1}-|U_{\gamma}|_{1}-|V_{\gamma}|_{1}}\Delta^{2|\gamma|_{2}-|U_{\gamma}|_{2}-|V_{\gamma}|_{2}}\prod_{e\in
E(\gamma)}\frac{\lambda^{l_{e}}}{k^{l_{e}}}\leq\frac{1}{d^{B\varepsilon(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|+\sum_{e\in E(\gamma)}l_{e})}}$

The idea is that the $d^{B\varepsilon}$ decay for the edges are obtained from
the stronger assumption on $m$, namely
$m\leq\frac{d^{1-\varepsilon}}{\lambda^{2}},m\leq\frac{k^{2-\varepsilon}}{\lambda^{2}}$.
And the $d^{B\varepsilon}$ decay for the type $1$ vertices of
$V(\gamma)\setminus(U_{\gamma}\cap V_{\gamma})$ are obtained both from the
stronger assumption on $m$ as well as the factors of $\frac{k}{d}$, the latter
especially useful for the degree $0$ vertices. Finally, the $d^{B\varepsilon}$
decay for the type $2$ vertices of $V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})$ are obtained from the factors of $\Delta$.

Indeed, note that for a constant $B$ that depends on $C_{\Delta}$,
$\Delta^{2|\gamma|_{2}-|U_{\gamma}|_{2}-|V_{\gamma}|_{2}}\leq
d^{-B\varepsilon|V(\gamma)\setminus(U_{\gamma}\cap V_{\gamma})|_{2}}$. So, we
would be done if we prove

$\displaystyle
d^{p+\frac{e+g}{2}}m^{q+\frac{f+h}{2}}\left(\frac{k}{d}\right)^{2|\gamma|_{1}-|U_{\gamma}|_{1}-|V_{\gamma}|_{1}}\left(\frac{\lambda}{k}\right)^{\sum_{e\in
E(\gamma)}l_{e}}\leq\frac{1}{d^{B\varepsilon(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|_{1}+\sum_{e\in E(\gamma)}l_{e})}}$

Let $c_{0}$ be the number of type $1$ vertices $i$ in
$V(\gamma)\setminus(U_{\gamma}\cap V_{\gamma})$ such that $deg^{\gamma}(i)=0$.
Since they have degree $0$, they must be in $(U_{\gamma})_{1}\setminus
V_{\gamma}$. Also, we have
$2|\gamma|_{1}-|U_{\gamma}|_{1}-|V_{\gamma}|_{1}=2p+e+g+c_{0}$ and hence,
$\left(\frac{k}{d}\right)^{2|\gamma|_{1}-|U_{\gamma}|_{1}-|V_{\gamma}|_{1}}=\left(\frac{k}{d}\right)^{2p+e+g+c_{0}}$.
For these degree $0$ vertices, we have that the factors of $\frac{k}{d}\leq
d^{-A\varepsilon}$ offer a decay of $\frac{1}{d^{B\varepsilon}}$. Therefore,
it suffices to prove

$\displaystyle
d^{p+\frac{e+g}{2}}m^{q+\frac{f+h}{2}}\left(\frac{k}{d}\right)^{2p+e+g}\left(\frac{\lambda}{k}\right)^{\sum_{e\in
E(\gamma)}l_{e}}\leq\frac{1}{d^{B\varepsilon(p+q+e+f+g+h)+\sum_{e\in
E(\gamma)}l_{e})}}$

for a constant $B>0$. Observe that $p+q+e+f+g+h\leq 2(\sum_{e\in
E(\gamma)}l_{e})$. Therefore, using the notation
$r_{1}=p+\frac{e+g}{2},r_{2}=q+\frac{f+h}{2}$, it suffices to prove

$\displaystyle
d^{r_{1}}m^{r_{2}}\left(\frac{k}{d}\right)^{2r_{1}}\left(\frac{\lambda}{k}\right)^{\sum_{e\in
E(\gamma)}l_{e}}\leq\frac{1}{d^{B\varepsilon\sum_{e\in E(\gamma)}l_{e}}}$

for a constant $B>0$. But this follows by squaring 13.10 where we set
$r=\sum_{e\in E(\gamma)}l_{e}$.

######  Remark 13.14.

In the above bounds, note that there is a decay of $d^{B\varepsilon}$ for each
vertex in $V(\gamma)\setminus(U_{\gamma}\cap V_{\gamma})$. One of the main
technical reasons for introducing the slack parameter $C_{\Delta}$ in the
planted distribution was to introduce this decay, which is needed in the
current machinery.

We can now prove Lemma 13.4.

See 13.4

###### Proof.

By Lemma 6.17, we have

$\displaystyle
c(\gamma)^{2}N(\gamma)^{2}B(\gamma)^{2}H_{Id_{V}}^{-\gamma,\gamma}$
$\displaystyle\preceq
c(\gamma)^{2}N(\gamma)^{2}B(\gamma)^{2}S(\gamma)^{2}R(\gamma)^{2}\frac{|Aut(U)|}{|Aut(V)|}H^{\prime}_{\gamma}$

Using the same proof as in Lemma 6.11, we can see that
$H^{\prime}_{\gamma}\succeq 0$. Therefore, it suffices to prove that

$c(\gamma)^{2}N(\gamma)^{2}B(\gamma)^{2}S(\gamma)^{2}R(\gamma)^{2}\frac{|Aut(U)|}{|Aut(V)|}\leq
1$

Since $U,V\in{\mathcal{I}}_{mid}$,
$Aut(U)=|U|_{1}!|U|_{2}!,Aut(V)=|V|_{1}!|V|_{2}!$. Therefore,
$\frac{|Aut(U)|}{|Aut(V)|}=\frac{|U|_{1}!|U|_{2}!}{|V|_{1}!|V|_{2}!}\leq
D_{V}^{|U_{\gamma}\setminus V_{\gamma}|}$. Also, $|E(\gamma)|\leq\sum_{e\in
E(\gamma)}l_{e}$ and $q=d^{O(1)\cdot\varepsilon(C_{V}+C_{E})}$. Note that
$R(\gamma)^{2}=(C_{disc}\sqrt{D_{E}})^{2\sum_{j\in(U_{\gamma})_{2}\cup(V_{\gamma})_{2}}deg^{\gamma}(j)}\leq
d^{O(1)\cdot\varepsilon C_{E}\cdot\sum_{e\in E(\gamma)}l_{e}}$ and
$\left(\prod_{j\in V_{2}(\gamma)\setminus U_{\gamma}\setminus
V_{\gamma}}(deg^{\gamma}(j)-1)!!\right)^{2}\leq(D_{V}D_{E})^{2\sum_{e\in
E(\tau)}l_{e}}\leq d^{O(1)\cdot\varepsilon(C_{V}+C_{E})\cdot\sum_{e\in
E(\gamma)}l_{e}}$.

Let $B$ be the constant from Lemma 13.12. We can set $C_{V},C_{E}$
sufficiently small so that, using Lemma 13.12,

$\displaystyle c(\gamma)^{2}N(\gamma)^{2}B(\gamma)^{2}$ $\displaystyle
S(\gamma)^{2}R(\gamma)^{2}\frac{|Aut(U)|}{|Aut(V)|}$ $\displaystyle\leq
100^{2}(6D_{V})^{2|U_{\gamma}\setminus V_{\gamma}|+2|V_{\gamma}\setminus
U_{\gamma}|+|E(\alpha)|}16^{|V(\gamma)\setminus(U_{\gamma}\cup V_{\gamma})|}$
$\displaystyle\quad\cdot(3D_{V})^{4|V(\gamma)\setminus
V_{\gamma}|+2|V(\gamma)\setminus U_{\gamma}|}(6qD_{V})^{2|V(\gamma)\setminus
U_{\gamma}|+2|V(\gamma)\setminus V_{\gamma}|}\prod_{e\in
E(\gamma)}(400D_{V}^{2}D_{E}^{2}q)^{2l_{e}}$ $\displaystyle\quad\cdot
n^{w(V(\gamma)\setminus U_{\gamma})}S(\gamma)^{2}d^{O(1)\cdot\varepsilon
C_{E}\cdot\sum_{e\in E(\gamma)}l_{e}}\cdot D_{V}^{|U_{\gamma}\setminus
V_{\gamma}|}$ $\displaystyle\leq