The restricted spectral estimate needed above the connectivity threshold

Put $\mu =np=\gamma \log n$, let $I$ be the $n\times n$ identity matrix, and set $H=(A-p(J-I))\mathrm{/}\sqrt{\mu }$. Then $\mathbb{E}A=p(J-I)$, and $H$ has the independent mean-zero upper-triangular entries and variance and entry bounds supplied by the normalization lemma; also $\mu \to \mathrm{\infty }$ and eventually $0<p<1$ (Normalize the logarithmic random graph for nonbacktracking estimates).

Write $d_{\max }={\max }_{i\in [n]}{\sum }_{j\in [n]}{A}_{ij}$ for the maximum vertex degree. The event $d_{\max }\ge 8\mu$ has probability at most $n^{-\gamma }$ (A maximum-degree tail with an explicit logarithmic exponent).

For the matrix $H$ in [F1], let $B$ be its nonbacktracking matrix indexed by all ordered vertex pairs in $[n{]}^2$, with $B_{(i,j),(k,l)}=H_{kl}{\mathbf{1}}_{j=k}{\mathbf{1}}_{i\mathrm{\ne }l}$, where each indicator is $1$ when its subscript condition holds and $0$ otherwise. Write $\rho (B)=\max \{\mathrm{\mid }z\mathrm{\mid }:z\text{ is an eigenvalue of }B\}$. When $d_{\max }<8\mu$, $\rho (B)<2$, and $\mu >16$, we have $\mathrm{\parallel }A-pJ\mathrm{\parallel }<8\sqrt{\mu }$ (Transfer two nonbacktracking good events to the required norm bound).

For the same $H$ and $B$ as in [F1] and [F3], the event $\rho (B)\ge 2$ has probability at most $n^{-\gamma }$ eventually (A nonbacktracking tail smaller than the required polynomial).

For two events $E_1,E_2$ in the same probability space, $\mathbb{P}(E_1\cup E_2)\le \mathbb{P}(E_1)+\mathbb{P}(E_2)$ (The finite union bound).