ending points $v$ and $v^{\prime}$ belong to separate plain tree components in
$\Gamma_{m/2}$, by (P7).

The above observation suggests that to specify the bridges in
${\mathcal{E}}_{\rm single}(m)$, one can use the _forward construction_ by
first choosing their starting points from separate components of $\Gamma_{m}$
then choosing the ending points from shorter orbits $\cup_{\ell<m}S_{\ell}$ in
an unconstrained way; to specify the bridges in ${\mathcal{E}}_{\rm
double}(m)$, one can use the _backward construction_ by first choosing their
ending points from separate components of $\Gamma_{m/2}$ then choosing the
starting points from $S_{m}$ in an unconstrained way. This separate account of
bridges is useful in the enumeration scheme which we describe next.

Next, we describe an algorithm for generating all possible backbone graphs
$\Gamma$ that satisfy the properties (P1)–(P7). Given a sequence of integers
$(\mathbf{a},\mathbf{b},\mathbf{c},\mathbf{d})=(a_{t},b_{t},c_{t},d_{t})_{1\leq
t\leq k}$ with $b_{t}=0$ for odd $t$ and $d_{t}=0$ if $2t>k$, we construct
$\Gamma$ as follows:

Algorithm 2 Pseudoforest enumeration algorithm

1:for each $t=1,\ldots,k$ do

2: Step 1: Matching stage. Construct a rooted pseudoforest $\Gamma_{t}$ with
$n_{t}$ giant nodes and $a_{t}$ giant edges (allowing self-loops and multiple
edges). Attach a label from $[t]$ to each giant edge and a label from
$\left[\lfloor\frac{t-1}{2}\rfloor\right]$ to each self-loop;

3: Step 2: Splitting stage. Choose $b_{t}$ components from $n_{t}-a_{t}$ tree
components of $\Gamma_{t}$, and within each chosen component, choose a node:
if the node chosen is the same as the root, add a split to the root;
otherwise, add two splits, one at the root and the other one at the chosen
node;

4: Step 3: Forward bridging stage. Choose $c_{t}$ out of the remaining
$n_{t}-a_{t}-b_{t}$ tree components of $\Gamma_{t}$, and for each chosen
component, add a bridge connecting its root to a giant node in $\Gamma_{\ell}$
for some $\ell<t$ that is a divisor of $t$. Attach a label from $[\ell]$ to
the added bridge.

5: Step 4: Backward bridging stage. Choose $d_{t}$ from the remaining
$n_{t}-a_{t}-b_{t}-c_{t}$ tree components of of $\Gamma_{t}$. For each chosen
component, add a bridge by connecting its root to a giant node in
$\Gamma_{2t}$. Attach a label from $[t]$ to the added bridge.

6:end for

We note that an output graph of Algorithm 2 is not necessarily a pseudoforest;
nevertheless any orbit pseudoforest can be generated by Algorithm 2, which is
what we need for upper bounding the generating function of orbit
pseudoforests, $\sum_{H\in{\mathcal{H}}_{k}}s^{2e(H)}$. To verify this claim
formally, let $H$ be an orbit pseudoforest and let $\Gamma$ denote its
backbone graph as in Definition 2, where for $1\leq m\leq k$ there are:

  * •

$a_{m}$ giant edges (including self-loops) corresponding to either Type
${\mathsf{M}}_{m}$ or ${\mathsf{C}}_{m}$ edge orbits;

  * •

$b_{m}$ components that contain splits corresponding to Type
${\mathsf{S}}_{m}$ edge orbits;

  * •

$c_{m}$ giant edges corresponding to Type ${\mathsf{B}}_{m,\ell}$ edge orbits
for some $\ell<m$ that is a divisor of $m$;

  * •

$d_{m}$ giant edges corresponding to Type ${\mathsf{B}}_{m,2m}$ edge orbits.

For each $\Gamma_{m}$ where $1\leq m\leq k$, we arbitrarily choose the root
for each plain tree component, and specify the root in each non-plain tree
component as the giant node that either splits or is incident to a bridge in
${\mathcal{E}}_{\rm single}(m)\cup{\mathcal{E}}_{\rm double}(2m)$ (when there
are two giant nodes that split in a tree component, we choose any one of them
as the root; otherwise, the choice of the root is unique). Then it is clear
that Steps 1 and 2 can realize any configuration of splits and matchings in
$\Gamma$, thanks to Properties (P1)–(P4). Finally, note that bridges in
${\mathcal{E}}_{\rm single}(m)$ are added by Step 3 (forward bridging) at
iteration $t=m$ with $c_{m}=|{\mathcal{E}}_{\rm single}(m)|$, and bridges in
${\mathcal{E}}_{\rm double}(m)$ are added by Step 4 (backward bridging) at
iteration $t=m/2$ with $d_{m/2}=|{\mathcal{E}}_{\rm double}(m)|$.

Next we bound the generating function $\sum_{H\in{\mathcal{H}}_{k}}s^{2e(H)}$
from above. We first state an auxiliary lemma, which extends the well-known
formula (74) for enumerating rooted forests.

######  Lemma 4.

The number of rooted pseudoforests on $n$ nodes with $a$ edges (allowing self-
loops and multiple edges) is at most

$\binom{n}{a}\left(2n\right)^{a}.$ (81)

###### Proof.

To see this, let $m$ denote the number of cycles (including self-loops and
parallel edges). Then the number of connected components is $n-a+m$. To
enumerate all such rooted pseudoforests, we first enumerate all rooted forests
on $n$ vertices with $a-m$ edges, then choose $m$ roots out of $n-a+m$ roots,
and finally add one edge to each chosen root to form a cycle within its
corresponding component. Each added edge can either be a self-loop at the root
or connect the root to some other node, so there are at most $n$ different
choices of the added edge. Therefore, the total number of rooted pseudoforests
on $n$ vertices with $a$ edges is at most

$\displaystyle\sum_{m=0}^{a}\binom{n}{a-m}n^{a-m}\binom{n-a+m}{m}n^{m}$
$\displaystyle=n^{a}\underbrace{\sum_{m=0}^{a}\binom{n}{a-m}\binom{n-a+m}{m}}_{2^{a}\binom{n}{a}}=\binom{n}{a}(2n)^{a}.$

∎

Now, we can enumerate all possible output backbone graphs $\Gamma$ of
Algorithm 2 as follows. For $t=1,\ldots,k$,

  1. 1.

Note that $\Gamma_{t}$ constructed in Step 1 is a rooted pseudoforest with
$n_{t}$ giant nodes and $a_{t}$ giant edges. Moreover, each giant edge added
in Step 1 carries at most $t$ possible labels. Hence, the total number of all
possible rooted pseudoforests $\Gamma_{t}$ constructed in Step 1 is at most:

$\displaystyle\binom{n_{t}}{a_{t}}\left(2tn_{t}\right)^{a_{t}}.$ (82)

  2. 2.

The total number of different ways of splitting is at most

$\displaystyle\binom{n_{t}-a_{t}}{b_{t}}n_{t}^{b_{t}}.$ (83)

  3. 3.

The total number of different ways of forward bridging is at most:

$\displaystyle\binom{n_{t}-a_{t}-b_{t}}{c_{t}}\left(\sum_{\ell<t}\ell
n_{\ell}\right)^{c_{t}}.$ (84)

  4. 4.

The total number of different ways of backward bridging is at most:

$\displaystyle\binom{n_{t}-a_{t}-b_{t}-c_{t}}{d_{t}}\left(tn_{2t}\right)^{d_{t}}.$
(85)

Combining (82), (83), (84), and (85), we conclude that the total number of
possible output backbone graphs $\Gamma$ with input parameter
$(\mathbf{a},\mathbf{b},\mathbf{c},\mathbf{d})$ is at most

$\displaystyle\prod_{t=1}^{k}{\mathbf{1}_{\left\\{{b_{t}=0\text{ for odd
}t}\right\\}}}{\mathbf{1}_{\left\\{{d_{t}=0\text{ if
}2t>k}\right\\}}}\binom{n_{t}}{a_{t},\,b_{t},\,c_{t},\,d_{t}}\left(2tn_{t}\right)^{a_{t}}n_{t}^{b_{t}}\left(\sum_{\ell<t}\ell
n_{\ell}\right)^{c_{t}}\left(tn_{2t}\right)^{d_{t}}.$

Note that for each output backbone graph, the total number of edges in the
corresponding orbit graph $H$ satisfies

$e(H)\geq\sum_{t=1}^{k}t\left(a_{t}+b_{t}/2+c_{t}+2d_{t}\right).$

Combining the above two displays, we obtain

$\displaystyle\sum_{H\in{\mathcal{H}}_{k}}s^{2e(H)}$
$\displaystyle\leq\sum_{\mathbf{a},\mathbf{b},\mathbf{c},\mathbf{d}}\;\prod_{t=1}^{k}{\mathbf{1}_{\left\\{{b_{t}=0\text{
for odd }t}\right\\}}}{\mathbf{1}_{\left\\{{d_{t}=0\text{ if
}2t>k}\right\\}}}\binom{n_{t}}{a_{t},\,b_{t},\,c_{t},\,d_{t}}$
$\displaystyle~{}~{}~{}~{}\times\left(2tn_{t}\right)^{a_{t}}n_{t}^{b_{t}}\left(\sum_{\ell<t}\ell
n_{\ell}\right)^{c_{t}}\left(tn_{2t}\right)^{d_{t}}\times
s^{2ta_{t}+tb_{t}+2td_{t}+4td_{t}}$
$\displaystyle\leq\prod_{t=1}^{k}\left(1+s^{t}n_{t}{\mathbf{1}_{\left\\{{t:\mathrm{even}}\right\\}}}+2tn_{t}s^{2t}+s^{2t}\sum_{\ell<t}\ell
n_{\ell}+s^{4t}tn_{2t}{\mathbf{1}_{\left\\{{2t\leq
k}\right\\}}}\right)^{n_{t}}$
$\displaystyle\leq\prod_{t=1}^{k}\left(1+s^{t}n_{t}{\mathbf{1}_{\left\\{{t:\mathrm{even}}\right\\}}}+2s^{2t}\sum_{\ell\leq
t}\ell n_{\ell}+s^{4t}tn_{2t}{\mathbf{1}_{\left\\{{2t\leq
k}\right\\}}}\right)^{n_{t}},$

completing the proof of Theorem 4.

##  6 Conclusion and Open Questions

In this paper, we formulate the general problem of testing network correlation
and characterize the statistical detection limit. For both Gaussian-weighted
complete graphs and dense Erdős-Rényi graphs, we determine the sharp threshold
at which the asymptotic optimal testing error probability jumps from $0$ to
$1$. For sparse Erdős-Rényi graphs, we determine the threshold within a
constant factor. The proof of the impossibility results relies on a delicate
application of the truncated second moment method, and in particular,
leverages the pseudoforest structure of subcritical Erdős-Rényi graphs in the
sparse setting. We conclude the paper with a few important open questions.

  1. 1.

In a companion paper [MWXY20], we show that a polynomial-time test based on
counting trees achieves strong detection when the average degree $np\geq
n^{-o(1)}$ and the correlation $\rho\geq c$ for an explicit constant $c$. In
particular, this result combined with our negative results in Theorem 2 imply
that the detection limit is attainable in polynomial-time up to a constant
factor in the sparse regime when $np=\Theta(1).$ However, achieving the
optimal detection threshold in polynomial time remains largely open.

  2. 2.

It is of interest to study the detection limit under general weight
distributions. Our proof techniques are likely to work beyond the Gaussian
Wigner and Erdős-Rényi graphs model. For example, for general distributions
$P$ and $Q$, as shown in the proof of Proposition 1, the second moment is
determined by the eigenvalues of the kernel operator defined by the likelihood
ratio $L(x,y)=\frac{P(x,y)}{Q(x,y)}$. Another interesting direction is testing
correlations between hypergraphs.

  3. 3.

Another important open problem is to determine the sharp threshold for
detection in the sparse Erdős-Rényi graphs with $p=n^{-\Omega(1)}$. In
particular, to improve our positive result, one may need to analyze a more
powerful test statistic beyond QAP. For the negative direction, one needs to
consider the case where the intersection graph $A\wedge B^{\pi}$ is
supercritical and a more sophisticated conditioning beyond the pseudoforest
structure may be required.

##  Appendix A Supplementary Proof for Sections 1, 3 and 4

###  A.1 Proof for Remark 1

In this subsection, we show that in the non-trivial regime of
$p=\omega(1/n^{2})$ and $p=1-\Omega(1)$, weak detection can be achieved by
comparing the number of edges of the two observed graph, provided that
$s=\Omega(1)$. To see this, let $X,Y$ denote the total number of edges in the
observed graphs $\overline{G}_{1}$ and $\overline{G}_{2}$, respectively. Under
${\mathcal{H}}_{0}$ (resp. ${\mathcal{H}}_{1}$), $X-Y$ is a sum of $m$
$i.i.d.$ random variables that equal to $-1$ or $+1$ with the equal
probability $ps(1-ps)$ (resp. $ps(1-s)$) and $0$ otherwise. Using Gaussian
approximation, this essentially reduces to testing ${\mathcal{N}}(0,1)$ vs.
${\mathcal{N}}\left(0,\frac{1-ps}{1-s}\right)$, which can be non-trivially
separated as long as $s$ is non-vanishing.

Formally, assume $s\leq 1-\Omega(1)$ without loss of generality and let
$m=\binom{n}{2}$. Then for some $\tau$,

$\displaystyle{\mathcal{Q}}\left(|X-Y|\geq\tau\right)-{\mathcal{P}}\left(|X-Y|\geq\tau\right)$
$\displaystyle\overset{(a)}{\geq}\mathbb{P}\left(|{\mathcal{N}}(0,2mps(1-ps))|\geq\tau\right)-\mathbb{P}\left(|{\mathcal{N}}(0,2mps(1-s))|\geq\tau\right)-O\left(\frac{1}{\sqrt{mp}}\right)$
$\displaystyle\overset{(b)}{=}\mathrm{TV}\left({\mathcal{N}}\left(0,1\right),{\mathcal{N}}\left(0,\frac{1-ps}{1-s}\right)\right)-O\left(\frac{1}{\sqrt{mp}}\right)\overset{(c)}{=}\Omega(1),$

where $(a)$ follows from Berry-Esseen theorem [Pet95, Theorem 5.5] and the
assumption that $\Omega(1)\leq s\leq 1-\Omega(1)$; $(b)$ holds for some $\tau$
because the likelihood ratio between two centered normals is monotonic in
$|x|$; $(c)$ holds because $(1-ps)/(1-s)$ is bounded away from $1$ and
$mp=\omega(1)$ under assumptions that $s=\Omega(1)$, $p$ is bounded away from
$1$, and $n^{2}p=\omega(1)$.

###  A.2 Proof of Proposition 2

###### Proof.

Using (28), we have $N_{2}=\binom{n_{2}}{2}\times
2+n_{1}n_{2}+n_{4}\leq(n_{2}+n_{1})n_{2}+n_{4}\leq nn_{2}+n$. Therefore,

$\displaystyle\mathbb{E}_{\pi\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}{}{\widetilde{\pi}}}\left[\exp\left(\mu
n_{1}^{2}+\nu n_{1}+\tau n_{2}+\tau^{2}N_{2}\right){\mathbf{1}_{\left\\{{a\leq
n_{1}\leq b}\right\\}}}\right]$
$\displaystyle\leq\mathbb{E}_{\pi\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}{}{\widetilde{\pi}}}\left[\exp\left(\mu
n_{1}^{2}+\nu
n_{1}+\left(\tau+\tau^{2}n\right)n_{2}+\tau^{2}n\right){\mathbf{1}_{\left\\{{a\leq
n_{1}\leq b}\right\\}}}\right]$
$\displaystyle=\left(1+o(1)\right)\mathbb{E}_{\pi\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}{}{\widetilde{\pi}}}\left[\exp\left(\mu
n_{1}^{2}+\nu n_{1}+(\tau+\tau^{2}n)n_{2}\right){\mathbf{1}_{\left\\{{a\leq
n_{1}\leq b}\right\\}}}\right],$

where the last equality holds because $n\tau^{2}=o(1)$ by assumption. Pick
$\eta$ such that $\omega(1)\leq\eta\leq\sqrt{n}$. We decompose
$\mathbb{E}_{\pi\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}{}{\widetilde{\pi}}}\left[\exp\left(\mu
n_{1}^{2}+\nu n_{1}+(\tau+\tau^{2}n)n_{2}\right){\mathbf{1}_{\left\\{{a\leq
n_{1}\leq b}\right\\}}}\right]$ as $\text{(I)}+\text{(II)}$, where:

(I) $\displaystyle=\mathbb{E}_{\pi\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}{}{\widetilde{\pi}}}\left[\exp\left(\mu
n_{1}^{2}+\nu
n_{1}+\left(\tau+\tau^{2}n\right)n_{2}\right){\mathbf{1}_{\left\\{{a\leq
n_{1}\leq b}\right\\}}}{\mathbf{1}_{\left\\{{0\leq
n_{1}<\eta}\right\\}}}\right]$ (II)
$\displaystyle=\mathbb{E}_{\pi\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}{}{\widetilde{\pi}}}\left[\exp\left(\mu
n_{1}^{2}+\nu
n_{1}+\left(\tau+\tau^{2}n\right)n_{2}\right){\mathbf{1}_{\left\\{{a\leq
n_{1}\leq
b}\right\\}}}{\mathbf{1}_{\left\\{{n_{1}\geq\eta}\right\\}}}\right].$

  * •

To bound (I), we first apply the total variation bound (122) in Lemma 13 and
get

$\mathrm{TV}\left({\mathcal{L}}\left(n_{1},n_{2}\right),{\mathcal{L}}\left(Z_{1},Z_{2}\right)\right)\leq
F\left(\frac{n}{2}\right),$

where $Z_{1}\sim{\rm Poi}(1)$ and $Z_{2}\sim{\rm Poi}(\frac{1}{2})$ are
independent Poisson random variables, and $\log
F(n/2)=-(1+o(1))\frac{n}{2}\log\left(\frac{n}{2}\right)$. Then, we have

(I) $\displaystyle\leq\mathbb{E}\left[\exp\left(\mu Z_{1}^{2}+\nu
Z_{1}+\left(\tau+\tau^{2}n\right)Z_{2}\right){\mathbf{1}_{\left\\{{a\leq
Z_{1}<b}\right\\}}}\right]+2F\left(\frac{n}{2}\right)\exp\left(\left(\mu\eta+\nu\right)\eta+\left(\tau+\tau^{2}n\right)n\right)$
$\displaystyle=\mathbb{E}\left[\exp\left(\mu Z_{1}^{2}+\nu
Z_{1}+\left(\tau+\tau^{2}n\right)Z_{2}\right){\mathbf{1}_{\left\\{{a\leq
Z_{1}<b}\right\\}}}\right]+o(1),$

where the last equality holds by the claim that
$\left(\mu\eta+\nu\right)\eta+\left(\tau+\tau^{2}n\right)n=o(n\log n)$.
Indeed, note that $\mu b+\nu+2-\log b\leq 0$ and $\omega(1)\leq b\leq n$. It
follows that $\mu\leq\log(b)/b=o(1)$ and $\nu\leq\log b\leq\log n$. Moreover,
$\tau^{2}=o\left(\frac{1}{n}\right)$ and $\omega(1)\leq\eta\leq\sqrt{n}$.
Hence the claim follows.

  * •

To bound (II), we apply (121) in Lemma 12:

(II) $\displaystyle\leq\mathbb{E}\left[\exp\left(\mu Z_{1}^{2}+\nu
Z_{1}+\left(\tau+\tau^{2}n\right)Z_{2}\right){\mathbf{1}_{\left\\{{\eta\leq
Z_{1}\leq b}\right\\}}}\right]e^{\frac{3}{2}}.$

By applying the moment generating function $\mathbb{E}_{X\sim{\rm
Poi}(\lambda)}\left[\exp\left(tX\right)\right]=\exp\left(\lambda\left(e^{t}-1\right)\right)$,
we then get that
$\mathbb{E}\left[\exp\left(\left(\tau+\tau^{2}n\right)Z_{2}\right)\right]=1+o(1)$
given $\tau^{2}=o\left(\frac{1}{n}\right)$. Therefore, we have

(I) $\displaystyle\leq\mathbb{E}\left[\exp\left(\mu Z_{1}^{2}+\nu
Z_{1}\right){\mathbf{1}_{\left\\{{a\leq Z_{1}\leq
b}\right\\}}}\right](1+o(1))+o(1)$ (II)
$\displaystyle\leq\mathbb{E}\left[\exp\left(\mu Z_{1}^{2}+\nu
Z_{1}\right){\mathbf{1}_{\left\\{{\eta\leq Z_{1}\leq
b}\right\\}}}\right](1+o(1))e^{\frac{3}{2}}.$

The following intermediate result is proved in the end.

######  Lemma 5.

Assume $\alpha,\beta\geq 0$, $\alpha m+\beta+2-\log m\leq 0$ for some $1\leq
m\leq n$ such that $m=\omega(1)$, and $Z\sim{\rm Poi}\left(\lambda\right)$ for
some $0<\lambda\leq 1$.

  * •

If $\ell=\omega(1)$ and $\beta\leq\log(\ell)-3$,

$\displaystyle\mathbb{E}\left[\exp\left(\alpha Z^{2}+\beta
Z\right){\mathbf{1}_{\left\\{{\ell\leq Z\leq m}\right\\}}}\right]=o(1).$ (86)

  * •

If $\ell=0$ and $\beta=o(1)$,

$\displaystyle\mathbb{E}\left[\exp\left(\alpha Z^{2}+\beta
Z\right){\mathbf{1}_{\left\\{{\ell\leq Z\leq m}\right\\}}}\right]=1+o(1).$
(87)

If $a=\omega(1)$, applying (86) yields $\text{(I)}=o(1)$ and
$\text{(II)}=o(1)$, hence the desired (47). If $a=0$, applying both (86) and
(87), we get $\text{(I)}=1+o(1)$, $\text{(II)}=o(1)$, and hence the desired
(48).

Finally to show (49), note that using (28), we have
$N_{1}=\binom{n_{1}}{2}+n_{2}\leq n_{1}^{2}/2+n_{2}$. Then, we have
$\mathbb{E}_{\pi\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}{}{\widetilde{\pi}}}\left[\exp\left(\tau
N_{1}+\tau^{2}N_{2}\right)\right]\leq\mathbb{E}_{\pi\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}{}{\widetilde{\pi}}}\left[\exp\left(\tau
n_{1}^{2}/2+\tau n_{2}+\tau^{2}N_{2}\right)\right]$. Thus the desired bound
follows from applying (48) with $\mu=\tau^{2}/2$, $\nu=0$, $a=0$, and $b=n$. ∎

###### Proof of Lemma 5.

To show (86), note that

$\displaystyle\mathbb{E}\left[\exp\left(\alpha Z^{2}+\beta
Z\right){\mathbf{1}_{\left\\{{\ell\leq Z\leq m}\right\\}}}\right]$
$\displaystyle=e^{-\lambda}\sum_{a_{1}=\ell}^{m}\frac{\lambda^{a_{1}}\exp\left(\alpha
a_{1}^{2}+\beta a_{1}\right)}{a_{1}!}$
$\displaystyle\overset{(a)}{\leq}e^{-\lambda}\sum_{a_{1}=\ell}^{m}\lambda^{a_{1}}\exp\left(\alpha
a_{1}^{2}+\beta a_{1}-a_{1}\log a_{1}+a_{1}\right))$
$\displaystyle\overset{(b)}{=}e^{-\lambda}\sum_{a_{1}=\ell}^{m}\lambda^{a_{1}}\exp(-a_{1})=o(1),$

where $(a)$ holds due to $a_{1}!\geq(a_{1}/e)^{a_{1}}$ for $a_{1}\geq 1$;
$(b)$ follows from the claim that $\alpha x+\beta+2-\log x\leq 0$ for
$\ell\leq x\leq m$. To see this, define $f(x)=\frac{\log x-\beta-2}{x}$. Then
by assumption $f(m)\geq\alpha$. Since $f^{\prime}(x)\leq 0$ for $x\geq
e^{\beta+3}$ and $\ell\geq e^{\beta+3}$ by assumption, it follows that
$f(x)\geq\alpha$ for all $\ell\leq x\leq m$.

Next we prove (87). Since $\alpha m+\beta+2-\log m\leq 0$ for $m=\omega(1)$,
we have $\alpha\leq\log(m)/m=o(1)$. Moreover, $\beta=o(1)$ by assumption.
Therefore there exists some $t=\omega(1)$ such that $\ell=0<t\leq m$ and
$\alpha t^{2}+\beta t=o(1)$. Then

$\displaystyle\mathbb{E}\left[\exp\left(\alpha Z^{2}+\beta
Z\right){\mathbf{1}_{\left\\{{\ell\leq Z\leq m}\right\\}}}\right]$
$\displaystyle=\mathbb{E}\left[\exp\left(\alpha Z^{2}+\beta
Z\right){\mathbf{1}_{\left\\{{0\leq Z\leq
t}\right\\}}}\right]+\mathbb{E}\left[\exp\left(\alpha Z^{2}+\beta
Z\right){\mathbf{1}_{\left\\{{t<Z\leq m}\right\\}}}\right]$
$\displaystyle\overset{(a)}{=}e^{-\lambda}\sum_{a_{1}=0}^{t}\frac{\lambda^{a_{1}}\exp\left(\alpha
a_{1}^{2}+\beta a_{1}\right)}{a_{1}!}+o(1)$
$\displaystyle\overset{(b)}{=}e^{-\lambda}\sum_{a_{1}=0}^{t}\frac{\lambda^{a_{1}}\left(1+o(1)\right)}{a_{1}!}+o(1)\overset{(c)}{=}1+o(1),$

where $(a)$ holds by (86); $(b)$ holds because $\alpha a_{1}^{2}+\beta
a_{1}=o(1)$ for $0\leq a_{1}\leq t$; $(c)$ holds because
$\sum_{a_{1}=0}^{t}\frac{\lambda^{a_{1}}}{a_{1}!}=e^{\lambda}+o(1)$ for
$t=\omega(1)$. ∎

###  A.3 Sharp threshold for dense Erdős-Rényi graphs

In this subsection, we focus on the case of dense parent graph whose edge
density satisfies

$\displaystyle p\leq 1-\Omega(1)\quad\text{ and }\quad p=n^{-o(1)}.$ (88)

Recall that Theorem 3 implies that weak detection is impossible, if
$\rho^{2}=\frac{s^{2}(1-p)^{2}}{(1-ps)^{2}}\leq(2-\epsilon)\frac{\log n}{n}$.
We improve over this condition by showing that if

$\displaystyle nps^{2}\left(\log\frac{1}{p}-1+p\right)\leq(2-\epsilon)\log n,$
(89)

then weak detection is impossible. This completes the impossibility proof for
Theorem 2 in the dense regime of (88).

Without loss of generality, we assume that (89) holds with equality (otherwise
one can further subsample the edges), i.e.,

$\displaystyle nps^{2}\left(\log\frac{1}{p}-1+p\right)=(2-\epsilon)\log n.$
(90)

In the dense graph regime (88), under assumption (90), we have

$\displaystyle nps^{2}=\omega(1)\quad\text{ and }\quad s=n^{-1/2+o(1)}.$ (91)

As argued in Section 3.3, analogous to the Gaussian case, the unconditional
second moment explodes when $\rho^{2}\geq(2+\epsilon)\frac{\log n}{n}$, due to
the obstruction of fixed points, or more precisely, an atypically large
magnitude of $\prod_{O\in{\mathcal{O}}_{1}}X_{O}$. By (21),

$\displaystyle L(a,b)$
$\displaystyle=\frac{1-\eta}{1-ps}\left(\frac{1-s}{1-\eta}\right)^{a+b}\left(\frac{s(1-\eta)}{\eta(1-s)}\right)^{ab},$

where $\eta\triangleq\frac{ps(1-s)}{1-ps}$, and then by (30),

$\displaystyle\prod_{O\in{\mathcal{O}}_{1}}X_{O}$ $\displaystyle=\prod_{i<j\in
F}X_{ij}$
$\displaystyle=\left(\frac{1-\eta}{1-ps}\right)^{2\binom{n_{1}}{2}}\left(\frac{1-s}{1-\eta}\right)^{2e_{A}(F)+2e_{B^{\pi}}\left(F\right)}\left(\frac{s\left(1-\eta\right)}{\left(1-s\right)\eta}\right)^{2e_{A\wedge
B^{\pi}}(F)},$ (92)

where $F$ denotes the set of fixed points of
$\sigma=\pi^{-1}\circ{\widetilde{\pi}}$, and

$e_{A}(F)=\sum_{i<j\in F}A_{ij},\quad e_{B^{\pi}}\left(F\right)=\sum_{i<j\in
F}B_{\pi(i)\pi(j)},\quad\text{ and }\quad e_{A\wedge B^{\pi}}(F)=\sum_{i<j\in
F}A_{ij}B_{\pi(i)\pi(j)}.$

Since $s>\eta$, it follows that $\frac{1-s}{1-\eta}<1$ and
$\frac{s\left(1-\eta\right)}{\left(1-s\right)\eta}>1$. Thus when $e_{A\wedge
B^{\pi}}(F)$ is atypically large, $\prod_{i<j\in F}X_{ij}$ becomes enormously
large, driving the unconditional second moment to explode. Hence, we aim to
truncate $\prod_{i<j\in F}X_{ij}$ by conditioning on the maximum possible
value of $e_{A\wedge B^{\pi}}(F)$ under the planted model ${\mathcal{P}}$ when
$|F|=n_{1}$ is large.

Specifically, given $2\leq k\leq n$, define

$\displaystyle\zeta(k)\triangleq\binom{k}{2}ps^{2}\exp\left\\{1+W\left(\frac{2\log(2en/k)}{e(k-1)ps^{2}}-\frac{1}{e}\right)\right\\},$
(93)

where $W$ is the Lambert W function defined on $[-1,\infty)$ as the unique
solution of $W(x)e^{W(x)}=x$ for $x\geq-1/e$. Let

$\displaystyle\alpha\triangleq p\left(\log\frac{1}{p}-1+p\right).$ (94)

For each $S\subset[n]$, define the event

$\displaystyle{\mathcal{E}}_{S}\triangleq\bigg{\\{}$
$\displaystyle(A,B,\pi):e_{A}(S),e_{B^{\pi}}(S)\geq\binom{|S|}{2}ps-\sqrt{2\binom{|S|}{2}ps|S|\log\frac{2en}{|S|}},e_{A\wedge
B^{\pi}}(S)\leq\zeta\left(|S|\right)\bigg{\\}}.$ (95)

We condition on the event

$\displaystyle{\mathcal{E}}\triangleq\bigcap_{S\subset[n]:\alpha n\leq|S|\leq
n}{\mathcal{E}}_{S}.$ (96)

As previously explained in Section 4.1 for the Gaussian case, since we cannot
condition on the set $F$, in order to truncate $\prod_{i<j\in F}X_{ij}$,
${\mathcal{E}}$ is defined as the intersection of ${\mathcal{E}}_{S}$ over all
subsets $S$ with $|S|\geq\alpha n$, so that ${\mathcal{E}}$ implies
${\mathcal{E}}_{F}$ whenever $|F|\geq\alpha n$. However, in contrast to the
Gaussian case, it is no longer true that $e_{A\wedge
B^{\pi}}(S)=(1+o(1))\binom{|S|}{2}ps^{2}$ uniformly for all $S$ with
$|S|\geq\alpha n$. Thus, we condition on $e_{A\wedge
B^{\pi}}(S)\leq\zeta\left(|S|\right)$, where $\zeta(k)$ in (93) is defined
according to the large-deviation behavior of ${\rm
Binom}\left(\binom{k}{2},ps^{2}\right)$, as we will see in the next lemma.

The following lemma proves that ${\mathcal{E}}$ holds with high probability
under the planted model ${\mathcal{P}}$.

######  Lemma 6.

Suppose $\alpha n=\omega(1)$. Then
${\mathcal{P}}((A,B,\pi))\in{\mathcal{E}})=1-e^{-\Omega(\alpha n)}$.

###### Proof.

Fix an integer $\alpha n\leq k\leq n$ and let $m=\binom{k}{2}$. Let

$t=\sqrt{2mps\log(1/\delta)},\qquad
t^{\prime}=mps^{2}\exp\left\\{1+W\left(\frac{\log(1/\delta)}{emps^{2}}-\frac{1}{e}\right)\right\\},$

for a parameter $\delta$ to be specified later.

Fix a subset $S\subset[n]$ with $|S|=k$. As $e_{A}(S)\sim{\rm Binom}(m,ps)$
and $e_{B^{\pi}}(S)\sim{\rm Binom}(m,ps)$, using Chernoff’s bound for Binomial
distributions (118), we get that with probability at least $1-2\delta$,
$e_{A}(S)\geq mps-t$ and $e_{B^{\pi}}(S)\geq mps-t$. Moreover, since
$e_{A\wedge B^{\pi}}(S)\sim{\rm Binom}(m,ps^{2})$, Using the multiplicative
Chernoff bound for Binomial distributions (119), we get that with probability
at least $1-\delta$, $e_{A\wedge B^{\pi}}(S)\leq t^{\prime}$.

Now, there are $\binom{n}{k}\leq\left(\frac{en}{k}\right)^{k}$ different
choices of $S\subset[n]$ with $|S|=k$. Thus by choosing
$1/\delta=\left(\frac{2en}{k}\right)^{k}$ and applying the union bound, we get
that with probability at least $1-3\sum_{k=\alpha
n}^{n}2^{-k}=1-e^{-\Omega(\alpha n)}$, $e_{A}(S)\geq mps-t$,
$e_{B^{\pi}}(S)\geq mps-t$, and $e_{A\wedge B^{\pi}}(S)\leq t^{\prime}$ for
all $S\subset[n]$ with $|S|=k$ and all $\alpha n\leq k\leq n$. ∎

Now we compute the conditional second moment. By Lemma 6, it follows from (52)
that

$\displaystyle\mathbb{E}_{{\mathcal{Q}}}\left[\left(\frac{{\mathcal{P}}^{\prime}(A,B)}{{\mathcal{Q}}(A,B)}\right)^{2}\right]=\left(1+o\left(1\right)\right)\mathbb{E}_{\pi\perp\\!\\!\\!\perp\widetilde{\pi}}\left[\mathbb{E}_{{\mathcal{Q}}}\left[\prod_{O\in{\mathcal{O}}}X_{O}{\mathbf{1}_{\left\\{{\left(A,B,\pi\right)\in{\mathcal{E}}}\right\\}}}{\mathbf{1}_{\left\\{{\left(A,B,\widetilde{\pi}\right)\in{\mathcal{E}}}\right\\}}}\right]\right].$

To proceed further, we fix $\pi,{\widetilde{\pi}}$ and separately consider the
following two cases. Recall that $\alpha$ is defined in (94).

Case 1: $n_{1}\leq\alpha n$. In this case, we simply drop the indicators and
use the unconditional second moment:

$\mathbb{E}_{{\mathcal{Q}}}\left[\prod_{O\in{\mathcal{O}}}X_{O}{\mathbf{1}_{\left\\{{\left(A,B,\pi\right)\in{\mathcal{E}}}\right\\}}}{\mathbf{1}_{\left\\{{\left(A,B,\widetilde{\pi}\right)\in{\mathcal{E}}}\right\\}}}\right]\leq\mathbb{E}_{{\mathcal{Q}}}\left[\prod_{O\in{\mathcal{O}}}X_{O}\right]=\prod_{O\in{\mathcal{O}}}\left(1+\rho^{2|O|}\right),$

where the equality follows from (38).

Case 2: $n_{1}>\alpha n$. In this case, we have that

$\displaystyle\mathbb{E}_{{\mathcal{Q}}}\left[\prod_{O\in{\mathcal{O}}}X_{O}{\mathbf{1}_{\left\\{{\left(A,B,\pi\right)\in{\mathcal{E}}}\right\\}}}{\mathbf{1}_{\left\\{{\left(A,B,\widetilde{\pi}\right)\in{\mathcal{E}}}\right\\}}}\right]$
$\displaystyle\overset{(a)}{\leq}\mathbb{E}_{{\mathcal{Q}}}\left[\prod_{O\in{\mathcal{O}}}X_{O}{\mathbf{1}_{\left\\{{\left(A,B,\pi\right)\in{\mathcal{E}}_{F}}\right\\}}}\right]$
$\displaystyle\overset{(b)}{=}\prod_{O\notin{\mathcal{O}}_{1}}\mathbb{E}_{{\mathcal{Q}}}\left[X_{O}\right]\mathbb{E}_{{\mathcal{Q}}}\left[\prod_{O\in{\mathcal{O}}_{1}}X_{O}{\mathbf{1}_{\left\\{{\left(A,B,\pi\right)\in{\mathcal{E}}_{F}}\right\\}}}\right]$
$\displaystyle\overset{(c)}{=}\prod_{O\notin{\mathcal{O}}_{1}}\left(1+\rho^{2|O|}\right)\mathbb{E}_{{\mathcal{Q}}}\left[\prod_{i<j\in
F}X_{ij}{\mathbf{1}_{\left\\{{\left(A,B,\pi\right)\in{\mathcal{E}}_{F}}\right\\}}}\right],$

where $(a)$ holds because by definition (96),
${\mathcal{E}}\subset{\mathcal{E}}_{F}$ when $n_{1}>\alpha n$; $(b)$ holds
because $X_{O}$ is a function of $(A_{ij},B_{\pi(i)\pi(j)})_{(i,j)}$ that are
independent across different $O\in{\mathcal{O}}$, and
${\mathbf{1}_{\left\\{{(A,B,\pi)\in{\mathcal{E}}_{F}}\right\\}}}$ only depends
on $\left\\{(A_{ij},B_{\pi(i)\pi(j)})_{(i,j)\in
O}:O\in{\mathcal{O}}_{1}\right\\}$; $(c)$ follows from (38).

Let $m=\binom{n_{1}}{2}$. Under event ${\mathcal{E}}_{F}$, we have that
$e_{A}(F)\geq(1+o(1))mps$ and $e_{B^{\pi}}(F)\geq(1+o(1))mps$. This is because
by (95),

$\frac{n_{1}\log(n/n_{1})}{mps}=\frac{2\log(n/n_{1})}{(n_{1}-1)ps}\overset{(a)}{=}O\left(\frac{\log(1/\alpha)}{\alpha
nps}\right)\overset{(b)}{=}\Theta\left(\frac{1}{np^{2}s}\right)\overset{(c)}{=}o(1),$

where $(a)$ holds because $n_{1}\geq\alpha n$; $(b)$ holds due to
$\frac{1}{\alpha}\log\frac{1}{\alpha}=\Theta(1/p)$; $(c)$ holds because
$p=n^{o(1)}$ and $s=n^{-1/2+o(1)}$. Moreover, under event ${\mathcal{E}}_{F}$,
$e_{A\wedge B^{\pi}}(F)\leq\zeta(n_{1})$.

Let

$\displaystyle\gamma\equiv\gamma(n_{1})=\frac{2\log(2en/n_{1})}{(n_{1}-1)ps^{2}}.$
(97)

Then
$\zeta(n_{1})=mps^{2}\exp\left(1+W\left(\frac{\gamma-1}{e}\right)\right)$. The
following lemma characterizes the behavior of $\zeta(n_{1})$ in the following
three asymptotic regimes depending on $\gamma$.

######  Lemma 7.

  * •

If $\gamma=o(1)$, $\zeta(n_{1})=(1+o(1))mps^{2}$.

  * •

If $\gamma=\Theta(1)$, $\zeta(n_{1})=\Theta(mps^{2})$. In particular, for all
$n_{1}\geq\alpha n$, we have $\zeta(n_{1})=o(ms^{2})$.

  * •

If $\gamma=\omega(1)$, $\zeta(n_{1})\leq(e+o(1))mps^{2}\gamma/\log\gamma$. In
particular, for all $n_{1}\geq\alpha n$, $\zeta(n_{1})=o(ms^{2})$.

###### Proof.

  * •

$\gamma=o(1)$. Using the approximation
$W(\frac{\gamma-1}{e})=-1+\sqrt{2\gamma}+O(\gamma)$ [CGH+96, eq.(4.22)], we
get that $\zeta(n_{1})=(1+o(1))mps^{2}$.

  * •

$\gamma=\Theta(1)$. In this regime, $W(\frac{\gamma-1}{e})=\Theta(1)$ and thus
$\zeta(n_{1})=\Theta(mps^{2})$. In particular, for all $n_{1}\geq\alpha n$, we
have $\zeta(n_{1})=\Theta(mps^{2})=o(ms^{2})$. To see this, note that
$\frac{1}{\alpha}\log\frac{1}{\alpha}=\Theta(1/p)$. Thus,
$\gamma=O\left(\frac{\log(1/\alpha)}{\alpha
nps^{2}}\right)=O\left(\frac{1}{np^{2}s^{2}}\right)$. Hence
$p=O\left(\frac{1}{nps^{2}\gamma}\right)=o(1)$, as $nps^{2}=\omega(1)$ and
$\gamma=\Theta(1)$.

  * •

$\gamma=\omega(1)$. Using the approximation $W(x)=\log x-\log\log x+o(1)$ as
$x\to\infty$ [HH08, Theorem 2.7], we get that
$\zeta(n_{1})\leq(e+o(1))mps^{2}\gamma/\log\gamma=(2e+o(1))n_{1}\log(2en/n_{1})/\log(\gamma)$.
Moreover, for all $n_{1}\geq\alpha n$,

$\frac{\zeta(n_{1})}{ms^{2}}=O\left(\frac{n_{1}\log(n/n_{1})}{ms^{2}\log\gamma}\right)=O\left(\frac{\log(1/\alpha)}{\alpha
ns^{2}\log\gamma}\right)=\Theta\left(\frac{1}{nps^{2}\log\gamma}\right)=o(1).$

∎

In view of Lemma 7, we get that $\zeta(n_{1})\leq mps^{2}+o(ms^{2})$ for all
$n_{1}\geq\alpha n$. For ease of notation, we henceforth write $\zeta(n_{1})$
simply as $\zeta$.

It follows from (92) that

$\displaystyle\mathbb{E}_{{\mathcal{Q}}}\left[\prod_{i<j\in
F}X_{ij}{\mathbf{1}_{\left\\{{\left(A,B,\pi\right)\in{\mathcal{E}}_{F}}\right\\}}}\right]$
$\displaystyle=\left(\frac{1-\eta}{1-ps}\right)^{2\binom{n_{1}}{2}}\mathbb{E}_{{\mathcal{Q}}}\left[\left(\frac{1-s}{1-\eta}\right)^{2e_{A}(F)+2e_{B^{\pi}}(F)}\left(\frac{s\left(1-\eta\right)}{\left(1-s\right)\eta}\right)^{2e_{A\wedge
B^{\pi}}(F)}{\mathbf{1}_{\left\\{{\left(A,B,\pi\right)\in{\mathcal{E}}_{F}}\right\\}}}\right]$
$\displaystyle\leq\left(\frac{1-\eta}{1-ps}\right)^{2m}\left(\frac{1-s}{1-\eta}\right)^{(4+o(1))mps}\mathbb{E}_{\mathcal{Q}}\left[\left(\frac{s\left(1-\eta\right)}{\left(1-s\right)\eta}\right)^{2e_{A\wedge
B^{\pi}}(F)}{\mathbf{1}_{\left\\{{e_{A\wedge
B^{\pi}}(F)\leq\zeta}\right\\}}}\right]$
$\displaystyle=\exp\left\\{-(2+o(1))mps^{2}(1-p)\right\\}\mathbb{E}_{\mathcal{Q}}\left[\left(\frac{s\left(1-\eta\right)}{\left(1-s\right)\eta}\right)^{2e_{A\wedge
B^{\pi}}(F)}{\mathbf{1}_{\left\\{{e_{A\wedge
B^{\pi}}(F)\leq\zeta}\right\\}}}\right],$

where the last equality holds because in view of $\eta=\frac{ps(1-s)}{1-ps}$
and $s=o(1)$,

$\displaystyle\log\frac{1-\eta}{1-ps}$
$\displaystyle=\log\left(1+\frac{ps^{2}(1-p)}{(1-ps)^{2}}\right)=(1+o(1))ps^{2}(1-p)$
$\displaystyle\log\frac{1-\eta}{1-s}$
$\displaystyle=\log\left(1+\frac{s(1-p)}{(1-s)(1-ps)}\right)=(1+o(1))s(1-p).$

Let

$u=\left(\frac{s\left(1-\eta\right)}{\left(1-s\right)\eta}\right)^{2}=\left(\frac{(1-\eta)(1-ps)}{p(1-s)^{2}}\right)^{2}=(1+o(1))p^{-2}.$

Then for any $\lambda\in[0,1]$,

$\displaystyle\mathbb{E}_{\mathcal{Q}}\left[\left(\frac{s\left(1-\eta\right)}{\left(1-s\right)\eta}\right)^{2e_{A\wedge
B^{\pi}}(F)}{\mathbf{1}_{\left\\{{e_{A\wedge
B^{\pi}}(F)\leq\zeta}\right\\}}}\right]$
$\displaystyle\leq\mathbb{E}_{{\mathcal{Q}}}\left[u^{\lambda e_{A\wedge
B^{\pi}}(F)+(1-\lambda)\zeta}\right]$
$\displaystyle=u^{(1-\lambda)\zeta}\left(1+p^{2}s^{2}(u^{\lambda}-1)\right)^{m}.$

Optimizing over $\lambda\in[0,1]$, or equivalently, over
$y=u^{\lambda}\in[1,u]$, we get (by taking the log and differentiating) that

$\inf_{1\leq y\leq
u}\left(1+p^{2}s^{2}(y-1)\right)^{m}y^{-\zeta}=\left(\frac{m(1-p^{2}s^{2})}{m-\zeta}\right)^{m}\left(\frac{\zeta(1-p^{2}s^{2})}{p^{2}s^{2}(m-\zeta)}\right)^{-\zeta},$

where the infimum is achieved at
$y^{*}=\frac{\zeta(1-p^{2}s^{2})}{p^{2}s^{2}(m-\zeta)}$. Note that

$1\leq y^{*}\leq u\Longleftrightarrow
mp^{2}s^{2}\leq\zeta\leq\frac{mup^{2}s^{2}}{1+up^{2}s^{2}-p^{2}s^{2}}.$

Since $mps^{2}\leq\zeta\leq mps^{2}+o(ms^{2})$, $u=(1+o(1))p^{-2}$, $s=o(1)$,
and $p$ is bounded away from $1$, it follows that $y^{*}\in[1,u]$.

Putting everything together, we get that

$\displaystyle\mathbb{E}_{{\mathcal{Q}}}\left[\prod_{i<j\in
F}X_{ij}{\mathbf{1}_{\left\\{{(A,B,\pi)\in{\mathcal{E}}_{F}}\right\\}}}\right]$
$\displaystyle\leq\exp\left\\{-(2+o(1))mps^{2}(1-p)+m\log\frac{m(1-p^{2}s^{2})}{m-\zeta}+\zeta\log\frac{(m-\zeta)up^{2}s^{2}}{\zeta(1-p^{2}s^{2})}\right\\}$
$\displaystyle\overset{(a)}{\leq}\exp\left\\{-mps^{2}(2-p)+\zeta\left(\log(s^{2})+o(1)\right)+mh(\zeta/m)\right\\}$
$\displaystyle\overset{(b)}{\leq}\exp\left\\{-mps^{2}(2-p)+\zeta\log\frac{ems^{2}}{\zeta}+o(\zeta)\right\\},$

where $h(x)=-x\log x-(1-x)\log(1-x)$ is the binary entropy function; $(a)$
holds because in view of $s=o(1)$, we have $\zeta=ms^{2}(p+o(1))$, and
$u=(1+o(1))p^{-2}$, $(m-\zeta)\log(1-p^{2}s^{2})=-(1+o(1))mp^{2}s^{2}$ and
$\log(up^{2})=o(1)$; $(b)$ holds due to $h(x)=x\log(e/x)+o(x)$ by the Taylor
approximation.

Combining the two cases yields that

$\displaystyle\mathbb{E}_{{\mathcal{Q}}}\left[\left(\frac{{\mathcal{P}}^{\prime}(A,B)}{{\mathcal{Q}}(A,B)}\right)^{2}\right]$
$\displaystyle\leq(1+o(1))\mathbb{E}\left[\prod_{O\in{\mathcal{O}}}\left(1+\rho^{2|O|}\right){\mathbf{1}_{\left\\{{n_{1}\leq\alpha
n}\right\\}}}\right]$
$\displaystyle+(1+o(1))\mathbb{E}\left[\prod_{O\notin{\mathcal{O}}_{1}}\left(1+\rho^{2|O|}\right)\exp\left\\{\zeta\log\frac{ems^{2}}{\zeta}+o(\zeta)\right\\}{\mathbf{1}_{\left\\{{n_{1}>\alpha
n}\right\\}}}\right].$

Recall that $\rho=\frac{s(1-p)}{1-ps}\leq s$ and by (28),

$\displaystyle\prod_{O\notin{\mathcal{O}}_{1}}\left(1+\rho^{2|O|}\right)$
$\displaystyle=\left(1+\rho^{2}\right)^{n_{2}}\prod_{k\geq
2}\left(1+\rho^{2k}\right)^{N_{k}}$
$\displaystyle=(1+o(1))\left(1+\rho^{2}\right)^{n_{2}}\left(1+\rho^{4}\right)^{N_{2}}$
$\displaystyle\leq(1+o(1))\exp\left(s^{2}n_{2}+s^{4}N_{2}\right),$

where the first equality follows from (28); the second equality holds because
$\prod_{k\geq
3}\left(1+\rho^{2k}\right)^{N_{k}}\leq\exp\left(n^{2}\rho^{6}/2\right)=1+o(1)$
by (45) and $\rho\leq s=n^{-1/2+o(1)}$ in view of (91). Similarly,

$\prod_{O\in{\mathcal{O}}_{1}}\left(1+\rho^{2|O|}\right)=\left(1+\rho^{2}\right)^{\binom{n_{1}}{2}}\leq\exp\left(s^{2}n_{1}^{2}/2\right).$

Hence,

$\displaystyle\mathbb{E}_{{\mathcal{Q}}}\left[\left(\frac{{\mathcal{P}}^{\prime}(A,B)}{{\mathcal{Q}}(A,B)}\right)^{2}\right]$
$\displaystyle\leq(1+o(1))\mathbb{E}\left[\exp\left(s^{2}n_{1}^{2}/2+s^{2}n_{2}+s^{4}N_{2}\right){\mathbf{1}_{\left\\{{n_{1}\leq\alpha
n}\right\\}}}\right]$
$\displaystyle+(1+o(1))\mathbb{E}\left[\exp\left\\{s^{2}n_{2}+s^{4}N_{2}-mps^{2}(2-p)+\zeta\log\frac{ems^{2}}{\zeta}+o(\zeta)\right\\}{\mathbf{1}_{\left\\{{n_{1}>\alpha
n}\right\\}}}\right].$

We upper bound the two terms separately. For the first term, we apply (48) in
Proposition 2 with $\mu=s^{2}/2$, $\nu=0$, $\tau=s^{2}$, $a=0$, and $b=\alpha
n=p(\log\frac{1}{p}-1+p)n=n^{1-o(1)}=\omega(1)$. By the assumption that
$ns^{2}p(\log\frac{1}{p}-1+p)\leq(2-\epsilon)\log n/n$, it follows that

$\mu b+\nu+2-\log
b=\frac{1}{2}nps^{2}\left(\log\frac{1}{p}-1+p\right)+2-(1-o(1))\log
n\leq\frac{1}{2}\left(-\epsilon+o(1)\right)\log n+2\leq 0.$

Thus, it follows from (48) in Proposition 2 that

$\displaystyle\mathbb{E}\left[\exp\left(s^{2}n_{1}^{2}/2+s^{2}n_{2}+s^{4}N_{2}\right){\mathbf{1}_{\left\\{{n_{1}\leq\alpha
n}\right\\}}}\right]\leq 1+o(1).$

For the second term, we further divide into three cases according to Lemma 7.
We define

$\beta=\frac{\log^{2}(nps^{2})}{nps^{2}}\quad\text{ and
}\quad\beta^{\prime}=\frac{\log(nps^{2})}{100nps^{2}}.$

Recall $\gamma$ as defined in (97). By Lemma 7, we have that

  1. (a)

If $\beta n\leq n_{1}\leq n$, then $\gamma=o(1)$ and $\zeta=(1+o(1))mps^{2}$;

  2. (b)

If $\beta^{\prime}n\leq n_{1}\leq\beta n$, then $\gamma\leq 200+o(1)$ and
$\zeta=\Theta\left(mps^{2}\right)$;

  3. (c)

If $\alpha n\leq n_{1}\leq\beta^{\prime}n$, then $\gamma\geq 200+o(1)$ and
$\zeta=O\left(n_{1}\log\left(n/n_{1}\right)/\log(\gamma)\right)$.

Case 2 (a) : $\beta n\leq n_{1}\leq n$. In this case, $\zeta=(1+o(1))mps^{2}$
and hence

$\zeta\log\frac{ems^{2}}{\zeta}+o(\zeta)=(1+o(1))mps^{2}\log\frac{e}{p}.$

Therefore,

$\displaystyle\mathbb{E}\left[\exp\left\\{s^{2}n_{2}+s^{4}N_{2}-mps^{2}(2-p)+\zeta\log\frac{ems^{2}}{\zeta}+o(\zeta)\right\\}{\mathbf{1}_{\left\\{{n_{1}\geq\beta
n}\right\\}}}\right]$
$\displaystyle\leq\mathbb{E}\left[\exp\left\\{s^{2}n_{2}+s^{4}N_{2}+\frac{1+o(1)}{2}n_{1}^{2}ps^{2}\left(\log\frac{1}{p}-1+p\right)\right\\}{\mathbf{1}_{\left\\{{n_{1}\geq\beta
n}\right\\}}}\right]=o(1),$

where the first inequality uses the fact that $m\leq n_{1}^{2}/2$; the last
equality holds by invoking (47) in Proposition 2 with
$\mu=\frac{1+o(1)}{2}ps^{2}\left(\log\frac{1}{p}-1+p\right)$, $\nu=0$,
$\tau=s^{2}$, $a=\beta n=\omega(1)$, $b=n=\omega(1)$, and

$\displaystyle\mu b+\nu+2-\log
b=\frac{1+o(1)}{2}nps^{2}\left(\log\frac{1}{p}-1+p\right)+2-\log
n=-\frac{1}{2}(\epsilon+o(1))\log n+2\leq 0,$

where the last equality follows from the assumption that
$nps^{2}\left(\log\frac{1}{p}-1+p\right)=(2-\epsilon)\log n$.

When $p$ is a fixed constant bounded away from $1$, as $\alpha=\Theta(1)$ and
$\beta=o(1)$, we have $\beta=o(\alpha)$; thus the regime $\alpha n\leq
n_{1}\leq\beta n$ is vacuous. Thus henceforth we assume $p=o(1)$.

Case 2 (b) : $\beta^{\prime}n\leq n_{1}\leq\beta n$. In this case, $\gamma\leq
200+o(1)$ and $\zeta=O\left(mps^{2}\right),$ so that

$\zeta\log\frac{ems^{2}}{\zeta}+o(\zeta)\leq c_{1}mps^{2}\log\frac{1}{p}$

for a universal constant $c_{1}$. Therefore,

$\displaystyle\mathbb{E}\left[\exp\left\\{s^{2}n_{2}+s^{4}N_{2}-mps^{2}(2-p)+\zeta\log\frac{ems^{2}}{\zeta}+o(\zeta)\right\\}{\mathbf{1}_{\left\\{{\beta^{\prime}n\leq
n_{1}\leq\beta n}\right\\}}}\right]$
$\displaystyle\leq\mathbb{E}\left[\exp\left\\{s^{2}n_{2}+s^{4}N_{2}+c_{1}n_{1}^{2}ps^{2}\log\frac{1}{p}\right\\}{\mathbf{1}_{\left\\{{\beta^{\prime}n\leq
n_{1}\leq\beta n}\right\\}}}\right]=o(1),$

where the last equality holds by invoking Proposition 2 with
$\mu=c_{1}ps^{2}\log\frac{1}{p}$, $\nu=0$, $\tau=s^{2}$,
$a=\beta^{\prime}n=\omega(1)$, and $b=\beta n=\omega(1)$. Note that the
conditions of Proposition 2 for $a=\omega(1)$ are satisfied, in particular,
$\mu b+2-\log b\leq 0$ for $n$ sufficiently large. To see this, on the one
hand,

$\mu b=c_{1}\beta nps^{2}\log\frac{1}{p}=O\left(\beta\log n\right)=o(\log n),$

where we used the fact that $nps^{2}\log\frac{1}{p}=O(\log n)$ and
$\beta=o(1)$; on the other hand, $\log(b)=\log(\beta n)=(1+o(1))\log n$, as
$\log(\beta)=o(\log n)$ by our choice of $\beta$.

Case 2 (c) : $\alpha n\leq n_{1}\leq\beta^{\prime}n$. In this case,
$\gamma\geq 200+o(1)$ and

$\zeta=O\left(n_{1}\log(n/n_{1})/\log(\gamma)\right),$

so that

$\zeta\log\frac{ems^{2}}{\zeta}+o(\zeta)\leq
c_{1}n_{1}\frac{\log(n/n_{1})}{\log\gamma}\log\frac{n_{1}s^{2}\log\gamma}{\log(n/n_{1})}\triangleq
n_{1}\psi$

for a universal constant $c_{1}$. Therefore,

$\displaystyle\mathbb{E}\left[\exp\left\\{s^{2}n_{2}+s^{4}N_{2}-mps^{2}(2-p)+\zeta\log\frac{ems^{2}}{\zeta}+o(\zeta)\right\\}{\mathbf{1}_{\left\\{{\alpha
n\leq n_{1}\leq\beta^{\prime}n}\right\\}}}\right]$
$\displaystyle\leq\mathbb{E}\left[\exp\left\\{s^{2}n_{2}+s^{4}nn_{2}+n_{1}\psi\right\\}{\mathbf{1}_{\left\\{{\alpha
n\leq n_{1}\leq\beta^{\prime}n}\right\\}}}\right]=o(1),$

where the last equality holds by invoking (47) in Proposition 2 with $\mu=0$,
$\nu=\max_{\alpha n\leq n_{1}\leq\beta^{\prime}n}\psi(n_{1})$, $a=\alpha n$,
$b=\beta^{\prime}n$, and the claim that $\nu=o\left(\log(\alpha
n)\right)=o(\log a)$ . Note that the conditions of Proposition 2 for
$a=\omega(1)$ are satisfied, in particular, $\nu+3\leq\log a$ and $\mu
b+\nu+2-\log b=\nu+2-\log b\leq\nu+2-\log a\leq 0$ for $n$ sufficiently large.

To finish the proof, it remains to verify the claim that
$\psi=o\left(\log(\alpha n)\right)$ for $\alpha n\leq
n_{1}\leq\beta^{\prime}n$. Note that $\log(\alpha n)=(1+o(1))\log n$, as
$\log(\alpha)=o(\log n)$ by the choice of $\alpha$ and the assumption that
$p=n^{o(1)}$. Thus it suffices to show that $\psi=o(\log n)$, i.e.,

$\frac{\log(n/n_{1})}{\log\gamma}\log\frac{n_{1}s^{2}\log\gamma}{\log(n/n_{1})}=o\left(\log
n\right).$

Note that

$\frac{\log(n/n_{1})}{\log\gamma}\log\log\gamma\leq\log(n/n_{1})\leq\log\frac{1}{\alpha}=o(\log
n).$

Thus it suffices to show

$\frac{\log(n/n_{1})}{\log\gamma}\log\frac{n_{1}s^{2}}{\log(n/n_{1})}=o\left(\log
n\right),$

which further reduces to proving that
$\max_{x\in[1/\beta^{\prime},1/\alpha]}g(x)=o(\log n)$, where

$g(x)=\frac{\log x}{\log\frac{x\log x}{nps^{2}}}\log\frac{ns^{2}}{x\log x},$

since $\gamma=O\left(\frac{x\log x}{nps^{2}}\right)$ for
$x=n/n_{1}\in[1/\beta^{\prime},1/\alpha]$. To this end, let

$\delta=\frac{1}{\log\left(\log n/\log(1/\alpha)\right)}=o(1),$

where the last equality holds because $\log(1/\alpha)=(1+o(1))\log(1/p)=o(\log
n)$ by the choice of $\alpha$ and the assumption that $p=n^{-o(1)}$. Let

$\phi(x)=\log x\log\frac{ns^{2}}{x\log x}-\log\frac{x\log
x}{nps^{2}}\delta\log n.$

It is sufficient to show that for all $x\in[1/\beta^{\prime},1/\alpha]$,
$\phi(x)\leq 0$, which immediately implies that $g(x)\leq\delta\log n=o(\log
n)$.

Taking derivative of $\phi(x)$, we get that

$\displaystyle\phi^{\prime}(x)$
$\displaystyle=\frac{1}{x}\log\frac{ns^{2}}{x\log x}-\frac{\log
x}{x}\left(1+\frac{1}{\log x}\right)-\frac{1}{x}\left(1+\frac{1}{\log
x}\right)\delta\log n$ $\displaystyle=\frac{1}{x}\left(\log(ns^{2})-2\log
x-\log\log x-1-\delta\log n-\frac{\delta\log n}{\log x}\right).$

By assumption that $ns^{2}\alpha=(2-\epsilon)\log n$, we get that

$\log(ns^{2})\leq\log(2\log n)+\log\frac{1}{\alpha}=o(\delta\log n),$

where the last equality uses the fact that $\frac{\log(1/\alpha)}{\delta\log
n}=\frac{\log(1/\alpha)}{\log n}\log\frac{\log n}{\log(1/\alpha)}=o(1).$

Moreover, $\beta^{\prime}=o(1)$ and hence $x=\omega(1)$. Therefore,
$\phi^{\prime}(x)\leq 0$ for all $x\in[1/\beta^{\prime},1/\alpha]$. Hence, to
show $\phi(x)\leq 0$, it suffices to prove $\phi(1/\beta^{\prime})\leq 0$.
Note that

$\displaystyle\phi(1/\beta^{\prime})$
$\displaystyle=\log\frac{1}{\beta^{\prime}}\log\frac{ns^{2}}{(1/\beta^{\prime})\log(1/\beta^{\prime})}-\log\frac{(1/\beta^{\prime})\log(1/\beta^{\prime})}{nps^{2}}\delta\log
n$
$\displaystyle=\log\frac{1}{\beta^{\prime}}\log\frac{ns^{2}}{(200+o(1))nps^{2}}-\log\frac{(200+o(1))nps^{2}}{nps^{2}}\delta\log
n$
$\displaystyle=\log\frac{1}{\beta^{\prime}}\log\frac{1}{(200+o(1))p}-\log\left(200+o(1)\right)\delta\log
n\leq 0,$

where the last inequality holds because

$\frac{1}{\delta}\log\frac{1}{\beta^{\prime}}\leq\log\frac{200nps^{2}}{\log(nps^{2})}\log\frac{\log
n}{\log(1/\alpha)}\leq O\left(\left(\log\frac{\log
n}{\log(1/p)}\right)^{2}\right)=o\left(\frac{\log n}{\log(1/p)}\right),$

where we used the fact that $nps^{2}=O(\log n/\log(1/p))$ and
$\log(1/\alpha)=(1+o(1))\log(1/p)$ when $p=o(1)$.

##  Appendix B Supplementary Proofs for Section 5

###  B.1 Proof of Proposition 3: Long orbits

Fix any $\sigma=\pi^{-1}\circ{\widetilde{\pi}}$. Since
$\\{X_{O}\\}_{O\notin{\mathcal{O}}_{k}}$ are mutually independent, it follows
that

$\displaystyle\mathbb{E}_{{\mathcal{Q}}}\left[\prod_{O\notin{\mathcal{O}}_{k}}X_{O}\right]$
$\displaystyle=\prod_{O\notin{\mathcal{O}}_{k}}\mathbb{E}_{{\mathcal{Q}}}\left[X_{O}\right]=\prod_{O\notin{\mathcal{O}}_{k}}\left(1+\rho^{2|O|}\right).$

For any $O_{ij}\notin{\mathcal{O}}_{k}$, we have $i$ or $j$ is from node orbit
with length larger than $k$, or $O_{ij}$ has length larger than $k$. By
Section 5.1, we know that
$|O_{ij}|\geq\left\lceil\frac{k+1}{2}\right\rceil{}$. It follows that

$\displaystyle\mathbb{E}_{{\mathcal{Q}}}\left[\prod_{O\notin{\mathcal{O}}_{k}}X_{O}\right]\leq\prod_{m=\left\lceil\frac{k+1}{2}\right\rceil{}}^{\binom{n}{2}}\left(1+\rho^{2|O|}\right)^{N_{m}}$
$\displaystyle\overset{(a)}{\leq}\left(1+\rho^{k}\right)^{\sum_{m\geq\left\lceil\frac{k+1}{2}\right\rceil{}}^{\binom{n}{2}}N_{m}}$
$\displaystyle\overset{(b)}{\leq}\left(1+\rho^{k}\right)^{\frac{n^{2}}{k}}.$

where $(a)$ holds, since $1+\rho^{2m}$ decreases when $m$ increases, and
$1+\rho^{2m}\leq 1+\rho^{k}$ for any
$m\geq\left\lceil\frac{k+1}{2}\right\rceil{}$; $(b)$ holds since the total
number of edges is $\binom{n}{2}$, and the total number of edge orbits with
length at least $\left\lceil\frac{k+1}{2}\right\rceil{}$ is at most
$\frac{\binom{n}{2}}{\left\lceil\frac{k+1}{2}\right\rceil{}}\leq\frac{n^{2}}{k}$.

###  B.2 Proof of Proposition 4: Incomplete orbits

Fix any $\sigma=\pi^{-1}\circ{\widetilde{\pi}}$. Since edge orbits are
disjoint, and $A_{i,j}$ and $B_{ij}$ are i.i.d. ${\rm Bern}(ps)$ across all
$1\leq i<j\leq n$ under ${\mathcal{Q}}$, it follows that
$\\{A_{ij},B_{\pi(i)\pi(j)}\\}_{(i,j)\in O}$ are mutually independent across
different edge orbits $O$ under ${\mathcal{Q}}$. Recall that an edge orbit
$O\in{\mathcal{J}}_{k}$ if and only if $A_{ij}=B_{\pi(i)\pi(j)}=1$ for all
$(i,j)\in O$. Therefore, conditional on ${\mathcal{J}}_{k}={\mathcal{J}}$,
$\\{A_{ij},B_{\pi(i)\pi(j)}\\}_{(i,j)\in O}$ are independent across all edge
orbits $O\in{\mathcal{O}}_{k}\backslash{\mathcal{J}}$. In particular, the
distribution of $\\{A_{ij},B_{\pi(i)\pi(j)}\\}_{(i,j)\in O}$ for
$O\notin{\mathcal{J}}$ conditional on ${\mathcal{J}}_{k}={\mathcal{J}}$ is the
same as that conditional on $O\notin{\mathcal{J}}_{k}$. Since $X_{O}$ is a
function of $\\{A_{ij},B_{\pi(i)\pi(j)}\\}_{(i,j)\in O}$, it follows that

$\displaystyle\mathbb{E}_{{\mathcal{Q}}}\left[\prod_{O\in{\mathcal{O}}_{k}\backslash{\mathcal{J}}_{k}}X_{O}\;\Big{|}\;{\mathcal{J}}_{k}={\mathcal{J}}\right]=\prod_{O\in{\mathcal{O}}_{k}\backslash{\mathcal{J}}}\mathbb{E}_{{\mathcal{Q}}}\left[X_{O}\;\Big{|}\;{\mathcal{J}}_{k}={\mathcal{J}}\right]=\prod_{O\in{\mathcal{O}}_{k}\backslash{\mathcal{J}}}\mathbb{E}_{{\mathcal{Q}}}\left[X_{O}\;\Big{|}\;O\notin{\mathcal{J}}_{k}\right].$

Therefore, to prove Proposition 4, it suffices to show
$\mathbb{E}_{{\mathcal{Q}}}\left[X_{O}\;\Big{|}\;O\notin{\mathcal{J}}_{k}\right]\leq
1$. Note that

$\displaystyle\mathbb{E}_{{\mathcal{Q}}}\left[X_{O}|O\notin{\mathcal{J}}_{k}\right]$
$\displaystyle=\frac{\mathbb{E}_{{\mathcal{Q}}}\left[X_{O}{\mathbf{1}_{\left\\{{O\notin{\mathcal{J}}_{k}}\right\\}}}\right]}{\mathbb{P}\left(O\notin{\mathcal{J}}_{k}\right)}=\frac{\mathbb{E}_{{\mathcal{Q}}}\left[X_{O}\right]-\mathbb{E}_{{\mathcal{Q}}}\left[X_{O}{\mathbf{1}_{\left\\{{O\in{\mathcal{J}}_{k}}\right\\}}}\right]}{1-\mathbb{P}\left(O\in{\mathcal{J}}_{k}\right)}.$

Recall that $O\in{\mathcal{J}}_{k}$ if and only if
$A_{ij}=1,B_{\pi(i)\pi(j)}=1$ for all $(i,j)\in O$, in which case
$X_{O}=\left(\frac{1}{p}\right)^{2|O|}$. Thus
$\mathbb{P}\left\\{O\in{\mathcal{J}}_{k}\right\\}=\left(ps\right)^{2|O|}$ and

$\mathbb{E}_{{\mathcal{Q}}}\left[X_{O}{\mathbf{1}_{\left\\{{O\in{\mathcal{J}}_{k}}\right\\}}}\right]=\left(\frac{1}{p}\right)^{2|O|}\left(ps\right)^{2|O|}=s^{2|O|}.$

Recall that $\mathbb{E}_{{\mathcal{Q}}}\left[X_{O}\right]=1+\rho^{2|O|}$,
where $\rho=\frac{s(1-p)}{1-ps}$. Combining this with the last two displayed
equation yields that

$\displaystyle\mathbb{E}_{{\mathcal{Q}}}\left[X_{O}|O\notin{\mathcal{J}}_{k}\right]=\frac{1+\rho^{2|O|}-s^{2|O|}}{1-\left(ps\right)^{2|O|}}=\frac{1-s^{2|O|}\left(1-\left(\frac{1-p}{1-ps}\right)^{2|O|}\right)}{1-\left(ps\right)^{2|O|}}\leq
1,$

where the last inequality holds by the following claim: if $p\leq 1/2$ and
$s\leq 1/2$, then

$\displaystyle 1-\left(\frac{1-p}{1-ps}\right)^{2|O|}\geq
p^{2|O|},\quad\forall|O|\geq 1.$ (98)

Indeed, as $|O|$ increases, $1-\left(\frac{1-p}{1-ps}\right)^{2|O|}$ increases
while $p^{2|O|}$ decreases, so it suffices to verify (98) for $|O|=1$. When
$|O|=1$, we have $1-\left(\frac{1-p}{1-ps}\right)^{2}\geq
p^{2}\iff\left(1-ps\right)^{2}\geq\frac{1-p}{1+p}$, which holds when
$p\leq\frac{1}{2}$ and $s\leq\frac{1}{2}$.

###  B.3 Proof of Proposition 5: Averaging over orbit lengths

In the following proof, for any $t\in{\mathbb{N}}$, denote the $t$th harmonic
number by ${h}_{t}\triangleq\sum_{\ell=1}^{t}\frac{1}{\ell}$ and
${h}_{0}\triangleq 0$.

Under the assumption of $s\leq 0.1$, we have $2ms^{m}\leq 0.04$ when $m\geq 2$
and $2ms^{m}\leq 0.2$ for $m=1$. Thus, for any $1\leq m\leq k$,

$\displaystyle
1+s^{m}n_{m}{\mathbf{1}_{\left\\{{m:\mathrm{even}}\right\\}}}+2s^{2m}\sum_{\ell\leq
m}\ell n_{\ell}+s^{4m}mn_{2m}{\mathbf{1}_{\left\\{{2m\leq k}\right\\}}}\leq
1+1.04s^{m}\sum_{\ell\leq 2m}n_{\ell}{\mathbf{1}_{\left\\{{\ell\leq
k}\right\\}}}.$ (99)

Hence, to prove (71), it suffices to show, for $s\leq 0.1$:

$\displaystyle\mathbb{E}\left[\prod_{m=1}^{k}\left(1+1.04s^{m}\sum_{\ell\leq
2m}n_{\ell}{\mathbf{1}_{\left\\{{\ell\leq
k}\right\\}}}\right)^{n_{m}}\right]=O(1).$ (100)

To prove (72), it suffices to show, for $s=o(1)$:

$\displaystyle\mathbb{E}\left[\prod_{m=1}^{k}\left(1+1.04s^{m}\sum_{\ell\leq
2m}n_{\ell}{\mathbf{1}_{\left\\{{\ell\leq
k}\right\\}}}\right)^{n_{m}}\right]=1+o(1).$ (101)

Pick $\eta=\log k\sqrt{\log\left(n/k\right)}$. We can write
$\mathbb{E}\left[\prod_{m=1}^{k}\left(1+1.04s^{m}\sum_{\ell\leq
2m}n_{\ell}{\mathbf{1}_{\left\\{{\ell\leq k}\right\\}}}\right)^{n_{m}}\right]$
as $\text{(I)}+\text{(II)}$ where

(I)
$\displaystyle=\mathbb{E}\left[\prod_{m=1}^{k}\left(1+1.04s^{m}\sum_{\ell\leq
2m}n_{\ell}{\mathbf{1}_{\left\\{{\ell\leq
k}\right\\}}}\right)^{n_{m}}{\mathbf{1}_{\left\\{{\sum_{\ell=1}^{k}n_{\ell}<\eta{h}_{k}}\right\\}}}\right],$
(II)
$\displaystyle=\mathbb{E}\left[\prod_{m=1}^{k}\left(1+1.04s^{m}\sum_{\ell\leq
2m}n_{\ell}{\mathbf{1}_{\left\\{{\ell\leq
k}\right\\}}}\right)^{n_{m}}{\mathbf{1}_{\left\\{{\sum_{\ell=1}^{k}n_{\ell}\geq\eta{h}_{k}}\right\\}}}\right].$

To bound (I), we first apply (122) in Lemma 13 and get:

$\mathrm{TV}\left({\mathcal{L}}\left(n_{1},\ldots,n_{k}\right),{\mathcal{L}}\left(Z_{1},\ldots,Z_{k}\right)\right)\leq
F\left(\frac{n}{k}\right),$

where ${\mathcal{L}}$ denotes the law of random variables,
$Z_{\ell}{\stackrel{{\scriptstyle\text{ind.}}}{{\sim}}}{\rm
Poi}(\frac{1}{\ell})$, and $\log
F(n/k)=-(1+o(1))\frac{n}{k}\log\left(\frac{n}{k}\right)$ when $k=o(n)$, with
$o(1)$ depending only on $k/n$. Then, we have

(I)
$\displaystyle\leq\mathbb{E}\left[\prod_{m=1}^{k}\left(1+1.04s^{m}\sum_{\ell\leq
2m}Z_{\ell}{\mathbf{1}_{\left\\{{\ell\leq
k}\right\\}}}\right)^{Z_{m}}\right]+2F\left(\frac{n}{k}\right)\left(1+1.04s\eta{h}_{k}\right)^{\eta{h}_{k}}.$
(102)

Here the second term satisfies

$\displaystyle
F\left(\frac{n}{k}\right)\left(1+1.04s\eta{h}_{k}\right)^{\eta{h}_{k}}$
$\displaystyle\overset{(a)}{\leq}\exp\left(-(1+o(1))\frac{n}{k}\log\left(\frac{n}{k}\right)+1.04s\eta^{2}{h}_{k}^{2}\right)\overset{(b)}{=}o(1),$

where $(a)$ holds because for $x\geq 0$, $\log(1+x)\leq x$; $(b)$ holds since
${h}_{k}\leq\log k+1$, and $k(\log
k)^{2}\eta^{2}=o\left(n\log\left(\frac{n}{k}\right)\right)$ under our
assumption of $k(\log k)^{4}=o(n)$.

To bound (II), applying (121) in Lemma 12, we get that

(II)
$\displaystyle\leq\mathbb{E}\left[\prod_{m=1}^{k}\left(1+1.04s^{m}\sum_{\ell\leq
2m}Z_{\ell}{\mathbf{1}_{\left\\{{\ell\leq
k}\right\\}}}\right)^{Z_{m}}{\mathbf{1}_{\left\\{{\sum_{\ell=1}^{k}Z_{\ell}\geq\eta{h}_{k}}\right\\}}}\right]e^{{h}_{k}}$
$\displaystyle\leq\mathbb{E}\left[\prod_{m=1}^{k}\left(1+1.04s^{m}\sum_{\ell\leq
2m}Z_{\ell}{\mathbf{1}_{\left\\{{\ell\leq
k}\right\\}}}\right)^{Z_{m}}\exp\left({\frac{\sum_{\ell=1}^{k}Z_{\ell}}{\eta}}\right)\right].$
(103)

Since $\eta=\log k\sqrt{\log(n/k)}=\omega(\log k)$, for $s=0.1$, the desired
(100) follows from applying (104) in Lemma 8 to (102) and (103); for $s=o(1)$,
the desired (101) follows from applying (105) in Lemma 8 to (102) and (103).
Hence, our desired result follows.

######  Lemma 8.

Suppose $\eta=\omega(\log k)$. If $s\leq 0.1$,

$\displaystyle\mathbb{E}\left[\prod_{m=1}^{k}\left(1+1.04s^{m}\sum_{\ell\leq
2m}Z_{\ell}{\mathbf{1}_{\left\\{{\ell\leq
k}\right\\}}}\right)^{Z_{m}}\exp\left(\frac{\sum_{\ell=1}^{k}Z_{\ell}}{\eta}\right)\right]=O(1).$
(104)

In particular, if $s=o(1)$,

$\displaystyle\mathbb{E}\left[\prod_{m=1}^{k}\left(1+1.04s^{m}\sum_{\ell\leq
2m}Z_{\ell}{\mathbf{1}_{\left\\{{\ell\leq
k}\right\\}}}\right)^{Z_{m}}\exp\left(\frac{\sum_{\ell=1}^{k}Z_{\ell}}{\eta}\right)\right]=1+o(1).$
(105)

To show Lemma 8 we need the following elementary result (proved at the end of
this subsection):

######  Lemma 9.

Let $a,b,d,\alpha,\lambda>0$ such that $be^{\alpha+1}\lambda<\frac{1}{4}$. Let
$X\sim{\rm Poi}(\lambda)$. Then

$\displaystyle\mathbb{E}\left[\left(a+bX\right)^{X+d}\exp\left(\alpha
X\right)\right]$ $\displaystyle\leq
a^{d}\left(1+2be^{\alpha+1}\lambda\right)^{d}\exp\left(\lambda\left(ae^{\alpha}\left(1+2be^{\alpha+1}\lambda\right)-1\right)\right)$
$\displaystyle+27\exp\left(-\lambda\right)\max\big{\\{}\left(4bd\right)^{d},a^{d}\big{\\}}.$
(106)

Moreover, if $d=0$, and $a,b,\alpha,\lambda$ are fixed constants such that
$be^{\alpha+1}\lambda<1$,

$\displaystyle\mathbb{E}\left[\left(a+bX\right)^{X}\exp\left(\alpha
X\right)\right]=O(1).$ (107)

In particular, if $d=0$, $a=1$, $b=o(1)$, $\alpha=o(1)$, and $\lambda$ is some
fixed constant,

$\displaystyle\mathbb{E}\left[\left(1+bX\right)^{X}\exp\left(\alpha
X\right)\right]=1+o(1).$ (108)

Before proceeding to the proof of Lemma 8, we pause to note that a direct
application of (107) (with $X=Z_{1}+\ldots+Z_{k}$, $a=1$, $b=1.04s$,
$\alpha=1/\eta$) yields the condition $s\log k=O(1)$. Since $k$ will be chosen
to be $\Theta(\log n)$ eventually, this translates into the statement that
strong detection is impossible if $s=O(\frac{1}{\log\log n})$. In order to
improve this to $s=O(1)$, the key idea is to partition the product over $[k]$
in (104) into subsets and recursively peel off the expectation backwards by
repeated applications of Lemma 9.

###### Proof of Lemma 8.

Let $m_{0}=0$, $m_{1}=1$, and iteratively define

$\displaystyle m_{\ell}=\left\lfloor\exp\left(3\times
2^{-2\ell+1}s^{-\frac{m_{\ell-1}}{2}}\right)\right\rfloor{},\quad
2\leq\ell\leq r,$ (109)

where $r$ is the integer such that $m_{r-1}<k\leq m_{r}$. Note that for $s\leq
0.1$, we have $m_{2}\geq 3=3m_{1}$; moreover, if $s=o(1)$, we have
$m_{2}=\omega(1)$. Note that it is possible that $m_{r-1}$ is very close to
$k$ and $m_{r}$ is much larger than $k$, especially when $s=o(1)$. To simplify
the argument, define $K=\min\\{k^{2},m_{r}\\}$. Since the quantity inside the
expectation in (104) increases in $k$, it suffices to bound

$\mathbb{E}\left[\prod_{m=1}^{K}\left(1+1.04s^{m}\sum_{\ell\leq
2m}Z_{\ell}{\mathbf{1}_{\left\\{{\ell\leq
K}\right\\}}}\right)^{Z_{m}}\exp\left(\frac{\sum_{\ell=1}^{K}Z_{\ell}}{\eta}\right)\right]$

and we can assume, without loss of generality, that $k=\omega(1)$.

Next we partition $[K]$ into the following $r$ subsets:

$\\{m_{0}+1,\cdots,m_{1}\\},\\{m_{1}+1,\cdots,m_{2}\\},\cdots,\\{m_{r-1}+1,\cdots,K\\}.$

For $1\leq\ell\leq r$, define

$A_{\ell}\triangleq\sum_{t=m_{\ell-1}+1}^{m_{\ell}}Z_{t}{\mathbf{1}_{\left\\{{t\leq
K}\right\\}}},\quad
B_{\ell}\triangleq\sum_{t=m_{\ell-1}+1}^{2m_{\ell-1}}Z_{t}{\mathbf{1}_{\left\\{{t\leq
K}\right\\}}},\quad
C_{\ell}\triangleq\sum_{t=2m_{\ell-1}+1}^{m_{\ell}}Z_{t}{\mathbf{1}_{\left\\{{t\leq
K}\right\\}}},\quad M_{\ell}\triangleq\sum_{t=1}^{\ell}A_{t},$

and $B_{r+1}=0$. Note that $A_{\ell}=B_{\ell}+C_{\ell}$ and, by the definition
of $r$, $M_{r}=\sum_{t=1}^{K}Z_{t}$. Furthermore, for $1\leq\ell\leq r$,

$\displaystyle C_{\ell}+B_{\ell+1}$
$\displaystyle{\stackrel{{\scriptstyle\text{ind.}}}{{\sim}}}{\rm
Poi}\left(\lambda_{\ell}\right),\quad\mathrm{where\
}\lambda_{\ell}\triangleq{h}_{2m_{\ell}\wedge K}-{h}_{2m_{\ell-1}\wedge K}\,.$

Then we can upper bound (104) as

$\displaystyle(\ref{eq:s_constant})$
$\displaystyle\leq\mathbb{E}\left[\prod_{\ell=1}^{r}\left(\prod_{m=m_{\ell-1}+1}^{m_{\ell}}\left(1+1.04s^{m_{\ell-1}+1}\left(M_{\ell}+B_{\ell+1}\right)\right)^{Z_{m}}\right)\exp\left(\frac{M_{r}}{\eta}\right)\right]$
$\displaystyle=\mathbb{E}\left[\prod_{\ell=1}^{r}\left(1+1.04s^{m_{\ell-1}+1}\left(M_{\ell}+B_{\ell+1}\right)\right)^{A_{\ell}}\exp\left(\frac{M_{r}}{\eta}\right)\right].$
(110)

Define the sequence $\\{\alpha_{\ell}\\}_{\ell=1}^{r}$ and
$\\{\beta_{\ell}\\}_{\ell=1}^{r}$ backward recursively by
$\alpha_{r}=\frac{1}{\eta}$, $\beta_{r}=0$ and for $2\leq\ell\leq r$,

$\displaystyle\alpha_{\ell-1}$
$\displaystyle\triangleq\alpha_{\ell}+1.04\lambda_{\ell}e^{\alpha_{\ell}}s^{m_{\ell-1}+1}\left(1+2.08s^{m_{\ell-1}+1}e^{\alpha_{\ell}+1}\lambda_{\ell}\right)+\log\left(1+2.08s^{m_{\ell-1}+1}e^{\alpha_{\ell}+1}\lambda_{\ell}\right),$
(111) $\displaystyle\beta_{\ell-1}$
$\displaystyle\triangleq\beta_{\ell}+\lambda_{\ell}\left(e^{\alpha_{\ell}}\left(1+2.08s^{m_{\ell-1}+1}e^{\alpha_{\ell}+1}\lambda_{\ell}\right)-1\right).$
(112)

For $1\leq\ell\leq r$, define

$\displaystyle S_{\ell}$
$\displaystyle\triangleq\mathbb{E}\biggl{[}\left(\prod_{t=1}^{\ell-1}\left(1+1.04s^{m_{t-1}+1}\left(M_{t}+B_{t+1}\right)\right)^{A_{t}}\right)$
$\displaystyle~{}~{}~{}~{}\left(1+1.04s^{m_{\ell-1}+1}\left(M_{\ell}+B_{\ell+1}\right)\right)^{A_{\ell}+B_{\ell+1}}e^{\alpha_{\ell}\left(M_{\ell}+B_{\ell+1}\right)+\beta_{\ell}}\biggr{]},$
(113)

Since $B_{r+1}=0$, it follows that $S_{r}$ is precisely the RHS of (110) and
our goal is to show $S_{r}=O(1)$. This is accomplished by the following
sequence of claims:

  1. (C1)

For any $2\leq\ell\leq r$, $\left(\log
m_{\ell}\right)s^{m_{\ell-1}+1}\leq\left(\log
m_{\ell}\right)^{2}s^{m_{\ell-1}+1}\leq 9s\times 2^{-4\ell+2}$;

  2. (C2)

For any $2\leq\ell\leq r$, $m_{\ell}\geq m_{\ell-1}^{2}$ and
$m_{\ell}\geq\left(m_{2}\right)^{2^{\ell-2}}$;

  3. (C3)

For any $2\leq\ell\leq r$, $\left(\log
m_{\ell+1}\right)s^{m_{\ell}}\leq\frac{1}{8}\left(\log
m_{\ell}\right)s^{m_{\ell-1}}$;

  4. (C4)

For any $2\leq\ell\leq r$, $\lambda_{\ell}\leq\log m_{\ell}$, and
$\sum_{\ell=2}^{r}\exp\left(-\lambda_{\ell}\right)=O(1)$, in particular, if
$s=o(1)$, $\sum_{\ell=2}^{r}\exp\left(-\lambda_{\ell}\right)=o(1)$;

  5. (C5)

For $1\leq\ell\leq r$, $\alpha_{\ell}\leq\frac{2}{5}$, and $\beta_{1}\leq 3$,
in particular, if $s=o(1)$, for $1\leq\ell\leq r$, $\alpha_{\ell}=o(1)$, and
$\beta_{1}=o(1)$;

  6. (C6)

For any $2\leq\ell\leq r$, $S_{\ell}\leq
S_{\ell-1}\left(1+27\exp\left(-\lambda_{\ell}\right)\right)$, and
$S_{r}=O(1)$, in particular, if $s=o(1)$, $S_{r}=1+o(1)$.

We finish the proof by verifying these claims:

  * •

Proof of (C1): This follows from the definition of $m_{\ell}$ given in (109).

  * •

Proof of (C2): It suffices to prove the first inequality. We proceed by
induction. For the base case of $\ell=2$, recall that we have shown under the
assumption $s\leq 0.1$, we have $m_{2}\geq 3m_{1}\geq m_{1}^{2}$. By (109), we
can get that

$\frac{m_{3}}{m_{2}^{2}}\geq\frac{1}{m_{2}^{2}}\left(\exp\left(3\times
2^{-5}0.1^{-\frac{m_{2}}{2}}\right)-1\right)\geq 2,$

where the last inequality holds because $m_{2}\geq 3$ and
$x\mapsto\frac{1}{x^{2}}\left(\exp\left(3\times
2^{-5}0.1^{-\frac{x}{2}}\right)-1\right)$ increases for $x\geq 3$. Then we
have $m_{3}\geq 2m_{2}^{2}\geq 6m_{2}$ given $m_{2}\geq 3$.

Fix any $4\leq\ell\leq r$, suppose we have shown for every $2\leq
t\leq\ell-1$, $m_{t}\geq m_{t-1}^{2}$. By (109),
$m_{\ell-1}\leq\exp\left(3\times 2^{-2\ell+3}s^{-\frac{m_{\ell-2}}{2}}\right)$
and

$m_{\ell}\geq\exp\left(3\times
2^{-2\ell+1}s^{-\frac{m_{\ell-1}}{2}}\right)-1\geq\exp\left(3\times
2^{-2\ell+1}s^{-\frac{6m_{\ell-2}}{2}}\right)-1,$

where the last inequality holds because $m_{\ell-1}\geq 6m_{\ell-2}$ for
$\ell\geq 4$ following from $m_{3}\geq 6m_{2}$ and the induction hypothesis
$m_{\ell-1}\geq m_{\ell-2}^{2}$. Then we have

$\displaystyle\frac{m_{\ell}}{m_{\ell-1}}\geq\exp\left(3\times
2^{-2\ell+3}s^{-\frac{m_{\ell-2}}{2}}\left(2^{-2}s^{-\frac{5}{2}m_{\ell-2}}-1\right)\right)-1$
$\displaystyle\overset{(a)}{\geq}\exp\left(3\times
2^{-2\ell+3}s^{-\frac{m_{\ell-2}}{2}}\times 2\right)-1$
$\displaystyle\overset{(b)}{\geq}m_{\ell-1}^{2}-1\overset{(c)}{\geq}m_{\ell-1},$

where $(a)$ holds by $2^{-2}s^{-\frac{5}{2}m_{\ell-2}}\geq 3$ given $s\leq
0.1$ and $m_{\ell-2}\geq 3$; $(b)$ holds by $m_{\ell-1}\leq\exp\left(3\times
2^{-2\ell+3}s^{-\frac{m_{\ell-2}}{2}}\right)$; $(c)$ holds by $m_{\ell-1}\geq
6m_{\ell-2}\geq 18$ for $\ell\geq 4$ given $m_{2}\geq 3$. Hence, (C2) follows.

  * •

Proof of (C3): We prove a stronger statement: $\left(\log
m_{\ell+1}\right)^{2}s^{m_{\ell}}\leq\frac{1}{8}\left(\log
m_{\ell}\right)^{2}s^{m_{\ell-1}}$ for $2\leq\ell\leq r$. Since $\left(\log
m_{\ell+1}\right)^{2}s^{m_{\ell}}\leq 9\times 2^{-4\ell-2}$ by (C1), it
suffices to show $\left(\log m_{\ell}\right)^{2}s^{m_{\ell-1}}\geq 9\times
2^{-4\ell+1}$ for $\ell\geq 2$. For $\ell=2$, we have $\left(\log
m_{2}\right)^{2}s^{m_{1}}\geq 9\times 2^{-7}$, since $m_{2}\geq 3$ and $s\leq
0.1$. By (109), we have

$m_{\ell}\geq\exp\left(3\times
2^{-2\ell+1}s^{-\frac{m_{\ell-1}}{2}}\right)-1\geq\exp\left(3\times
2^{-2\ell+\frac{1}{2}}s^{-\frac{m_{\ell-1}}{2}}\right),$

where the last inequality holds because $\exp(x)-1\geq\exp(x/\sqrt{2})$ for
$x\geq 1.22$, and $3\times 2^{-2\ell+1}s^{-\frac{m_{\ell-1}}{2}}\geq\ln
m_{\ell}\geq 2^{\ell-2}\ln m_{2}\geq 2$ for $\ell\geq 3$, by (C1), (C2), and
$m_{2}\geq 3.$

  * •

Proof of (C4): Note that $2m_{r-1}\leq m_{r}$ by (C2). Moreover,
$2m_{r-1}<k^{2}$ as $m_{r-1}<k$ and $k=\omega(1)$. Since
$K=\min\\{k^{2},m_{r}\\}$, it follows that $2m_{r-1}\leq K\leq m_{r}$.
Therefore, $\lambda_{r}={h}_{K}-{h}_{2m_{r-1}}$ and
$\lambda_{\ell}={h}_{2m_{\ell}}-{h}_{2m_{\ell-1}}$ for $1\leq\ell\leq r-1.$

Since for any $n,k\in{\mathbb{N}}$,
${h}_{n}-{h}_{k}\leq\int_{k}^{n}\frac{1}{x}\mathrm{d}x\leq\log\frac{n}{k},$
then for any $2\leq\ell\leq r$,

$\lambda_{\ell}\leq{h}_{2m_{\ell}}-{h}_{2m_{\ell-1}}\leq\log\frac{m_{\ell}}{m_{\ell-1}}\leq\log
m_{\ell},$

where the last inequality holds due to $m_{\ell-1}\geq 1$ for $\ell\geq 2.$

Conversely, since for any $n,k\in{\mathbb{N}}$,
${h}_{n}-{h}_{k}\geq\int_{k+1}^{n+1}\frac{1}{x}\mathrm{d}x\geq\log\frac{n+1}{k+1}\geq\log\frac{n}{k}-1$,
it follows that for any $2\leq\ell\leq r-1$,

$\lambda_{\ell}={h}_{2m_{\ell}}-{h}_{2m_{\ell-1}}\geq\log\left(\frac{m_{\ell}}{m_{\ell-1}}\right)-1,$

and $\lambda_{r}\geq\log\frac{K}{2m_{r-1}}-1$. If $K=k^{2}$, then $K\geq
km_{r-1}$ and thus $\lambda_{r}\geq\log\frac{k}{2}-1$; otherwise, $K=m_{r}$
and thus $\lambda_{r}\geq\log\frac{m_{r}}{2m_{r-1}}-1$. Hence, we get that

$\displaystyle\sum_{\ell=2}^{r}\exp\left(-\lambda_{\ell}\right)$
$\displaystyle\leq\sum_{\ell=2}^{r}\frac{2em_{\ell-1}}{m_{\ell}}+\frac{2e}{k}\overset{(a)}{\leq}\frac{2e}{m_{2}}+\sum_{\ell=3}^{r}\frac{2e}{m_{\ell-1}}+o(1)\overset{(b)}{\leq}\frac{3e}{m_{2}}+o(1)=O(1),$

where $(a)$ holds by $m_{1}=1$, $k=\omega(1)$, and (C2) so that $m_{\ell}\geq
m_{\ell-1}^{2}$ for $\ell\geq 2$; $(b)$ holds because in view of (C2),
$m_{\ell}\geq\left(m_{2}\right)^{2^{\ell-2}}$ and $m_{2}\geq 3$, so that

$\sum_{\ell=3}^{r-1}\frac{1}{m_{\ell-1}}\leq\sum_{\ell=3}^{r-1}\frac{1}{(m_{2})^{2^{\ell-2}}}\leq\sum_{\ell=2}^{\infty}\frac{1}{(m_{2})^{\ell}}=\frac{1}{m_{2}^{2}}\frac{1}{1-m_{2}^{-1}}\leq\frac{1}{2m_{2}}.$

In particular, if $s=o(1)$, then $m_{2}=\omega(1)$ and we have

$\sum_{\ell=2}^{r}\exp\left(-\lambda_{\ell}\right)\leq\frac{3e}{m_{2}}+o(1)=o(1).$

Hence, (C4) follows.

  * •

Proof of (C5): For $2\leq\ell\leq r$, let $c=1.04$, we define

$\psi_{\ell}\triangleq(2+4e)c\left(\log
m_{\ell}\right)s^{m_{\ell-1}+1}+8ec^{2}\left(\log
m_{\ell}\right)^{2}s^{2m_{\ell-1}+2}.$

We prove $\alpha_{\ell}\leq\frac{2}{5}$ for $1\leq\ell\leq r$ by induction.
Since $\eta=\omega(1)\geq 6$, we have $\alpha_{r}=\frac{1}{\eta}<\frac{2}{5}$.
Fix any $2\leq\ell\leq r$. Suppose we have shown for any $\ell\leq t\leq r$,
$\alpha_{t}\leq\frac{2}{5}$. Then $e^{\alpha_{t}}\leq 1+2\alpha_{t}$,
$e^{2\alpha_{t}}\leq 1+4\alpha_{t}$. Since $\log(1+x)\leq x$ for $x\geq 0$, by
(111) we have

$\displaystyle\alpha_{t-1}$
$\displaystyle\leq\alpha_{t}+\left(1+2e\right)c\lambda_{t}e^{\alpha_{t}}s^{m_{t-1}+1}+2ec^{2}s^{2m_{t-1}+2}e^{2\alpha_{t}}\lambda_{t}^{2}$
$\displaystyle\leq\alpha_{t}+\left(1+2e\right)c\lambda_{t}\left(1+2\alpha_{t}\right)s^{m_{t-1}+1}+2ec^{2}s^{2m_{t-1}+2}\left(1+4\alpha_{t}\right)\lambda_{t}^{2}$
$\displaystyle\leq\alpha_{t}\left(1+\psi_{t}\right)+\frac{1}{2}\psi_{t},$

where the last inequality holds by (C4). By the induction hypothesis,

$\displaystyle\alpha_{\ell-1}$
$\displaystyle\leq\alpha_{r}\prod_{t=\ell}^{r}\left(1+\psi_{t}\right)+\frac{1}{2}\sum_{t=\ell}^{r}\psi_{t}\prod_{j=\ell}^{t-1}\left(1+\psi_{j}\right)$
$\displaystyle\leq\left(\alpha_{r}+\frac{1}{2}\sum_{t=\ell}^{r}\psi_{t}\right)\exp\left(\sum_{t=\ell}^{r}\psi_{t}\right)\overset{(a)}{<}\frac{9}{7}\alpha_{r}+\frac{36}{49}\psi_{\ell}\overset{(b)}{<}\frac{2}{5},$
(114)

where $(a)$ holds by
$\exp\left(\sum_{t=\ell}^{r}\psi_{t}\right)\leq\frac{9}{7}$, since
$\sum_{t=\ell}^{r}\psi_{t}\leq\frac{8}{7}\psi_{\ell}$ following from
$\psi_{t+1}\leq\frac{1}{8}\psi_{t}$ by (C3), and $\psi_{\ell}\leq 0.2$ for
$\ell\geq 2$ because $\left(\log m_{\ell}\right)s^{m_{\ell-1}+1}\leq 9s\times
2^{-6}\leq 2^{-6}$ by (C1); $(b)$ holds because
$\alpha_{r}=\frac{1}{\eta}\leq\frac{1}{6}$ by $\eta=\omega(1)$ and
$\psi_{\ell}\leq 0.2$.

In particular, if $s=o(1)$, by (C3), we have
$\sum_{t=\ell}^{r}\psi_{t}\leq\frac{8}{7}\psi_{\ell}=o(1)$ because
$\psi_{\ell}=o(1)$ for $\ell\geq 2$ following from $\left(\log
m_{\ell}\right)s^{m_{\ell-1}+1}\leq 9s\times 2^{-4\ell+2}=o(1)$ by (C1) and
$s=o(1)$. Then for $2\leq\ell\leq r$, we have

$\alpha_{\ell-1}\leq\left(\alpha_{r}+\frac{1}{2}\sum_{t=\ell}^{r}\psi_{t}\right)\exp\left(\sum_{t=\ell}^{r}\psi_{t}\right)=\left(\alpha_{r}+o(1)\right)\left(1+o(1)\right)=o(1),$

where the last equality holds because $\alpha_{r}=\frac{1}{\eta}=o(1)$ given
$\eta=\omega(\log k)$.

Since we have shown that $\alpha_{\ell}\leq\frac{2}{5}$ for $1\leq\ell\leq r$,
it follows that $e^{\alpha_{\ell}}\leq 1+2\alpha_{\ell}$ and
$e^{2\alpha_{\ell}}\leq 1+4\alpha_{\ell}$. Then by (112), we can get that for
$2\leq\ell\leq r$,

$\displaystyle\beta_{\ell-1}$
$\displaystyle\leq\beta_{\ell}+\lambda_{\ell}\left\\{2\alpha_{\ell}+2ecs^{m_{\ell-1}+1}(1+4\alpha_{\ell})\lambda_{\ell}\right\\}$
$\displaystyle\overset{(a)}{\leq}\beta_{\ell}+2\alpha_{\ell}\lambda_{\ell}+\left(1+\frac{8}{5}\right)2ec\lambda_{\ell}^{2}s^{m_{\ell-1}+1}$
$\displaystyle\overset{(b)}{\leq}\beta_{\ell}+2\left(\frac{9}{7}\alpha_{r}+\frac{36}{49}\psi_{\ell+1}\right)\lambda_{\ell}+\frac{26}{5}ec\lambda_{\ell}^{2}s^{m_{\ell-1}+1}$
$\displaystyle\overset{(c)}{<}\beta_{\ell}+\frac{18}{7}\alpha_{r}\lambda_{\ell}+\frac{9}{49}\psi_{\ell}\log(m_{\ell})+\frac{26}{5}ec\left(\log
m_{\ell}\right)^{2}s^{m_{\ell-1}+1},$

where $(a)$ holds by $\alpha_{\ell}\leq\frac{2}{5}$; $(b)$ holds by (114) so
that $\alpha_{\ell}\leq\frac{9}{7}\alpha_{r}+\frac{36}{49}\psi_{\ell+1}$;
$(c)$ holds because $\lambda_{\ell}\leq\log m_{\ell}$ for $\ell\geq 2$ by (C4)
and $\psi_{\ell+1}\leq\frac{1}{8}\psi_{\ell}$ by (C3). Since $\left(\log
m_{\ell}\right)s^{m_{\ell-1}+1}\leq 9s\times 2^{-4\ell+2}\leq 2^{-6}$ by (C1),
it follows that

$\psi_{\ell}\leq(2+4e)c\left(\log
m_{\ell}\right)s^{m_{\ell-1}+1}+\frac{8ec^{2}}{2^{6}}\left(\log
m_{\ell}\right)s^{m_{\ell-1}+1}\leq 14\left(\log
m_{\ell}\right)s^{m_{\ell-1}+1}.$

Combining the last two displayed equation yields that

$\displaystyle\beta_{\ell-1}\leq\beta_{\ell}+\frac{18}{7}\alpha_{r}\lambda_{\ell}+18\left(\log
m_{\ell}\right)^{2}s^{m_{\ell-1}+1}\leq\beta_{\ell}+\frac{18}{7}\alpha_{r}\lambda_{\ell}+18\times
9s\times 2^{-4\ell+2},$

where the last inequality holds in view of $\left(\log
m_{\ell}\right)^{2}s^{m_{\ell-1}+1}\leq 9s\times 2^{-4\ell+2}$ by (C1).

By the telescoping summation of the last displayed equation and $\beta_{r}=0$,
we get

$\displaystyle\beta_{1}$
$\displaystyle\leq\frac{18}{7}\alpha_{r}\sum_{\ell=2}^{r}\lambda_{\ell}+18\times
9s\times\sum_{\ell=2}^{r}2^{-4\ell+2}\leq 3,$

where the last equality holds by since
$\sum_{\ell=2}^{r}\lambda_{\ell}\leq\log K\leq 2\log k$ and
$\alpha_{r}=\frac{1}{\eta}=\frac{1}{\omega\left(\log k\right)}$. In particular
if $s=o(1)$, we have $\beta_{1}=o(1).$

  * •

Proof of (C6)) First, we prove for any $2\leq\ell\leq r$, $S_{\ell}\leq
S_{\ell-1}\left(1+27\exp\left(-\lambda_{\ell}\right)\right)$. Since
$M_{{\ell}}=M_{{\ell}-1}+B_{{\ell}}+C_{{\ell}}$ and
$A_{\ell}=B_{{\ell}}+C_{{\ell}}$, by (113), letting $c=1.04$, we have

$\displaystyle S_{\ell}$
$\displaystyle\leq\mathbb{E}\bigg{[}\left(\prod_{t=1}^{\ell-1}\left(1+cs^{m_{t-1}+1}\left(M_{t}+B_{t+1}\right)\right)^{A_{t}}\right)$
$\displaystyle~{}~{}~{}~{}\left(1+cs^{m_{\ell-1}+1}\left(M_{\ell-1}+B_{\ell}+C_{\ell}+B_{\ell+1}\right)\right)^{B_{\ell}+C_{\ell}+B_{\ell+1}}\exp\left(\alpha_{\ell}\left(M_{\ell-1}+B_{\ell}+C_{\ell}+B_{\ell+1}\right)+\beta_{\ell}\right)\bigg{]}$
$\displaystyle=\mathbb{E}\bigg{[}\left(\prod_{t=1}^{\ell-1}\left(1+cs^{m_{t-1}+1}\left(M_{t}+B_{t+1}\right)\right)^{A_{t}}\right)\exp\left(\alpha_{\ell}\left(M_{\ell-1}+B_{\ell}\right)+\beta_{\ell}\right)$
$\displaystyle~{}~{}~{}~{}\left(1+cs^{m_{\ell-1}+1}\left(M_{\ell-1}+B_{\ell}+C_{\ell}+B_{\ell+1}\right)\right)^{B_{\ell}+C_{\ell}+B_{\ell+1}}\exp\left(\alpha_{\ell}\left(C_{\ell}+B_{\ell+1}\right)\right)\bigg{]}.$
(115)

Note that $\\{B_{t},A_{t}\\}_{t=1}^{\ell-1}$ and $B_{\ell}$ are independent
from $C_{\ell}+B_{\ell+1}$. To proceed, we condition on
$\\{B_{t},A_{t}\\}_{t=1}^{\ell-1}$ and $B_{\ell}$, and take expectation over
$C_{\ell}+B_{\ell+1}$ by applying (106) in Lemma 9. In particular, let
$X=C_{\ell}+B_{\ell+1}\sim{\rm Poi}\left(\lambda_{\ell}\right)$,
$a=1+cs^{m_{\ell-1}+1}\left(M_{\ell-1}+B_{\ell}\right)$,
$b=cs^{m_{\ell-1}+1}$, $d=B_{\ell}$, $\lambda=\lambda_{\ell}$, and
$\alpha=\alpha_{\ell}\leq\frac{2}{5}$ by (C5). By (C4),
$\lambda_{\ell}\leq\log m_{\ell}$ for $\ell\geq 2$, and thus

$be^{\alpha+1}\lambda=cs^{m_{\ell-1}+1}e^{\alpha_{\ell}+1}\lambda_{\ell}\leq
ce^{1.4}s^{m_{\ell-1}+1}\log m_{\ell}\leq ce^{1.4}\times 2^{-6}<\frac{1}{4},$

where the second-to-the-last inequality holds by (C1). For ease of notation,
let $\xi=1+2be^{\alpha+1}\lambda$ and note that
$a=1+b\left(M_{\ell-1}+B_{\ell}\right)$. Then it follows from (106) in Lemma 9
that

$\displaystyle\mathbb{E}_{C_{\ell}+B_{\ell+1}}\left[\left(1+cs^{m_{\ell-1}+1}\left(M_{\ell-1}+B_{\ell}+C_{\ell}+B_{\ell+1}\right)\right)^{B_{\ell}+C_{\ell}+B_{\ell+1}}\exp\left(\alpha_{\ell}\left(C_{\ell}+B_{\ell+1}\right)\right)\mid
M_{\ell-1},B_{\ell}\right]$
$\displaystyle\leq\left(1+b\left(M_{\ell-1}+B_{\ell}\right)\right)^{B_{\ell}}\xi^{B_{\ell}}\exp\left\\{\lambda_{\ell}\left[\left(1+b\left(M_{\ell-1}+B_{\ell}\right)\right)e^{\alpha_{\ell}}\xi-1\right]\right\\}$
$\displaystyle~{}~{}~{}~{}+27\exp\left(-\lambda_{\ell}\right)\max\big{\\{}\left(4bB_{\ell}\right)^{B_{\ell}},\left(1+b\left(M_{\ell-1}+B_{\ell}\right)\right)^{B_{\ell}}\big{\\}}$
$\displaystyle\leq\left(1+b\left(M_{\ell-1}+B_{\ell}\right)\right)^{B_{\ell}}\xi^{M_{\ell-1}+B_{\ell}}\exp\left\\{\lambda_{\ell}\left[\left(1+b\left(M_{\ell-1}+B_{\ell}\right)\right)e^{\alpha_{\ell}}\xi-1\right]\right\\}$
$\displaystyle~{}~{}~{}~{}+27\exp\left(-\lambda_{\ell}\right)\left(1+4b\left(M_{\ell-1}+B_{\ell}\right)\right)^{B_{\ell}}$
$\displaystyle\leq\left(1+4b\left(M_{\ell-1}+B_{\ell}\right)\right)^{B_{\ell}}\exp\left\\{\left(\lambda_{\ell}be^{\alpha_{\ell}}\xi+\log\xi\right)\left(M_{\ell-1}+B_{\ell}\right)+\lambda_{\ell}\left(e^{\alpha_{\ell}}\xi-1\right)\right\\}\left(1+27\exp\left(-\lambda_{\ell}\right)\right)$
$\displaystyle\leq\left(1+cs^{m_{\ell-2}+1}\left(M_{\ell-1}+B_{\ell}\right)\right)^{B_{\ell}}\exp\left\\{\left(\alpha_{\ell-1}-\alpha_{\ell}\right)\left(M_{\ell-1}+B_{\ell}\right)+\left(\beta_{\ell-1}-\beta_{\ell}\right)\right\\}\left(1+27\exp\left(-\lambda_{\ell}\right)\right),$

where the last inequality holds in view of (111) and (112), and the fact that
$4s^{m_{\ell-1}}\leq s^{m_{\ell-2}}$ by (C2) and $s\leq 0.1$.

Combining the above result with (115), we get

$\displaystyle S_{\ell}$
$\displaystyle\leq\mathbb{E}\bigg{[}\left(\prod_{t=1}^{\ell-1}\left(1+cs^{m_{t-1}+1}\left(M_{t}+B_{t+1}\right)\right)^{A_{t}}\right)$
$\displaystyle~{}~{}~{}~{}\left(1+cs^{m_{\ell-2}+1}\left(M_{\ell-1}+B_{\ell}\right)\right)^{B_{\ell}}\exp\left(\alpha_{\ell-1}\left(M_{\ell-1}+B_{\ell}\right)+\beta_{\ell-1}\right)\bigg{]}\left(1+27\exp\left(-\lambda_{\ell}\right)\right)$
$\displaystyle=S_{\ell-1}\left(1+27\exp\left(-\lambda_{\ell}\right)\right).$

Applying the last displayed equation recursively, we get that

$\displaystyle(\ref{eq:s_constant})=S_{r}$ $\displaystyle\leq
S_{1}\prod_{\ell=2}^{r}\left(1+27\exp\left(-\lambda_{\ell}\right)\right)\leq
S_{1}\exp\left(27\sum_{\ell=2}^{r}\exp\left(-\lambda_{\ell}\right)\right)=O(S_{1}),$

where the last equality holds by (C4), in particular if $s=o(1)$, we have

$S_{r}=S_{1}\left(1+o(1)\right).$

It remains to calculate $S_{1}$. Note that

$\displaystyle S_{1}$
$\displaystyle=\mathbb{E}\left[(1+cs(M_{1}+B_{2}))^{A_{1}+B_{2}}\exp\left(\alpha_{1}(M_{1}+B_{2})+\beta_{1}\right)\right]$
$\displaystyle=\mathbb{E}\left[(1+cs(C_{1}+B_{2}))^{C_{1}+B_{2}}\exp\left(\alpha_{1}(C_{1}+B_{2})\right)\right]\exp\left(\beta_{1}\right),$

where the last equality holds due to $B_{1}=0$ and $M_{1}=A_{1}=C_{1}$. We
apply (107) in Lemma 9, with $X=C_{1}+B_{2}\sim{\rm Poi}(\lambda_{1})$, $a=1$,
$b=1.04s\leq 0.104$, $\lambda=\lambda_{1}=\frac{3}{2}$ and
$\alpha=\alpha_{1}\leq\frac{2}{5}$ by (C5). Noting that
$be^{\alpha+1}\lambda\leq 1.04\cdot 0.1\cdot e^{1.4}\cdot\frac{3}{2}<0.633$
and $\beta_{1}\leq 3$ by (C5), we conclude $S_{1}=O(1)$ and hence
$S_{r}=O(1)$.

In particular, if $s=o(1)$, by (108) in Lemma 9 with $a=1$, $b=1.04s=o(1)$,
$d=0$, $\alpha=\alpha_{1}=o(1)$ by (C5), and $\lambda=\frac{3}{2}$, we have
$S_{1}=1+o(1)$ and hence $S_{r}=1+o(1)$.

∎

###### Proof of Lemma 9.

First, we show (106): Let $\gamma=2e^{\alpha+1}a$. Write

$\displaystyle\mathbb{E}\left[\left(a+bX\right)^{X+d}\exp\left(\alpha
X\right)\right]$
$\displaystyle=\mathbb{E}\left[\left(a+bX\right)^{X+d}\exp\left(\alpha
X\right){\mathbf{1}_{\left\\{{X<\gamma\lambda}\right\\}}}\right]+\mathbb{E}\left[\left(a+bX\right)^{X+d}\exp\left(\alpha
X\right){\mathbf{1}_{\left\\{{X\geq\gamma\lambda}\right\\}}}\right]$
$\displaystyle=\text{(I)}+\text{(II)}.$

Then we have

(I)
$\displaystyle\leq\mathbb{E}\left[\left(a+b\gamma\lambda\right)^{X+d}\exp\left(\alpha
X\right)\right]$
$\displaystyle=\left(a+b\gamma\lambda\right)^{d}\mathbb{E}\left[\exp\left(X\left(\log\left(a+b\gamma\lambda\right)+\alpha\right)\right)\right]$
$\displaystyle\overset{(a)}{=}\left(a+b\gamma\lambda\right)^{d}\exp\left(\lambda\left(e^{\alpha}\left(a+b\gamma\lambda\right)-1\right)\right)$
$\displaystyle=\left(a+2abe^{\alpha+1}\lambda\right)^{d}\exp\left(\lambda\left(ae^{\alpha}\left(1+2be^{\alpha+1}\lambda\right)-1\right)\right),$

where $(a)$ holds by the moment generating function
$\mathbb{E}\left[\exp\left(tX\right)\right]=\exp\left(\lambda\left(e^{t}-1\right)\right)$.
Then, directly substituting the Poisson PMF into (II), we get

(II) $\displaystyle\leq
e^{-\lambda}\sum_{k\geq\gamma\lambda}\frac{\lambda^{k}}{k!}\left(a+bk\right)^{k+d}\exp\left(\alpha
k\right)$
$\displaystyle\overset{(a)}{\leq}e^{-\lambda}\sum_{k\geq\gamma\lambda}\left(\frac{e\lambda}{k}\right)^{k}\left(a+bk\right)^{k+d}\exp\left(\alpha
k\right)$ $\displaystyle\leq
e^{-\lambda}\sum_{k\geq\gamma\lambda}\left[\frac{ae^{\alpha+1}}{\gamma}+be^{\alpha+1}\lambda\right]^{k}\left(a+bk\right)^{d}$
$\displaystyle\overset{(b)}{\leq}e^{-\lambda}\sum_{k\geq\gamma\lambda}\left(\frac{3e^{\frac{1}{4}}}{4}\right)^{k}\exp\left(f\left(k\right)\right),$

where $(a)$ holds because $k!\geq\left(\frac{k}{e}\right)^{k}$; $(b)$ holds by
the choice of $\gamma=2ae^{\alpha+1}$, our assumption that
$be^{\alpha+1}\lambda<\frac{1}{4}$, and defining:

$f(x)\triangleq d\log\left(a+bx\right)-\frac{x}{4}.$

As $b,d>0$, $f(x)$ is concave and $f^{\prime}(x)=\frac{bd}{a+bx}-\frac{1}{4},$
which equals $0$ when $x=4d-\frac{a}{b}$. Therefore, if $4d\geq\frac{a}{b}$,
then $f(x)$ for $x\geq 0$ is maximized at $x=4d-\frac{a}{b}$, and
$f(4d-\frac{a}{b})=d\log\left(4bd\right)-d+\frac{a}{4b}\leq
d\log\left(4bd\right)$. Otherwise, $f(x)$ for $x\geq 0$ is maximized at $x=0$,
and $f(0)=d\log a.$ In conclusion, we have $\max_{k\geq
0}f(k)\leq\max\\{d\log\left(4bd\right),d\log a\\}.$ Then we get an upper bound
on (II) as

(II)
$\displaystyle\leq\exp\left(-\lambda\right)\sum_{k\geq\gamma\lambda}\left(\frac{3e^{\frac{1}{4}}}{4}\right)^{k}\max\big{\\{}\left(4bd\right)^{d},a^{d}\big{\\}}$
$\displaystyle\leq
27\exp\left(-\lambda\right)\max\big{\\{}\left(4bd\right)^{d},a^{d}\big{\\}}.$

where the last inequality follows by
$\frac{\frac{3}{4}e^{1/4}}{1-\frac{3}{4}e^{1/4}}<27$.

Next we prove (107). Substituting the Poisson PMF into (107) yields that

$\displaystyle\mathbb{E}\left[\left(a+bX\right)^{X}\exp\left(\alpha
X\right)\right]$
$\displaystyle=\sum_{k=0}^{\infty}\frac{\lambda^{k}e^{-\lambda}}{k!}(a+bk)^{k}\exp(\alpha
k)$
$\displaystyle\overset{(a)}{\leq}e^{-\lambda}\left(1+\sum_{k=1}^{\infty}\left(\frac{a\lambda
e^{\alpha+1}}{k}+be^{\alpha+1}\lambda\right)^{k}\right)$
$\displaystyle\overset{(b)}{=}O(1).$

where $(a)$ holds due to $k!\geq\left(\frac{k}{e}\right)^{k}$ for $k\geq 1$,
and $(b)$ holds because $a,b,\alpha,\lambda$ are fixed constants such that
$be^{\alpha+1}\lambda<1$.

It remains to prove (108). Given $b=o(1)$, $\alpha=o(1)$, we pick
$t=\omega(1)$ such that $bt^{2}+\alpha t=o(1)$ and get:

$\displaystyle\mathbb{E}\left[\left(1+bX\right)^{X}\exp\left(\alpha
X\right)\right]$
$\displaystyle=\sum_{k=0}^{t}\frac{\lambda^{k}e^{-\lambda}}{k!}(1+bk)^{k}e^{\alpha
k}+\sum_{k=t+1}^{\infty}\frac{\lambda^{k}e^{-\lambda}}{k!}(1+bk)^{k}e^{\alpha
k}$
$\displaystyle\overset{(a)}{\leq}\sum_{k=0}^{t}\frac{\lambda^{k}e^{-\lambda}}{k!}\exp\left(bk^{2}+\alpha
k\right)+e^{-\lambda}\sum_{k=t+1}^{\infty}\left(\frac{\lambda
e^{\alpha+1}}{k}+be^{\alpha+1}\lambda\right)^{k}$ $\displaystyle=1+o(1),$

where the last equality holds because $\exp\left(bk^{2}+\alpha
k\right)=1+o(1)$ for any $0\leq k\leq t$ given $bt^{2}+\alpha t=o(1)$, and
$\sum_{k=t+1}^{\infty}\left(\frac{\lambda
e^{\alpha+1}}{k}+be^{\alpha+1}\lambda\right)^{k}=o(1)$ for any $k>t$ given
$t=\omega(1)$, $b=o(1)$, $\alpha=o(1)$, and $\lambda$ is some constant. ∎

##  Appendix C Concentration Inequalities for Gaussians and Binomials

######  Lemma 10 (Hanson-Wright inequality).

Let $X,Y\in{\mathbb{R}}^{n}$ are standard Gaussian vectors such that the pairs
$(X_{i},Y_{i})\sim{\mathcal{N}}\Big{(}\left(\begin{smallmatrix}0\\\
0\end{smallmatrix}\right),\left(\begin{smallmatrix}1&\rho\\\
\rho&1\end{smallmatrix}\right)\Big{)}$ are independent for $i=1,\ldots,n$. Let
$M\in{\mathbb{R}}^{n\times n}$ be any deterministic matrix. There exists some
universal constant $c>0$ such that with probability at least $1-2\delta$,

$\displaystyle\left|X^{\top}MY-\rho\mathsf{Tr}(M)\right|\leq
c\left(\|M\|_{F}\sqrt{\log(1/\delta)}+\|M\|\log(1/\delta)\right).$ (116)

###### Proof.

When $\rho=1$, i.e. $X=Y$, the bilinear form reduces to a quadratic form and
this lemma is the original Hanson-Wright inequality [HW71, RV13]. In general,
note that

$\displaystyle
X^{\top}MY=\frac{1}{4}(X+Y)^{\top}M(X+Y)-\frac{1}{4}(X-Y)^{\top}M(X-Y).$

Thus, it suffices to analyze the two terms separately. Note that

$\mathbb{E}\left[(X\pm Y)^{\top}M(X\pm Y)\right]=(2\pm 2\rho)\mathsf{Tr}(M).$

Applying the Hanson-Wright inequality, we get that with probability at least
$1-\delta$,

$\left|(X\pm Y)^{\top}M(X\pm Y)-\mathbb{E}\left[(X\pm Y)^{\top}M(X\pm
Y)\right]\right|\leq
c\left(\|M\|_{F}\sqrt{\log(1/\delta)}+\|M\|\log(1/\delta)\right),$

where $c$ is some universal constant. The conclusion readily follows by
combining the last three displayed equations. ∎

######  Lemma 11 (Chernoff’s inequality for Binomials).

Suppose $X\sim{\rm Binom}(n,p)$ with mean $\mu=np$. Then for any $\delta>0$,

$\displaystyle\mathbb{P}\left\\{X\geq(1+\delta)\mu\right\\}\leq\exp\left(-\mu\left((1+\delta)\log(1+\delta)-\delta\right)\right),$
(117)

and

$\displaystyle\mathbb{P}\left\\{X\leq(1-\delta)\mu\right\\}\leq\exp\left(-\frac{\delta^{2}}{2}\mu\right).$
(118)

In particular, it follows from (117) that

$\displaystyle\mathbb{P}\left\\{X\geq\tau\right\\}\leq\exp\left(-t\right),\quad\forall
t>0,$ (119)

where
$\tau=\mu\exp\left\\{1+W\left(\frac{t}{e\mu}-\frac{1}{e}\right)\right\\}$ and
$W(x)$ is the Lambert W function defined on $[-1,\infty]$ as the unique
solution of $W(x)e^{W(x)}=x$ for $x\geq-1/e$.

###### Proof.

Note that (117) and (118) are direct consequences of [MU05, Theorems 4.4 and
4.5]. To derive (119) from (117), we use

$y=\exp\left(1+W(x/e)\right)\iff\log\frac{y}{e}=W(x/e)\iff\log\frac{y}{e}\exp\left(\log\frac{y}{e}\right)=\frac{x}{e}\iff
y\log y-y=x,$

and let $x=t/\mu-1$, $y=1+\delta$, and $\tau=y\mu$. ∎

##  Appendix D Facts on Random Permutation

In this appendix we collect several useful facts about random permutation (cf.
[AT92]). For any $\ell\in{\mathbb{N}}$, let $n_{\ell}$ denote the number of
$\ell$-cycles in a uniform random permutation $\sigma\in{\mathcal{S}}_{n}$.
Let $\\{Z_{\ell}\\}_{1\leq\ell\leq k}$ denote a sequence of independent
Poisson random variables where $Z_{\ell}\sim{\rm
Poi}\left(\frac{1}{\ell}\right)$.

######  Lemma 12.

For any $k\in[n]$ and $a_{1},a_{2},\cdots,a_{k}\in{\mathbb{Z}}_{+}$,

$\displaystyle\mathbb{P}\left\\{n_{1}\geq a_{1},n_{2}\geq
a_{2},\cdots,n_{k}\geq a_{k}\right\\}$
$\displaystyle\leq\frac{1}{\prod_{\ell=1}^{k}\ell^{a_{\ell}}a_{\ell}!}.$ (120)

Consequently, for any nonnegative function $g$,

$\mathbb{E}[g(n_{1},\ldots,n_{k})]\leq\mathbb{E}[g(Z_{1},\ldots,Z_{k})]\exp\left({h}_{k}\right)$
(121)

where ${h}_{k}=\sum_{1\leq\ell\leq k}\frac{1}{k}$ denote the harmonic number.

###### Proof.

It suffices to check the first inequality. Note that for all
$\sum_{\ell=1}^{k}\ell a_{\ell}\leq n$, $\mathbb{E}\left[\prod_{1\leq\ell\leq
k}\binom{n_{\ell}}{a_{\ell}}\right]=\frac{1}{\prod_{\ell=1}^{k}\ell^{a_{\ell}}a_{\ell}!}$
(see e.g. [AT92, Eq. (5)]). Then (120) follows due to
${\mathbf{1}_{\left\\{{n_{\ell}\geq
a_{\ell}}\right\\}}}\leq\binom{n_{\ell}}{a_{\ell}}$ for $1\leq\ell\leq k$. ∎

######  Lemma 13 ([AT92, Theorem 2]).

For any $1\leq k<n$, the total variation distance between the law of
$\\{n_{\ell}\\}_{1\leq\ell\leq k}$ and the law of
$\\{Z_{\ell}\\}_{1\leq\ell\leq k}$ satisfies:

$\displaystyle\mathrm{TV}\left({\mathcal{L}}\left(n_{1},n_{2},\ldots,n_{k}\right),{\mathcal{L}}\left(Z_{1},Z_{2},\ldots,Z_{k}\right)\right)\leq
F\left(\frac{n}{k}\right),$ (122)

where $F(x)=\sqrt{2\pi
m}\frac{2^{m-1}}{\left(m-1\right)!}+\frac{1}{m!}+3\left(\frac{x}{e}\right)^{-x},$
with $m\triangleq\left\lceil x\right\rceil{}$, so that $\log F(x)=-x\log
x(1+o(1))$ as $x\to\infty$.

## Acknowledgment

The authors thank Cristopher Moore for simplifying the proof of Proposition 1.
J. Xu would like to thank Tselil Schramm for helpful discussions on the
hypothesis testing problem at the early stage of the project.

## References

  * [ACV14] Ery Arias-Castro and Nicolas Verzelen.  Community detection in dense random networks.  The Annals of Statistics, 42(3):940–969, 2014.
  * [AT92] Richard Arratia and Simon Tavaré.  The cycle structure of random permutations.  The Annals of Probability, pages 1567–1591, 1992.
  * [BBM05] Alexander C Berg, Tamara L Berg, and Jitendra Malik.  Shape matching and object recognition using low distortion correspondences.  In 2005 IEEE computer society conference on computer vision and pattern recognition (CVPR’05), volume 1, pages 26–33. IEEE, 2005.
  * [BBSV19] Paul Balister, Béla Bollobás, Julian Sahasrabudhe, and Alexander Veremyev.  Dense subgraphs in random graphs.  Discrete Applied Mathematics, 260:66–74, 2019.
  * [BCL+19] Boaz Barak, Chi-Ning Chou, Zhixian Lei, Tselil Schramm, and Yueqi Sheng.  (Nearly) efficient algorithms for the graph matching problem on correlated random graphs.  In Advances in Neural Information Processing Systems, pages 9186–9194, 2019.
  * [BGSW13] Mohsen Bayati, David F Gleich, Amin Saberi, and Ying Wang.  Message-passing algorithms for sparse network alignment.  ACM Transactions on Knowledge Discovery from Data (TKDD), 7(1):1–31, 2013.
  * [BI13] Cristina Butucea and Yuri I. Ingster.  Detection of a sparse submatrix of a high-dimensional noisy matrix.  Bernoulli, 19(5B):2652–2688, 11 2013.
  * [BMNN16] Jess Banks, Cristopher Moore, Joe Neeman, and Praneeth Netrapalli.  Information-theoretic thresholds for community detection in sparse networks.  In Conference on Learning Theory, pages 383–416, 2016.
  * [CFSV04] Donatello Conte, Pasquale Foggia, Carlo Sansone, and Mario Vento.  Thirty years of graph matching in pattern recognition.  International journal of pattern recognition and artificial intelligence, 18(03):265–298, 2004.
  * [CGH+96] Robert M Corless, Gaston H Gonnet, David EG Hare, David J Jeffrey, and Donald E Knuth.  On the Lambert W function.  Advances in Computational mathematics, 5(1):329–359, 1996.
  * [CK16] Daniel Cullina and Negar Kiyavash.  Improved achievability and converse bounds for Erdős-Rényi graph matching.  ACM SIGMETRICS Performance Evaluation Review, 44(1):63–72, 2016\.
  * [CK17] Daniel Cullina and Negar Kiyavash.  Exact alignment recovery for correlated Erdős-Rényi graphs.  arXiv preprint arXiv:1711.06783, 2017.
  * [CKMP19] Daniel Cullina, Negar Kiyavash, Prateek Mittal, and H Vincent Poor.  Partial recovery of Erdős-Rényi graph alignment via k-core alignment.  Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3(3):1–21, 2019.
  * [CSS07] Timothee Cour, Praveen Srinivasan, and Jianbo Shi.  Balanced graph matching.  In Advances in Neural Information Processing Systems, pages 313–320, 2007.
  * [DCKG19] Osman Emre Dai, Daniel Cullina, Negar Kiyavash, and Matthias Grossglauser.  Analysis of a canonical labeling algorithm for the alignment of correlated Erdos-Rényi graphs.  Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3(2):1–25, 2019.
  * [DMWX18] Jian Ding, Zongming Ma, Yihong Wu, and Jiaming Xu.  Efficient random graph matching via degree profiles.  To appear in _Probability Theory and Related Fields_ , Nov 2018\.  arxiv preprint arxiv:1811.07821.
  * [FK16] Alan Frieze and Michał Karoński.  Introduction to random graphs.  Cambridge University Press, 2016.
  * [FMWX19a] Zhou Fan, Cheng Mao, Yihong Wu, and Jiaming Xu.  Spectral graph matching and regularized quadratic relaxations I: The Gaussian model.  arxiv preprint arXiv:1907.08880, 2019.
  * [FMWX19b] Zhou Fan, Cheng Mao, Yihong Wu, and Jiaming Xu.  Spectral graph matching and regularized quadratic relaxations II: Erdős-Rényi graphs and universality.  arxiv preprint arXiv:1907.08883, 2019.
  * [FS09] Philippe Flajolet and Robert Sedgewick.  Analytic combinatorics.  Cambridge University press, 2009.
  * [GLM19] Luca Ganassali, Marc Lelarge, and Laurent Massoulié.  Spectral alignment of correlated Gaussian random matrices.  arXiv preprint arXiv:1912.00231, 2019.
  * [GM20] Luca Ganassali and Laurent Massoulié.  From tree matching to sparse graph alignment.  arXiv preprint arXiv:2002.01258, 2020.
  * [HH08] Abdolhossein Hoorfar and Mehdi Hassani.  Inequalities on the Lambert W function and hyperpower function.  J. Inequal. Pure and Appl. Math, 9(2):5–9, 2008.
  * [HM20] Georgina Hall and Laurent Massoulié.  Partial recovery in the graph alignment problem.  arXiv preprint arXiv:2007.00533, 2020.
  * [HNM05] Aria D Haghighi, Andrew Y Ng, and Christopher D Manning.  Robust textual inference via graph matching.  In Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, pages 387–394. Association for Computational Linguistics, 2005.
  * [HW71] David Lee Hanson and Farroll Tim Wright.  A bound on tail probabilities for quadratic forms in independent random variables.  The Annals of Mathematical Statistics, 42(3):1079–1083, 1971.
  * [JLR11] Svante Janson, Tomasz Luczak, and Andrzej Rucinski.  Random graphs, volume 45.  John Wiley & Sons, 2011.
  * [Kib45] WF Kibble.  An extension of a theorem of mehler’s on hermite polynomials.  In Mathematical Proceedings of the Cambridge Philosophical Society, volume 41, pages 12–15. Cambridge University Press, 1945.
  * [LR13] Lorenzo Livi and Antonello Rizzi.  The graph matching problem.  Pattern Analysis and Applications, 16(3):253–283, 2013.
  * [MMS10] Konstantin Makarychev, Rajsekar Manokaran, and Maxim Sviridenko.  Maximum quadratic assignment problem: Reduction from maximum label cover and lp-based approximation algorithm.  In International Colloquium on Automata, Languages, and Programming, pages 594–604. Springer, 2010.
  * [MNS15] Elchanan Mossel, Joe Neeman, and Allan Sly.  Reconstruction and estimation in the planted partition model.  Probability Theory and Related Fields, 162(3-4):431–461, 2015.
  * [MU05] Michael Mitzenmacher and Eli Upfal.  Probability and Computing: Randomized Algorithms and Probabilistic Analysis.  Cambridge University Press, USA, 2005.
  * [MWXY20] Cheng Mao, Yihong Wu, Jiaming Xu, and Sophie H. Yu.  Counting trees and testing correlation of unlabeled random graphs.  preprint, 2020.
  * [MX19] Elchanan Mossel and Jiaming Xu.  Seeded graph matching via large neighborhood statistics.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1005–1014. SIAM, 2019.
  * [NS08] Arvind Narayanan and Vitaly Shmatikov.  Robust de-anonymization of large sparse datasets.  In 2008 IEEE Symposium on Security and Privacy (sp 2008), pages 111–125. IEEE, 2008.
  * [NS09] Arvind Narayanan and Vitaly Shmatikov.  De-anonymizing social networks.  In 2009 30th IEEE symposium on security and privacy, pages 173–187. IEEE, 2009.
  * [Ott48] Richard Otter.  The number of trees.  Annals of Mathematics, pages 583–599, 1948.
  * [Pet95] Valentin V. Petrov.  Limit theorems of probability theory: Sequences of independent random variables.  Oxford Science Publications, Clarendon Press, Oxford, United Kingdom, 1995\.
  * [PG11] Pedram Pedarsani and Matthias Grossglauser.  On the privacy of anonymized networks.  In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1235–1243, 2011.
  * [RPW94] F Rendl, P Pardalos, and H Wolkowicz.  The quadratic assignment problem: A survey and recent developments.  In Proceedings of the DIMACS workshop on quadratic assignment problems, volume 16, pages 1–42, 1994.
  * [RS20] Miklos Z Racz and Anirudh Sridhar.  Correlated randomly growing graphs.  arXiv preprint arXiv:2004.13537, 2020.
  * [RV13] Mark Rudelson and Roman Vershynin.  Hanson-Wright inequality and sub-Gaussian concentration.  Electronic Communications in Probability, 18, 2013.
  * [RXZ19] Galen Reeves, Jiaming Xu, and Ilias Zadik.  The all-or-nothing phenomenon in sparse linear regression.  arXiv preprint arXiv:1903.05046, 2019.
  * [SXB08] Rohit Singh, Jinbo Xu, and Bonnie Berger.  Global alignment of multiple protein interaction networks with application to functional orthology detection.  Proceedings of the National Academy of Sciences, 105(35):12763–12768, 2008.
  * [Tsy09] A. B. Tsybakov.  Introduction to Nonparametric Estimation.  Springer Verlag, New York, NY, 2009.
  * [VAC15] Nicolas Verzelen and Ery Arias-Castro.  Community detection in sparse random networks.  The Annals of Applied Probability, 25(6):3465–3510, 2015.
  * [VCP+11] Joshua T Vogelstein, John M Conroy, Louis J Podrazik, Steven G Kratzer, Eric T Harley, Donniell E Fishkind, R Jacob Vogelstein, and Carey E Priebe.  Large (brain) graph matching via fast approximate quadratic programming.  arXiv preprint arXiv:1112.5507, 2011.
  * [WXY21] Yihong Wu, Jiaming Xu, and Sophie H. Yu.  Settling the sharp reconstruction thresholds of random graph matching.  arXiv preprint arXiv:2102.00082, 2021.