# Localized phase for the Erdős-Rényi graph

Johannes Alt  Raphael Ducatez  Antti Knowles

###### Abstract

We analyse the eigenvectors of the adjacency matrix of the Erdős-Rényi graph
$\mathbb{G}(N,d/N)$ for $\sqrt{\log N}\ll d\lesssim\log N$. We show the
existence of a localized phase, where each eigenvector is exponentially
localized around a single vertex of the graph. This complements the completely
delocalized phase previously established in ADK20 . For large enough $d$, we
establish a mobility edge by showing that the localized phase extends up to
the boundary of the delocalized phase. We derive explicit asymptotics for the
localization length up to the mobility edge and characterize its divergence
near the phase boundary.

The proof is based on a rigorous verification of Mott’s criterion for
localization, comparing the tunnelling amplitude between localization centres
with the eigenvalue spacing. The first main ingredient is a new family of
global approximate eigenvectors, for which sharp enough estimates on the
tunnelling amplitude can be established. The second main ingredient is a lower
bound on the spacing of approximate eigenvalues. It follows from an
anticoncentration result for these discrete random variables, obtained by a
recursive application of a self-improving anticoncentration estimate due to
Kesten.

######  Contents

  1. 1 Introduction
  2. 2 Proof of main results
  3. 3 Preliminaries
  4. 4 Exponential decay of $\mathbf{u}(x)$ and proof of Proposition 2.2
  5. 5 Approximate eigenvalues – proof of Proposition 2.3
  6. 6 Eigenvalue spacing – proof of Proposition 2.4
  7. A Graph properties – proofs of Propositions 3.1 and 3.2
  8. B Quantitative behaviour of $\alpha^{*}$
  9. C Qualitative behaviour of degree sequence and of $\alpha^{*}$
  10. D Largest eigenvalues of $H$ and some submatrices – proof of Proposition 3.4
  11. E Tools
  12. F The expected optimal range for $\mu$

## 1\. Introduction

### 1.1. Overview

Let $A$ be the adjacency matrix of a graph with vertex set
$[N]=\\{1,\dots,N\\}$. We are interested in the geometric structure of the
eigenvectors of $A$, in particular their _spatial localization_. An
$\ell^{2}$-normalized eigenvector
$\mathbf{w}=(w_{x})_{x\in[N]}\in\mathbb{R}^{N}$ gives rise to a probability
measure $x\mapsto w_{x}^{2}$ on the set of vertices $[N]$. Informally,
$\mathbf{w}$ is _delocalized_ if its mass is approximately uniformly
distributed throughout $[N]$, and _localized_ if its mass is essentially
concentrated on a small number of vertices.

In this paper we study the spatial localization of eigenvectors for the Erdős-
Rényi graph $\mathbb{G}\equiv\mathbb{G}(N,d/N)$. It is the simplest model of a
random graph, where each edge of the complete graph on $N$ vertices is kept
independently with probability $d/N$, with $0\leqslant d\leqslant N$. Here,
$d\equiv d_{N}$ is a parameter whose interpretation is the expected degree of
a vertex. It is well known that $\mathbb{G}$ undergoes a dramatic change in
behaviour at the _critical scale_ $d\asymp\log N$, which is the scale at and
below which the vertex degrees do not concentrate. For $d\gg\log N$, with high
probability all degrees are approximately equal and the graph is
_homogeneous_. On the other hand, for $d\lesssim\log N$, the degrees do not
concentrate and the graph becomes highly _inhomogeneous_ : it contains for
instance hubs of large degree, leaves, and isolated vertices. As long as
$d>1$, the graph $\mathbb{G}$ has with high probability a unique giant
component, and we shall always restrict our attention to it.

The Erdős-Rényi graph $\mathbb{G}$ at and below criticality was proposed in
ADK20 as a simple and natural model on which to address the question of
spatial localization of eigenvectors. Its graph structure provides an
intrinsic and nontrivial notion of distance, which allows for a study of the
geometry of the eigenvectors. It can be interpreted as a model of quantum
disorder, where the disorder arises from the random geometry of the graph.
Moreover, its phase diagram turns out to be remarkably amenable to rigorous
analysis.

In this paper we establish the existence of a fully _localized phase_ in a
region of the phase diagram of $\mathbb{G}$ near the spectral edge. This
complements the completely _delocalized phase_ established in ADK20 ;
ADK_delocalized ; HeKnowlesMarcozzi2018 ; EKYY1 . Our results in both phases
are quantitative with essentially optimal bounds.

As a consequence, for a range of critical densities $d\asymp\log N$, we
establish a _mobility edge_ separating the localized and delocalized phases.
We derive the explicit behaviour of the localization length on either side of
the mobility edge. In particular, we show how the localization length diverges
as one approaches the mobility edge from the localized phase (see Figure 1.3
below). The Erdős-Rényi graph at criticality is hence one of the very few
models where a mobility edge can be rigorously established. Moreover, our
proofs yield strong quantitative control of the localization length in the
localized phase, as well as complete delocalization in the delocalized phase,
all the way up to the mobility edge in both phases. To the best of our
knowledge, this is the first time quantitative control is obtained in the
vicinity of the mobility edge.

A graphical overview of the main result of this paper, and how it fits into
the previous results of ADK20 ; ADK_delocalized , is provided by the phase
diagram of Figure 1.1. It depicts three phases, which are most conveniently
characterized by the $\ell^{\infty}$-norm $\lVert\mathbf{w}\rVert_{\infty}$ of
an $\ell^{2}$-normalized eigenvector $\mathbf{w}$. Clearly,
$N^{-1}\leqslant\lVert\mathbf{w}\rVert_{\infty}^{2}\leqslant 1$, where
$\lVert\mathbf{w}\rVert_{\infty}^{2}=1$ corresponds to localization at a
single vertex and $\lVert\mathbf{w}\rVert_{\infty}^{2}=N^{-1}$ to perfect
delocalization. We say that an eigenvalue $\lambda$ of the rescaled adjacency
matrix $H\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=A/\sqrt{d}$
with eigenvector $\mathbf{w}$ belongs to

  1. (i)

the _localized phase_ if $\lVert\mathbf{w}\rVert_{\infty}^{2}\asymp 1$,

  2. (ii)

the _delocalized phase_ if $\lVert\mathbf{w}\rVert_{\infty}^{2}=N^{-1+o(1)}$,

  3. (iii)

the _semilocalized phase_ if $\lVert\mathbf{w}\rVert_{\infty}^{2}\geqslant
N^{-\gamma}$ for some constant $\gamma<1$.

In particular, the localized phase is a subphase of the semilocalized phase.
The result of this paper is the existence of phase (i), while phases (ii) and
(iii) were previously established in ADK20 ; ADK_delocalized .

delocalized
---
$b$
---
$-2$
---
$0$
---
$2$
---
$b_{*}$
---
-2
---
2
---
localized
---
semilocalized
---
$1$
---
$\lambda$
---
Figure 1.1: The phase diagram of the rescaled adjacency matrix $A/\sqrt{d}$ of
the (giant component of the) Erdős-Rényi graph $\mathbb{G}(N,d/N)$ at
criticality, where $d=b\log N$ with $b$ fixed. The horizontal axis records the
location $\lambda$ in the spectrum and the vertical axis the sparseness
parameter $b$. The spectrum is confined to the coloured region, which is split
into the indicated phases. The thick purple lines correspond to phase
boundaries, which are not covered by our results. (The phase boundary at
energy $0$ for $b\leqslant 1$ is discussed in ADK20 ; ADK_delocalized .) For
large enough $b$, there is a mobility edge between the localized and the
delocalized phases at energies $\pm 2$.

We now briefly describe the structure of the phase diagram in Figure 1.1. It
is well known Wigner1958 that, as long as $d\gg 1$, the global eigenvalue
density of $H$ converges to the semicircle law supported in $[-2,2]$. We write
$d=b\log N$ for some constant111Our results hold also for $d\ll\log N$, i.e.
below the critical scale, but in this overview we suppose for simplicity that
$b$ is a constant. $b>0$. The localized and semilocalized phases exist only if
$b<b_{*}$, where

$b_{*}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\frac{1}{2\log
2-1}\approx 2.59\,.$ (1.1)

For fixed $b<b_{*}$, the spectrum splits into two disjoints parts, the
delocalized phase $(-2,0)\cup(0,2)$ and the semilocalized phase
$(-\lambda_{\max},-2)\cup(2,\lambda_{\max})$, where $\lambda_{\max}>2$ is an
explicit function of $b$ (see (C.3) below). A region
$(-\lambda_{\max},-\lambda_{\mathrm{loc}})\cup(\lambda_{\mathrm{loc}},\lambda_{\max})$
near the spectral edges is in fact fully localized, where
$2\leqslant\lambda_{\mathrm{loc}}<\lambda_{\max}$. In particular, for large
enough $b$, the semilocalized phase consists entirely of the localized phase,
i.e. $\lambda_{\mathrm{loc}}=2$. For smaller values of $b$, the diagram in
Figure 1.1 does not rule out the possibility of an eigenvector $\mathbf{w}$ in
the semilocalized phase satisfying
$\lVert\mathbf{w}\rVert_{\infty}^{2}=N^{-\gamma+o(1)}$ for some constant
$\gamma\in(0,1)$. This latter scenario corresponds to eigenvectors that are
neither fully localized nor fully delocalized222In the literature, this
phenomenon is sometimes referred to as nonergodic delocalization., where
$\gamma\in(0,1)$ plays the role of an anomalous fractal dimension. In fact, it
is plausible that such fractal eigenvectors occur in the semilocalized phase
for small enough $b$; for more details, we refer to tarzia2022 and the
heuristic discussion on localization phenomena later in this subsection, as
well as Appendix F below.

The localization-delocalization transition for $\mathbb{G}$ described above is
an example of an _Anderson transition_ , where a disordered quantum system
exhibits localized or delocalized states depending on the disorder strength
and the location in the spectrum, corresponding to an insulator or conductor,
respectively. Originally proposed in the 1950s anderson1958absence to model
conduction in semiconductors with random impurities, this phenomenon is now
recognized as a general feature of wave transport in disordered media, and is
one of the most influential ideas in modern condensed matter physics
lee1985disordered ; evers2008anderson ; lagendijk2009fifty ; abrahams201050 .
It is expected to occur in great generality whenever linear waves, such as
quantum particles, propagate through a disordered medium. For weak enough
disorder, the stationary states are expected to be delocalized, while a strong
enough disorder can give rise to localized states.

The general heuristic behind localization is the following. A disordered
quantum system is characterized by its Hamiltonian $H$, a large Hermitian
random matrix. The disorder inherent in $H$ gives rise to spatial regions
where the environment is in some sense exceptional, such as vertices of
unusually large degree for the Erdős-Rényi graph333For the Anderson model
discussed below, these regions arise from an unusually large mean random
potential. We note that, just like the large degree vertices for $\mathbb{G}$,
these regions arise as a result of a collective phenomenon, requiring the
conspiracy of a large number of independent random variables to yield an
exceptional local configuration.. These regions are possible localization
centres, around which localized states may form. Whether they do so is
captured by the following well-known rule of thumb, also known as Mott’s
criterion: localization occurs whenever _the eigenvalue spacing is much larger
than the tunnelling amplitude between localization centres_. The simplest
illustration of this rule is for a two-state system whose Hamiltonian is the
matrix $\bigl{(}\begin{smallmatrix}a&\tau\\\ \tau&b\end{smallmatrix}\bigr{)}.$
Setting the tunnelling amplitude $\tau$ between the two sites to zero, we have
an eigenvalue spacing $\lvert a-b\rvert$. Denoting by
$\mathbf{e}_{1},\mathbf{e}_{2}$ the standard basis vectors of
$\mathbb{R}^{2}$, we find that if $\lvert\tau\rvert\ll\lvert a-b\rvert$ then
the eigenvectors are approximately $\mathbf{e}_{1},\mathbf{e}_{2}$,
corresponding to localization, and if $\lvert\tau\rvert\gg\lvert a-b\rvert$
then the eigenvectors are approximately
$\frac{1}{\sqrt{2}}(\mathbf{e}_{1}\pm\mathbf{e}_{2})$, corresponding to
delocalization.

More generally, for a disordered Hamiltonian $H$ defined on some connected
graph, a simple yet instructive way to think of the rule of thumb is to
suppose that the localization centres are spatially separated, and to
construct the Hamiltonian $\widehat{H}$ from $H$ by removing edges from the
graph so as to disconnect the localization centres from each other. Hence,
$\widehat{H}$ is defined on a union of connected components, each of which is
associated with a single localization centre. Denote by $\mathcal{W}$ the set
of localization centres, which are vertices in the underlying graph. A
component associated with a localization centre $x\in\mathcal{W}$ trivially
gives rise to a localized state $\mathbf{w}(x)$ of $\widehat{H}$ with
eigenvalue $\theta(x)$, which has the interpretation of the energy of the
localization centre $x$. Upon putting back the removed edges, one can imagine
two scenarios:

  1. (i)

_localization_ , where the eigenvectors of $H$ remain close to the
eigenvectors $\mathbf{w}(x)$ of $\widehat{H}$;

  2. (ii)

_hybridization_ , where eigenvectors $\mathbf{w}(x)$ associated with several
resonant localization centres $x$ with similar energies $\theta(x)$ are
superimposed to form eigenvectors of $H$.

We refer to Figure 1.2 for an illustration of this dichotomy.

$H$
---
$\widehat{H}$
---

localization
---

hybridization
---

$\operatorname{spec}(\widehat{H})$
---
$\operatorname{spec}(H)$
---
$H$
---
$H$
---
$\operatorname{spec}(\widehat{H})$
---
$\operatorname{spec}(H)$
---
$\operatorname{spec}(\widehat{H})$
---
Figure 1.2: A schematic illustration of the localization-hybridization
dichotomy. A disordered Hamiltonian $H$ defined on a graph has three
localization centres whose energies are in resonance. They are indicated in
red, green, and blue. The Hamiltonian $\widehat{H}$ is obtained from $H$ by
splitting the graph into disconnected components around each localization
centre. This gives rise to three eigenvalues of $\widehat{H}$ associated with
the three components. Each component associated with a centre $x$ carries a
localized state $\mathbf{w}(x)$ drawn as a decaying density in the colour
corresponding to that of the centre. The spectrum of $\widehat{H}$ is drawn
above the real line in dotted lines that match the colour of the associated
centre. Upon putting back the edges of the graph to return to $H$, we can have
either localization or hybridization, depending on Mott’s criterion. In each
case, we draw the spectrum of $H$ below the real line. In the case of
localization, the eigenvectors of $H$ remain close to $\mathbf{w}(x)$ and the
eigenvalues are shifted by an amount that is small compared to the eigenvalue
spacing. In the case of hybridization, the eigenvectors of $H$ are delocalized
over the three centres, being approximately nontrivial linear combinations of
all three vectors $\mathbf{w}(x)$.

To use Mott’s criterion, we note that one possible way of quantifying the
tunnelling amplitude is

$\tau\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\max_{x\in\mathcal{W}}\lVert(H-\theta(x))\mathbf{w}(x)\rVert\,.$
(1.2)

Indeed, this expression clearly generalizes the tunnelling amplitude for the
two-level system given above, expressing in general the error arising from
putting back the edges of $H$ missing from $\widehat{H}$, with respect to the
family $(\mathbf{w}(x))_{x\in\mathcal{W}}$. It measures the extent to which
the localized eigenvectors $\mathbf{w}(x)$ of $\widehat{H}$ are approximate
eigenvectors of $H$ (sometimes also called quasi-modes of $H$). Under some
assumptions on the localization components, $\tau$ also controls the off-
diagonal part in a block-diagonal representation of $H$ in the basis
$(\mathbf{w}(x)\mathrel{\vbox{\hbox{.}\hbox{.}}}x\in\mathcal{W})$; see Section
2.3 below. Mott’s criterion states that localization occurs whenever
$\tau\ll\Delta$, where

$\Delta\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\min_{x\neq
y\in\mathcal{W}}\lvert\theta(x)-\theta(y)\rvert$ (1.3)

is the eigenvalue spacing. Otherwise, we expect hybridization. The main
difficulty in establishing localization is therefore to control _resonances_ ,
i.e. pairs of vertices $x,y$ such that $\lvert\theta(x)-\theta(y)\rvert$ is
small, and to rule out hybridization. Although this picture is helpful in
gaining intuition about localization, in many instances, such as in the proof
for the Erdős-Rényi graph in this paper444Or for the Anderson model e.g. in
FroSpe ., it is but a rough caricature and the true picture is considerably
more subtle (as we explain later in this subsection and in more detail in
Section 2.3).

The semilocalized phase of the Erdős-Rényi graph from ADK20 is a phase where
the eigenvectors are concentrated around a small number of localization
centres, but where hybridization cannot be ruled out. As shown in ADK20 , the
set of all possible localization centres of $\mathbb{G}$ corresponds to
vertices $x\in[N]$ whose _normalized degree_

$\alpha_{x}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\sum_{y\in[N]}H_{xy}^{2}=\frac{1}{d}\sum_{y\in[N]}A_{xy}$

is greater than $2$. The energy $\theta(x)$ of a localization centre $x$ is
approximately equal to $\Lambda(\alpha_{x})$, where we introduced the function
$\Lambda\colon[2,\infty)\to[2,\infty)$ through

$\Lambda(\alpha)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\frac{\alpha}{\sqrt{\alpha-1}}\,.$
(1.4)

As shown in ADK19 (see also MR4234995 ), there is a one-to-one correspondence
between eigenvalues $\lambda>2$ in the semilocalized phase and vertices $x$ of
normalized degree $\alpha_{x}\geqslant 2$ given by
$\lambda=\Lambda(\alpha_{x})+o(1)$. An eigenvalue $\lambda$ in the
semilocalized phase has an eigenvector that is almost entirely concentrated in
small balls around the set of vertices
$\mathcal{W}_{\lambda}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\\{x\in[N]\mathrel{\vbox{\hbox{.}\hbox{.}}}\Lambda(\alpha_{x})=\lambda+o(1)\\}$
in resonance with the energy $\lambda$ ADK20 . The size of the set of resonant
vertices $\mathcal{W}_{\lambda}$ is comparable to the density of states, equal
to $N^{\rho_{b}(\lambda)+o(1)}$ for an explicit exponent $\rho_{b}(\lambda)<1$
given in (C.4) in Appendix C below. Hence, owing to the small size of the set
of resonant vertices $\mathcal{W}_{\lambda}$, the semilocalized phase is
sharply distinguished from the delocalized phase. However, the key issue of
controlling resonances and ruling out hybridization is not addressed in ADK20
(see Figure 1.2).

In this paper we prove localization by ruling out hybridization among the
resonant vertices. Our result holds for the largest and smallest $N^{\mu}$
eigenvalues for $\mu<\frac{1}{24}$. For small enough $\mu$, our obtained rate
of exponential decay is optimal all the way up to radii of the order of the
diameter of the graph. The bound $\frac{1}{24}$ is not optimal, and we expect
that by a refinement of the method developed in this paper it can be improved;
for the sake of keeping the argument reasonably simple, we refrain from doing
so here. Heuristic arguments suggest that the optimal upper bound for $\mu$ is
$\frac{1}{4}$; see Appendix F below as well as tarzia2022 .

At this point it is helpful to review the previous works ADK20 ; ADK21 , which
addressed the tunnelling amplitude (1.2) in the above simple picture of
localization based on disjoint neighbourhoods of localization centres. In
ADK20 , the estimate $\tau\lesssim d^{-1/2}$ was established in the entire
semilocalized phase, while in ADK21 it was improved to $\tau\lesssim d^{-3/2}$
at the spectral edge. In fact, here we argue that the best possible bound on
$\tau$ in terms of the local approximate eigenvectors $\mathbf{w}(x)$
introduced above is $\mathrm{e}^{-c\frac{\log N}{\log d}}$ for some constant
$c>0$. To see this, we recall from ADK20 that the vector $\mathbf{w}(x)$ is
exponentially decaying around $x$ at some fixed rate $C>0$ depending on $b$.
Thus, the best possible estimate for $\tau$ arising from the exponential decay
is $\mathrm{e}^{-Cr}$, where
$r\asymp\operatorname{diam}(\mathbb{G})=\frac{\log N}{\log d}(1+o(1))$ (see
ChungLu_diameter ).

As for the eigenvalue spacing (1.3), it was not addressed at all in ADK20 . In
ADK21 , it was estimated at the spectral edge as $\Delta\geqslant
d^{-1-\varepsilon}$ with high probability for any constant $\varepsilon>0$.
Combined with the bound $\tau\lesssim d^{-3/2}$ at the spectral edge obtained
in ADK21 , one finds that Mott’s criterion is satisfied at the spectral edge.
This observation was used in ADK21 to prove localization for the top $O(1)$
eigenvectors.

In the interior of the localized phase, the eigenvalue spacing at energy
$\lambda$ is typically of order $N^{-\rho_{b}(\lambda)}$, where
$\rho_{b}(\lambda)>0$ is an exponent defined in (C.4) below. This is much
smaller than the best possible estimate on the tunnelling amplitude,
$\mathrm{e}^{-c\frac{\log N}{\log d}}=N^{-o(1)}$. Hence, Mott’s criterion is
never satisfied inside the localized phase, and thus the simple picture based
on local approximate eigenvectors cannot be used to establish localization. In
this paper we therefore introduce a new setup for proving localization.

The first key idea of our proof is to abandon the above simple picture of
localization, and to replace the _local_ approximate eigenvectors
$\mathbf{w}(x)$ by _global_ approximate eigenvectors, denoted by
$\mathbf{u}(x)$, which approximate eigenvectors of $H$ much more accurately
and therefore lead to a much smaller tunnelling amplitude (1.2). To define
$\mathbf{u}(x)$, we consider the graph obtained from $\mathbb{G}$ by removing
all localization centres except $x$; we denote by $\lambda(x)$ the second
largest eigenvalue of its adjacency matrix, and by $\mathbf{u}(x)$ the
associated eigenvector. The latter is localized around the vertex $x$.
Crucially, the quantity (1.2) with $\mathbf{w}(x)$ replaced by $\mathbf{u}(x)$
can now be estimated by a _polynomial_ error $N^{-\zeta}$ for some $\zeta>0$.

The price to pay for passing from local approximate eigenvectors
$\mathbf{w}(x)$ to global approximate eigenvectors $\mathbf{u}(x)$ is a
breakdown of orthogonality. Indeed, the vectors $\mathbf{u}(x)$ have a nonzero
overlap, and a significant difficulty in our proof is to control these
overlaps and various resulting interactions between localization centres.

To complete the verification of Mott’s criterion, we need to establish a
polynomial lower bound $\min_{x\neq
y\in\mathcal{W}}\lvert\lambda(x)-\lambda(y)\rvert\geqslant N^{-\eta}$ for some
$\eta<\zeta$. Clearly, the left-hand side cannot be larger than the eigenvalue
spacing $N^{-\rho_{b}(\lambda)}$ at the energy $\lambda$ we are considering,
which yields the necessary bound $\eta>\rho_{b}(\lambda)>0$. Hence, we require
an anticoncentration result for the eigenvalue difference
$\lambda(x)-\lambda(y)$ on a polynomial scale. Owing to the discrete law of
$\mathbb{G}$ (a product of independent Bernoulli random variables), methods
based on smoothness such as Wegner estimates wegner1981bounds are not
available, and obtaining strong enough anticoncentration is the most involved
part of our proof. Our basic strategy is to perform a recursive resampling of
neighbourhoods of increasingly large balls around $y$. At each step, we derive
a _concentration_ bound for $\lambda(x)$ and an _anticoncentration_ bound for
$\lambda(y)$. The key tool for the latter is a self-improving version, due to
Kesten Kesten1969 , of a classical anticoncentration result of Doeblin, Lévy,
Kolmogorov, and Rogozin. In order to obtain sufficiently strong
anticoncentration, it is crucial to perform the recursion up to radii
comparable to the diameter of $\mathbb{G}$.

We conclude this overview with a survey of related results. The eigenvalues
and eigenvectors of the Erdős-Rényi graph have been extensively studied in the
denser regime $d\gg\log N$. Complete eigenvector delocalization for $d\gg\log
N$ was established in HeKnowlesMarcozzi2018 ; EKYY1 . The local spectral
statistics in the bulk were proved to follow the universal GOE statistics in
EKYY2 ; UBY15 for $d\geqslant N^{o(1)}$. At the spectral edge, the local
spectral statistics were proved to be Tracy-Widom for $d\gg N^{1/3}$ EKYY2 ;
lee2018local with a transition from Tracy-Widom to Gaussian at $d\asymp
N^{1/3}$ huang2020transition , and Gaussian throughout the regime
$N^{o(1)}\leqslant d\ll N^{1/3}$ huang2020transition ; he2021fluctuations . In
fact, in the latter regime the Tracy-Widom statistics were recovered in
huang2022edge ; lee2021higher after subtraction of an explicit random shift.

The random $d$-regular graph is another canonical model of sparse random
graphs. Owing to the regularity constraint, it is much more homogeneous than
the Erdős-Rényi graph and only exhibits a delocalized phase. The eigenvectors
were proved to be completely delocalized for all $d\geqslant 3$ in BKY15 ;
BHY1 ; huang2021spectrum , and the local spectral statistics in the bulk were
shown to follow GOE statistics for $d\geqslant N^{o(1)}$ in BHKY15 and at the
edge Tracy-Widom statistics for $N^{o(1)}\leqslant d\ll N^{1/3}$ in
bauerschmidt2020edge ; huang2023edge or for $N^{2/3}\ll d\leqslant N/2$ in
he2022spectral .

Anderson transitions have been studied in a variety of models. The archetypal
example is the tight-binding, or Anderson, model on $\mathbb{Z}^{d}$
abou1973selfconsistent ; abou1974self ; anderson1978local ; aizenman2015random
. In dimensions $d\leqslant 2$, all eigenvectors of the Anderson model are
expected to be localized, while for $d\geqslant 3$ a coexistence of localized
and delocalized phases, separated by a mobility edge, is expected for small
enough disorder. So far, only the localized phase of the Anderson model has
been understood rigorously, starting from the landmark works FroSpe ; AizMol ;
see for instance aizenman2015random for a recent survey.

Although a rigorous understanding of the metal-insulator transition for the
Anderson tight-binding model is still elusive, some progress has been made for
random band matrices. Random band matrices MFDQS ; Wig ; CMI1 ; FM1
interpolate between the Anderson model and mean-field Wigner matrices. They
retain the $d$-dimensional structure of the Anderson model but have proved
more amenable to rigorous analysis. They are conjectured FM1 to have a similar
phase diagram as the Anderson model in dimensions $d\geqslant 3$. For $d=1$
much has been understood both in the localized Sch ; PSSS1 ;
cipolloni2022dynamical ; chen2022random and the delocalized So1 ; EKY2 ; EKYY3
; EK1 ; EK2 ; EK3 ; EK4 ; shcherbina2019universality ; BYY1 ; BYY2 ; BEYY1 ;
YY1 ; HM1 phases. For large enough $d$, recent progress in the delocalized
phase has been made in xu2022bulk ; yang2021delocalization ;
yang2022delocalization . A simplification of band matrices is the ultrametric
ensemble FOR1 , where the Euclidean metric of $\mathbb{Z}^{d}$ is replaced
with an ultrametric arising from a tree structure. For this model, a phase
transition was rigorously established in VW1 .

Another modification of the $d$-dimensional Anderson model is the Anderson
model on the Bethe lattice, an infinite regular tree corresponding to the case
$d=\infty$. For it, the existence of a delocalized phase was shown in ASW1 ;
FHS1 ; K94 . In AW1 ; AW2 it was shown that for unbounded random potentials
the delocalized phase exists for arbitrarily weak disorder. The underlying
mechanism is resonant delocalization, in which the exponentially decaying
tunnelling amplitudes between localization centres are counterbalanced by an
exponentially large number of possible channels through which tunnelling can
occur, so that Mott’s criterion is violated. As a consequence, the
eigenvectors hybridize.

Heavy-tailed Wigner matrices, or Lévy matrices, whose entries have
$\alpha$-stable laws for $0<\alpha<2$, were proposed in CB1 as a simple model
that exhibits a transition in the localization of its eigenvectors; we refer
to ALY1 for a summary of the predictions from CB1 ; TBT1 . In BG1 ; BG2 it was
proved that eigenvectors are weakly delocalized for energies in a compact
interval around the origin, and for $0<\alpha<2/3$ eigenvectors are weakly
localized for energies far enough from the origin. In ALY1 full
delocalization, as well as GOE local eigenvalue statistics, were proved in a
compact interval around the origin, and in ALM1 the law of the eigenvector
components was computed. Recently, by comparison to a limiting tree model, a
mobility edge was established in aggarwal2022mobility for $\alpha$ near $0$ or
$1$.

##### Conventions

Every quantity that is not explicitly called _fixed_ or a _constant_ is a
sequence depending on $N$. We use the customary notations $o(\cdot)$ and
$O(\cdot)$ in the limit $N\to\infty$. For nonnegative $X,Y$, if $X=O(Y)$ then
we also write $X\lesssim Y$, and if $X=o(Y)$ then we also write $X\ll Y$.
Moreover, we write $X\asymp Y$ to mean $X\lesssim Y$ and $Y\lesssim X$. We say
that an event $\Omega$ holds with _high probability_ if
$\mathbb{P}(\Omega)=1-o(1)$. Throughout this paper every eigenvector is
assumed to be normalized in $\ell^{2}([N])$. Finally, we use $\kappa\in(0,1)$
to denote a small positive constant, which is used to state assumptions and
definitions; a smaller $\kappa$ always results in a weaker condition.

### 1.2. Results

Let $\mathbb{G}\equiv\mathbb{G}(N,d/N)$ be the Erdős–Rényi graph with vertex
set $[N]$ and edge probability $d/N$ for $0\leqslant d\leqslant N$. Let
$A=(A_{xy})_{x,y\in[N]}\in\\{0,1\\}^{N\times N}$ be the adjacency matrix of
$\mathbb{G}$. Thus, $A=A^{*}$, $A_{xx}=0$ for all $x\in[N]$, and
$(A_{xy}\mathrel{\vbox{\hbox{.}\hbox{.}}}x<y)$ are independent
$\operatorname{Bernoulli}(d/N)$ random variables. Define the rescaled
adjacency matrix

$H\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=A/\sqrt{d}\,.$

We always assume that $d$ satisfies

$\sqrt{\log N}\,\log\log N\ll d\leqslant 3\log N\,.$ (1.5)

Owing to the nonzero expectation of $H$, it is well known that the largest
eigenvalue of $H$, denoted by $\lambda_{1}(H)$, is an outlier separated from
the rest of the spectrum (see e.g. Proposition 3.4 (iv) below), and we shall
always discard it from our discussion. The lower bound of (1.5) is made for
convenience, to ensure that $\lambda_{1}(H)$ is separated from the bulk
spectrum555In fact, to ensure the separation, the weaker lower bound
$d\gg\sqrt{\log N/\log\log N}$ would be sufficient; see KrivelevichSudakov and
(ADK21, , Remark 1.4) for detailed explanations. We impose the slightly
stronger lower bound in (1.5) for convenience, as it allows us to directly
import results from ADK20 that were proved under this condition.; the upper
bound of (1.5) is made without loss of generality, since for $d\geqslant 3\log
N$ the localized phase does not exist and the entire spectrum is known to
belong to the delocalized phase ADK20 ; ADK_delocalized .

We denote by $B_{r}(x)$ (respectively by $S_{r}(x)$) the closed ball
(respectively the sphere) of radius $r$ with respect to the graph distance of
$\mathbb{G}$ around the vertex $x$. We refer to Section 2.1 below for a full
account of notations used throughout this paper.

The localized phase is characterized by a threshold $\alpha^{*}$ defined, for
any fixed $\kappa\in(0,1)$ and $\mu\in[0,1]$, as

$\alpha^{*}\equiv\alpha^{*}(\mu)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\max\Big{\\{}\inf\big{\\{}\alpha>0:\mathbb{P}(\alpha_{1}\geqslant\alpha)\leqslant
N^{\mu-1}\big{\\}},2+\kappa\Big{\\}}\,.$ (1.6)

We refer to Appendix C below for the basic qualitative properties of
$\alpha^{*}$ as well as a graph. We shall show exponential localization for
any eigenvector with eigenvalue $\lambda$ satisfying the condition

$\lambda\neq\lambda_{1}(H)\,,\qquad\lvert\lambda\rvert\geqslant\Lambda(\alpha^{*}(\mu))+\kappa\,,$
(1.7)

for sufficiently small $\mu>0$. In particular, the number of eigenvalues
$\lambda$ satisfying (1.7) is with high probability $N^{\mu+o(1)}$ as
$\kappa\to 0$; see Remark 1.2 below.

#### 1.2.1. Exponential localization

Our main result is the following theorem. We recall that by convention all
eigenvectors are normalized.

######  Theorem 1.1 (Exponential localization).

Suppose that (1.5) holds. Fix $\kappa\in(0,1)$ and $\mu\in(0,1/24)$. Then
there is a constant $c\in(0,1)$ depending on $\kappa$ such that, with high
probability, for any eigenvector $\mathbf{w}=(w_{x})_{x\in[N]}$ of $H$ with
eigenvalue $\lambda$ satisfying (1.7), there exists a unique vertex $x\in[N]$
with $\alpha_{x}>\alpha^{*}(\mu)$ such that

$w_{x}^{2}={\frac{\alpha_{x}-2}{2(\alpha_{x}-1)}}+o(1)\,,\qquad\qquad\lVert\mathbf{w}|_{B_{i}(x)^{c}}\rVert\lesssim\sqrt{\alpha_{x}}(1-c)^{i}\,,$
(1.8)

for all $i\in\mathbb{N}$ with $1\leqslant i\leqslant\frac{1}{6}\frac{\log
N}{\log d}$.

######  Remark 1.2 (Eigenvalue locations).

The eigenvalue $\lambda$ of the eigenvector $\mathbf{w}$ and the associated
vertex $x$ from Theorem 1.1 satisfy
$\lvert\lambda\rvert=\Lambda(\alpha_{x})+o(1)$ with high probability. This
follows from (2.4) and (3.3) below.

The eigenvalue locations in the localized phase were previously studied in
(ADK19, , Theorem 2.1) (see also (ADK20, , Theorem 1.7)). In particular, if
$d>b_{*}\log N$ then the localized phase does not exist (see (ADK19, , Remark
2.5)) and there is no eigenvalue of $H$ satisfying (1.7). Conversely, if
$d\leqslant(b_{*}-\varepsilon)\log N$ for some constant $\varepsilon>0$ then
for small enough $\kappa>0$ there is a polynomial number of eigenvalues
satisfying (1.7), by (ADK20, , Theorem 1.7). By the same argument, if $d/\log
N$ is small enough, then with high probability $N^{\mu+o(1)}$ eigenvalues of
$H$ satisfy (1.7) as $N\to\infty$ and $\kappa\to 0$.

######  Remark 1.3 (Conditions in Theorem 1.1).

The exponential decay in Theorem 1.1 holds up to the scale $\frac{\log N}{\log
d}$ of the diameter of $\mathbb{G}$. The upper bound $1/24$ and the factor
$1/6$ are not optimal (see the discussion in Appendix F), and they can be
improved with some extra effort, which we however refrain from doing here.

######  Remark 1.4 (Optimal exponential decay).

If $\mu$ is sufficiently small then the rate $1-c$ of exponential decay from
(1.8) can be made explicit. Suppose (1.5). Then for each small enough constant
$\varepsilon>0$ and small enough constant $\mu>0$, depending on $\varepsilon$,
with high probability, for any eigenvector $\mathbf{w}$ of $H$ with eigenvalue
$\lambda$ satisfying (1.7), there exists a unique vertex $x\in[N]$ with
$\alpha_{x}>\alpha^{*}(\mu)$ such that

$\lVert\mathbf{w}|_{B_{i}(x)^{c}}\rVert\lesssim\sqrt{\alpha_{x}}\bigg{(}\frac{1+O(\varepsilon)}{\sqrt{\alpha_{x}-1}}\bigg{)}^{i+1}$
(1.9)

for each $i\in\mathbb{N}$ satisfying $i\ll\frac{\log N}{\log
d}\frac{1}{\log\frac{10\log N}{d}}$. This follows from (2.3) and Proposition
4.3 below.

The rate of decay in (1.9) is optimal up to the error term $O(\varepsilon)$.
Indeed, by Theorem 1.6 and the explicit form (1.10)–(1.11) below, we find that

$\lVert\mathbf{w}|_{B_{i}(x)^{c}}\rVert\asymp\sqrt{\alpha_{x}}\biggl{(}\frac{1}{\sqrt{\alpha_{x}-1}}\biggr{)}^{i+1}+o(1)\,.$

for any fixed $i\in\mathbb{N}$. In particular, (1.9) improves the rate
$\frac{q^{i}}{(1-q)^{2}}$ with
$q=(2+o(1))\frac{\sqrt{\alpha_{x}-1}}{\alpha_{x}}$ obtained in (ADK21, ,
Theorem 1.7) at the spectral edge, corresponding to
$\alpha_{x}=(1+o(1))\alpha^{*}(0)$.

#### 1.2.2. Geometric structure of eigenvectors

Next, we describe the precise geometric structure of the eigenvectors in the
localized phase. For any vertex $x$ with $\alpha_{x}>2$ and radius
$r\in\mathbb{N}^{*}$, we shall define two local vectors, $\mathbf{w}_{r}(x)$
and $\mathbf{v}_{r}(x)$, which depend only on $\mathbb{G}$ in the ball
$B_{r}(x)$. If $\mathbf{w}$ is an eigenvector of $H$ as in Theorem 1.1 with
associated vertex $x$, then $\mathbf{w}$ will be well approximated by
$\mathbf{w}_{r}(x)$ and $\mathbf{v}_{r}(x)$ for suitably chosen $r\gg 1$.

To define these local vectors, we need the following definitions. Let
$r\in\mathbb{N}^{*}$. For $\alpha>2$ define the positive sequence
$(u_{i}(\alpha))_{i=0}^{r-1}$ through

$u_{1}(\alpha)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\biggl{(}\frac{\alpha}{\alpha-1}\biggr{)}^{1/2}u_{0}(\alpha)\,,\qquad
u_{i}(\alpha)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\biggl{(}\frac{1}{\alpha-1}\biggr{)}^{(i-1)/2}u_{1}(\alpha)\qquad(1\leqslant
i\leqslant r-1)\,.$ (1.10)

We normalize the sequence by choosing $u_{0}(\alpha)>0$ such that
$\sum_{i=0}^{r-1}u_{i}(\alpha)^{2}=1$.

######  Definition 1.5 (Localization profile vectors $\mathbf{w}_{r}(x)$ and
$\mathbf{v}_{r}(x)$).

Let $r\in\mathbb{N}^{*}$ and $x\in[N]$.

  1. (i)

Denote by $\mathbf{w}_{r}(x)$ an eigenvector of $H|_{B_{r}(x)}$ associated
with its largest eigenvalue, chosen so that its value at $x$ is nonnegative.
Here $H|_{B_{r}(x)}$ denotes the matrix $H$ restricted to the vertices in
$B_{r}(x)$ (See Section 2.1 below.)

  2. (ii)

For $\alpha_{x}>2$ and $(u_{i}(\alpha))_{i=0}^{r-1}$ as in (1.10), define

$\qquad\mathbf{v}_{r}(x)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\sum_{i=0}^{r-1}u_{i}(\alpha_{x})\frac{\mathbf{1}_{S_{i}(x)}}{|S_{i}(x)|^{1/2}}\,,$
(1.11)

where $\mathbf{1}_{S_{i}(x)}$ denotes the indicator function of the sphere
$S_{i}(x)$.

Note that $\mathbf{w}_{r}(x)$ is unique by the Perron-Frobenius theorem for
irreducible matrices with nonnegative entries.

######  Theorem 1.6 (Localization profile).

Suppose that (1.5) holds and fix $\kappa\in(0,1)$ and $\mu\in(0,1/24)$. With
high probability, for any eigenvector $\mathbf{w}$ of $H$ with eigenvalue
$\lambda$ satisfying (1.7), there exists a unique vertex $x\in[N]$ with
$\alpha_{x}>\alpha^{*}(\mu)$ such that666We assume that the sign of
$\mathbf{w}$ is chosen suitably.

$\mathbf{w}=\mathbf{w}_{r}(x)+o(1)=\mathbf{v}_{r}(x)+o(1)$ (1.12)

for each $r\in\mathbb{N}^{*}$ satisfying $\log d\ll
r\leqslant\frac{1}{6}\frac{\log N}{\log d}$. Here, $o(1)$ is meant with
respect to the Euclidean norm on $\mathbb{R}^{N}$.

In particular, $\mathbf{w}$ has locally the radial exponentially decaying
structure of $\mathbf{v}_{r}(x)$.

#### 1.2.3. Mobility edge and localization length

Finally, we combine the results of this paper with those obtained for the
delocalized phase in ADK20 ; ADK_delocalized to establish a mobility edge at
$\pm 2$ for certain values of $d$, and analyse the structure of the
eigenvectors quantitatively in the vicinity of the mobility edge.

######  Theorem 1.7 (Mobility edge).

Fix $\kappa>0$ and suppose that
$\frac{23}{24}+\kappa\leqslant\frac{d}{b_{*}\log N}\leqslant 1-\kappa$. Then,
with high probability, for any eigenvector $\mathbf{w}$ of $H$ with eigenvalue
$\lambda\neq\lambda_{1}(H)$ we have the following dichotomy.

  1. (i)

(Localized phase) If $\lvert\lambda\rvert\geqslant 2+\kappa$ then $\mathbf{w}$
is exponentially localized as in (1.8) and (1.12).

  2. (ii)

(Delocalized phase) If $\lvert\lambda\rvert\leqslant 2-\kappa$ then
$\mathbf{w}$ is completely delocalized in the sense that

$\lVert\mathbf{w}\rVert_{\infty}^{2}\leqslant N^{-1+o(1)}\,.$ (1.13)

Both phases in Theorem 1.7 are nonempty under the assumption on $d$; see
Section 1.1 and (ADK19, , Remark 2.5). Theorem 1.7 establishes a dichotomy
because (1.8) and (1.13) are mutually exclusive, since
$\lVert\mathbf{w}\rVert_{\infty}^{2}\geqslant
w_{x}^{2}=\frac{\alpha_{x}-2}{2(\alpha_{x}-1)}+o(1)\gtrsim 1$ if
$\alpha_{x}>\alpha^{*}(\mu)\geqslant 2+\kappa$.

Next, we investigate the spatial extent of the eigenvectors near the mobility
edge. To that end, we use the following notion of localization length. With
each normalized vector $\mathbf{w}$ we associate the length

$\ell(\mathbf{w})\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\min_{x\in[N]}\sum_{y\in[N]}\mathrm{d}(x,y)\,w_{y}^{2}\,,$
(1.14)

where $\mathrm{d}(x,y)$ denotes the distance from $x$ to $y$ in the graph
$\mathbb{G}$. Regarding $y\mapsto w_{y}^{2}$ as a probability measure on
$[N]$, the quantity $\ell(\mathbf{w})$ expresses the minimal expected distance
from a reference vertex $x$. The minimizing vertex $x$ has the interpretation
of a localization centre for $\mathbf{w}$.

Denote by $\operatorname{diam}(\mathbb{G})$ the diameter777We recall that the
diameter of a connected graph is the length of its longest geodesic. If the
graph is disconnected, then its diameter is the maximal diameter of its
connected components. of $\mathbb{G}$. It is a classical fact ChungLu_diameter
that with high probability $\operatorname{diam}(\mathbb{G})=\frac{\log N}{\log
d}(1+o(1))$ as long as $d\gg 1$.

######  Theorem 1.8 (Localization length).

Fix $\kappa>0$ and suppose that
$\frac{23}{24}+\kappa\leqslant\frac{d}{b_{*}\log N}\leqslant 1-\kappa$. Then,
with high probability, for any eigenvector $\mathbf{w}$ of $H$ with eigenvalue
$\lambda\neq\lambda_{1}(H)$ we have

$\ell(\mathbf{w})=\begin{cases}\frac{\lvert\lambda\rvert}{2\sqrt{\lambda^{2}-4}}+o(1)&\text{if
}\lvert\lambda\rvert\geqslant 2+\kappa\\\
\operatorname{diam}(\mathbb{G})(1+o(1))&\text{if }\lvert\lambda\rvert\leqslant
2-\kappa\,.\end{cases}$ (1.15)

######  Remark 1.9.

By the same proof, the first estimate of (1.15) holds also for all
eigenvectors satisfying the conditions of Theorem 1.1. Moreover, the constant
$\frac{23}{24}$ is not optimal and can be reduced with some extra effort.

Theorem 1.8 shows that the localization length diverges as one approaches the
mobility edge from the localized phase, and that it equals the diameter of the
graph in the delocalized phase. See Figure 1.3 for an illustration.

$\lambda$
---
$\lambda_{\max}$
---
$2$
---
$0$
---
$\operatorname{diam}(\mathbb{G})$
---
$\ell$
---
$\frac{\lambda}{2\sqrt{\lambda^{2}-4}}$
---
Figure 1.3: An illustration of the behaviour of the localization length (1.14)
around the mobility edge, established in Theorem 1.8. We plot the asymptotic
localization length $\ell$ of an eigenvector with eigenvalue $\lambda$ as a
function of $\lambda$. Here $\frac{d}{b_{*}\log N}$ is a fixed number in
$[\frac{23}{24}+\kappa,1-\kappa]$. The spectrum is asymptotically given by the
interval $[-\lambda_{\max},\lambda_{\max}]$. We only draw a portion of the
spectrum near the right edge. Below the mobility edge $2$, the localization
length is $\operatorname{diam}(\mathbb{G})=\frac{\log N}{\log d}(1+o(1))$.
Above the mobility edge $2$, the localization length is finite and diverges as
one approaches the mobility edge.

##### Structure of the paper

We conclude with a short summary of the structure of the paper. In Section 2,
we collect a few basic notations, then state the three core propositions of
the paper: Proposition 2.2, which gives exponential decay of the approximate
eigenvectors, Proposition 2.3, which compares the approximate eigenvalues with
the true eigenvalues, and Proposition 2.4, which estimates the spacing between
neighbouring approximate eigenvalues. After stating them, we use them to
deduce Theorem 1.1 in Section 2.2. Then, we sketch the proofs of these three
propositions in Section 2.3. Theorems 1.6, 1.7, and 1.8 are proved in the
short Sections 2.4, 2.5, and 2.6, respectively. Section 3 is devoted to
preliminary results on the graph $\mathbb{G}$, its spectrum, and its Green
function. Sections 4, 5 and 6 are devoted to the proofs of Propositions 2.2,
2.3, and 2.4, respectively. In the appendices, we collect some auxiliary
results and basic tools.

## 2\. Proof of main results

The rest of the paper is devoted to the proofs of Theorems 1.1, 1.6, 1.7, and
1.8. Throughout, $\kappa\in(0,1)$ denotes an arbitrary positive constant.

### 2.1. Basic notations

We write $\mathbb{N}=\\{0,1,2,\dots\\}$. We set
$[n]\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\\{1,\ldots,n\\}$
for any $n\in\mathbb{N}^{*}$ and
$[0]\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\emptyset$. We
write $\lvert X\rvert$ for the cardinality of a finite set $X$. For
$X\subset[N]$ we write
$X^{c}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=[N]\setminus X$.
We use $\mathbbm{1}_{\Omega}$ to denote the indicator function of an event
$\Omega$.

Vectors in $\mathbb{R}^{N}$ are denoted by boldface lowercase Latin letters
like $\mathbf{u}$, $\mathbf{v}$ and $\mathbf{w}$. We use the notation
$\mathbf{v}=(v_{x})_{x\in[N]}\in\mathbb{R}^{N}$ for the entries of a vector.
We denote by
$\operatorname{supp}\mathbf{v}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\\{x\in[N]\mathrel{\vbox{\hbox{.}\hbox{.}}}v_{x}\neq
0\\}$ the support of a vector $\mathbf{v}$. We denote by
$\langle\mathbf{v}\mspace{2.0mu},\mathbf{w}\rangle=\sum_{x\in[N]}v_{x}w_{x}$
the Euclidean scalar product on $\mathbb{R}^{N}$ and by
$\lVert\mathbf{v}\rVert=\sqrt{\langle\mathbf{v}\mspace{2.0mu},\mathbf{v}\rangle}$
the induced Euclidean norm. For $X\subset[N]$ we set
$\mathbf{v}|_{X}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=(v_{x}\mathbbm{1}_{x\in
X})_{x\in[N]}$. For any $x\in[N]$, we define the standard basis vector
$\mathbf{1}_{x}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=(\delta_{xy})_{y\in[N]}\in\mathbb{R}^{N}$,
so that $w_{x}=\langle\mathbf{1}_{x}\mspace{2.0mu},\mathbf{w}\rangle$. To any
subset $S\subset[N]$ we assign the vector $\mathbf{1}_{S}\in\mathbb{R}^{N}$
given by
$\mathbf{1}_{S}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\sum_{x\in
S}\mathbf{1}_{x}$. In particular, $\mathbf{1}_{\\{x\\}}=\mathbf{1}_{x}$.

We denote by $\mathrm{d}(x,y)$ the distance between the vertices $x,y\in[N]$
with respect to the graph $\mathbb{G}$, i.e. the number of edges in the
shortest path connecting $x$ and $y$. For $r\in\mathbb{N}$ and $x\in[N]$, we
denote by
$B_{r}(x)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\\{y\in[N]\mathrel{\vbox{\hbox{.}\hbox{.}}}\mathrm{d}(x,y)\leqslant
r\\}$ the closed ball of radius $r$ around $x$, and by
$S_{r}(x)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\\{y\in[N]\mathrel{\vbox{\hbox{.}\hbox{.}}}\mathrm{d}(x,y)=r\\}$
the sphere of radius $r$ around the vertex $x$. For $X\subset[N]$ we denote by
$\mathbb{G}|_{X}$ the subgraph on $X$ induced by $\mathbb{G}$.

For a matrix $M\in\mathbb{R}^{N\times N}$, $\lVert M\rVert$ is its operator
norm induced by the Euclidean norm on $\mathbb{R}^{N}$. For an $N\times N$
Hermitian matrix $M$, we denote by
$\lambda_{1}(M)\geqslant\lambda_{2}(M)\geqslant\cdots\geqslant\lambda_{N}(M)$
the ordered eigenvalues of $M$. For an $N\times N$ matrix
$M\in\mathbb{R}^{N\times N}$ and a subset $X\subset[N]$, we introduce the
$N\times N$ matrices
$M|_{X}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=(M_{xy}\mathbbm{1}_{x,y\in
X})_{x,y\in[N]}$ as well as
$M^{(X)}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=M|_{X^{c}}$
with entries $M^{(X)}_{xy}=M_{xy}\mathbbm{1}_{x,y\notin X}$.

### 2.2. Exponential localization – proof of Theorem 1.1

In this section, after introducing some notation and stating the core
propositions of the proof, we use them to prove our main result, Theorem 1.1.
Recalling the definition of $\Lambda$ from (1.4), we introduce the
$\mu$-dependent sets

$\displaystyle{\mathcal{V}}$
$\displaystyle\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\bigl{\\{}x\in[N]\mathrel{\vbox{\hbox{.}\hbox{.}}}\alpha_{x}\geqslant\alpha^{*}(\mu)\bigr{\\}}\,,$
(2.1) $\displaystyle{\mathcal{W}}$
$\displaystyle\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\bigl{\\{}x\in\mathcal{V}\mathrel{\vbox{\hbox{.}\hbox{.}}}\Lambda(\alpha_{x})\geqslant\Lambda(\alpha^{*}(\mu))+\kappa/2\bigr{\\}}\,.$
(2.2)

By definition, $\mathcal{W}\subset\mathcal{V}$.

The following definition introduces the fundamental approximate eigenvalues
and eigenvectors underlying our proof.

######  Definition 2.1 ($\lambda(x)$ and $\mathbf{u}(x)$).

For any $x\in\mathcal{W}$, we abbreviate
$\lambda(x)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\lambda_{2}(H^{(\mathcal{V}\setminus\\{x\\})})$.
Moreover, we denote by $\mathbf{u}(x)$ a normalized eigenvector of
$H^{(\mathcal{V}\setminus\\{x\\})}$ with eigenvalue $\lambda(x)$ satisfying
$\langle\mathbf{1}_{x}\mspace{2.0mu},\mathbf{u}(x)\rangle\geqslant 0$.

As we shall see, with high probability $\lambda(x)$ is a simple eigenvalue and
hence $\mathbf{u}(x)$ is unique (see Corollary 3.6 below).

The proof of Theorem 1.1 consists of three main steps, which are the content
of the three following propositions. The next proposition states that
$\mathbf{u}(x)$ has the exponential decay claimed in Theorem 1.1 for
$\mathbf{w}$. It is proved in Section 4 below.

######  Proposition 2.2 (Exponential decay of $\mathbf{u}(x)$).

Suppose that (1.5) holds. Then there is a constant $c\in(0,1)$ such that, for
each fixed $\mu\in[0,1/3)$, with high probability, for each $x\in\mathcal{W}$,

$\langle\mathbf{1}_{x}\mspace{2.0mu},\mathbf{u}(x)\rangle=\sqrt{\frac{\alpha_{x}-2}{2(\alpha_{x}-1)}}+o(1),\qquad\qquad\lVert\mathbf{u}(x)|_{B_{i}(x)^{c}}\rVert\lesssim\sqrt{\alpha_{x}}(1-c)^{i}$

for all $i\in\mathbb{N}$ satisfying $1\leqslant
i\leqslant\min\big{\\{}\frac{1}{5}-\frac{\mu}{4},\frac{1}{3}-\mu\big{\\}}\frac{\log
N}{\log d}-2$.

In the proof of Theorem 1.1, the next two propositions will be used to
conclude that any eigenvector of $H$ whose associated eigenvalue satisfies
(1.7) is close to $\mathbf{u}(x)$ for some $x\in\mathcal{W}$. Given
Proposition 2.2, this will directly imply Theorem 1.1.

The next proposition, Proposition 2.3, states that $\lambda(x)$ and
$\mathbf{u}(x)$ are approximate eigenvalues and eigenvectors of $H$,
respectively, with an error bounded by an inverse power of $N$. Moreover, up
to such an error, each eigenvalue of $H$ satisfying (1.7) is approximated by
$\lambda(x)$ for some $x\in\mathcal{W}$. In particular, it provides an upper
bound for the tunnelling amplitude, in the sense of (1.2), for the global
approximate eigenvectors from Definition 2.1. Its proof is given in Section 5
below.

######  Proposition 2.3 (Approximate eigenvalues).

Suppose (1.5). Fix $\mu\in[0,1/4)$ and $\zeta\in[0,1/2-3\mu/2)$. Then, with
high probability,

$\operatorname{spec}(H)\cap\mathcal{I}=\\{{\lambda}(x)+\varepsilon_{x}\mathrel{\vbox{\hbox{.}\hbox{.}}}x\in\mathcal{W}\\}\cap\mathcal{I}\,,\qquad\qquad\mathcal{I}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=[\Lambda(\alpha^{*})+3\kappa/4,\sqrt{d}/2]$

counted with multiplicity and

$\max_{x\in\mathcal{W}}\max\big{\\{}\lvert\varepsilon_{x}\rvert,\,\|(H-\lambda(x))\mathbf{u}(x)\|\big{\\}}\leqslant
N^{-\zeta}\,.$

The next proposition establishes a spacing of at least $N^{-\eta}$ between the
approximate eigenvalues $(\lambda(x))_{x\in\mathcal{W}}$, for large enough
$\eta$. It is proved in Section 6 below.

######  Proposition 2.4 (Eigenvalue spacing).

Suppose (1.5). Fix $\mu\in(0,1/24)$ and $\eta>8\mu$. Then, with high
probability,

$\lvert\lambda(x)-\lambda(y)\rvert\geqslant N^{-\eta}$

for all $x$, $y\in\mathcal{W}$ with $x\neq y$.

We now deduce Theorem 1.1 from Propositions 2.2, 2.3, and 2.4.

###### Proof of Theorem 1.1.

Let $\lambda$ be an eigenvalue of $H$ satisfying (1.7), and $\mathbf{w}$ an
associated, normalized eigenvector. Fix $\zeta\in(8\mu,1/3)$ and
$\eta\in(8\mu,\zeta)$. As $\mu<1/24$, both intervals are nonempty and
$\zeta<1/2-3\mu/2$. Thus, Propositions 2.3 and 2.4 are applicable with these
choices of $\zeta$ and $\eta$. We shall show below that, on the intersection
of the high–probability events of Propositions 2.3 and 2.4, there exists a
unique $x\in\mathcal{W}$ such that

$\mathbf{w}=\mathbf{u}(x)+O(N^{\eta-\zeta})$ (2.3)

(under suitable choice of the sign of $\mathbf{w}$). Thus, Theorem 1.1 follows
from $\eta<\zeta$ and Proposition 2.2 as $\exp\big{(}\frac{1}{6}\frac{\log
N}{\log d}\log(1-c)\big{)}\gg N^{-\varepsilon}$ for any $\varepsilon>0$.

What remains is the proof of (2.3). This is an application of perturbation
theory in the form of Lemma E.2, whose conditions we justify now. Note first
that, combining (5.24) below and the trivial fact
$\lambda_{1}(\mathbb{E}H)=\sqrt{d}(1+o(1))$ with rank-one eigenvalue
interlacing, we conclude that with high probability
$\lambda_{1}(H)=\sqrt{d}(1+o(1))$ and $\lambda_{2}(H)\leqslant\sqrt{d}/2$.
Hence, the eigenvalue $\lambda$ satisfying (1.7) lies in
$[\Lambda(\alpha^{*}(\mu))+\kappa,d/2]$. From Propositions 2.3 and 2.4 with
$\eta<\zeta$, we conclude that

$\operatorname{dist}(\lambda,\operatorname{spec}(H)\setminus\\{\lambda\\})\geqslant
N^{-\eta}-2N^{-\zeta},\qquad\qquad\lvert\lambda-\lambda(x)\rvert\leqslant
N^{-\zeta}$ (2.4)

for a unique $x\in\mathcal{W}$ (see Figure 2.1). In particular, as
$\eta<\zeta$, there is $\Delta\asymp N^{-\eta}$ such that $\lambda$ is the
unique eigenvalue of $H$ in $[\lambda(x)-\Delta,\lambda(x)+\Delta]$. Moreover,
$\lVert(H-\lambda(x))\mathbf{u}(x)\rVert\leqslant N^{-\zeta}$ by Proposition
2.3. Therefore, all conditions of Lemma E.2 are satisfied, and it implies
(2.3). This concludes the proof of Theorem 1.1. ∎

$\\{\lambda(x)\mathrel{\vbox{\hbox{.}\hbox{.}}}x\in\mathcal{W}\\}$
---
$\operatorname{spec}(H)$
---
$N^{-\eta}$
---
$2N^{-\zeta}$
---
$\Lambda(\alpha^{*})+\kappa$
---
Figure 2.1: An illustration of the setup for the perturbation theory in the
proof of Theorem 1.1. We draw two instances of the interval
$[\Lambda(\alpha^{*})+\kappa,\infty)$. On the top line, we draw each
$\lambda(x)$ for $x\in\mathcal{W}$ as blue dot. Each dot is surrounded by a
blue buffer of width $N^{-\eta}$. By Proposition 2.4, these buffers do not
intersect with high probability. On the bottom line, we draw each eigenvalue
of $H$ as red dot. Each dot on the top line gives rise to a red region on the
bottom line of width $2N^{-\zeta}$. Since $\zeta>\eta$, the red regions are
disjoint. By Proposition 2.3, each red region contains exactly one eigenvalue
of $H$ and each eigenvalue of $H$ is contained in a red region. Hence, the
eigenvalues of $H$ are separated by at least $N^{-\eta}/2$.

By choosing $\eta$ in (2.4) of the proof of Theorem 1.1 sufficiently small, we
conclude the following result.

######  Corollary 2.5 (Eigenvalue spacing of $H$).

Suppose (1.5). Fix $\mu\in(0,1/24)$ and $\eta>8\mu$. Then, with high
probability,

$\operatorname{dist}(\lambda,\operatorname{spec}(H)\setminus\\{\lambda\\})\geqslant
N^{-\eta}\,,$

for every
$\lambda\in\operatorname{spec}(H)\cap[\Lambda(\alpha^{*}(\mu))+\kappa,\infty)$.

######  Remark 2.6 (Eigenvalue spacing in critical regime).

In the critical regime, i.e. when $d\asymp\log N$, the lower bound on $\eta$
in the conditions of Proposition 2.4 and Corollary 2.5 can be weakened to
$\eta>4\mu$. Details can be found in Remark 6.2 below.

######  Remark 2.7 (Eigenvector mass on vertices in
$\mathcal{V}\setminus\\{x\\}$).

With high probability the following holds. Let $\mathbf{w}$ be an eigenvector
of $H$ associated with the vertex $x$ as in Theorem 1.1. Then, from
$\mathbf{u}(x)|_{\mathcal{V}\setminus\\{x\\}}=0$ and (2.3), we conclude

$\lVert\mathbf{w}|_{\mathcal{V}\setminus\\{x\\}}\rVert\lesssim
N^{-\varepsilon}$

for any small enough $\varepsilon>0$.

### 2.3. Sketch of the proof

In this subsection we sketch the proof of Theorem 1.1. We use the definitions
and notations from Sections 2.1 and 2.2.

The basic strategy is to find an orthogonal matrix $U$, a diagonal $n\times n$
matrix $\Theta=\operatorname{diag}(\theta_{1},\dots,\theta_{n})$, a symmetric
$(N-n)\times(N-n)$ matrix $X$, and a symmetric $N\times N$ matrix $E$ such
that the following holds. In the basis of the columns
$\mathbf{u}_{1},\dots,\mathbf{u}_{N}$ of $U$, the matrix $H$ has the form

$U^{*}HU=\begin{pmatrix}\Theta&0\\\ 0&X\end{pmatrix}+E\,,$ (2.5)

where the matrices $E$ and $X$ satisfy

$\displaystyle\|E\|\ll\min\big{\\{}\lvert\theta_{i}-\theta_{j}\rvert\mathrel{\vbox{\hbox{.}\hbox{.}}}i\neq
j\big{\\}},$ (2.6a)
$\displaystyle\operatorname{dist}(\operatorname{spec}(X),I)\geqslant\kappa\,;$
(2.6b)

here $I$ denotes the interval containing the eigenvalues of $H$ that we are
interested in (cf. (1.7)). We call the first $n$ columns
$\mathbf{u}_{1},\dots,\mathbf{u}_{n}$ of $H$ _profile vectors_.

If $\lVert E\rVert=o(1)$ then, for each $i\in[n]$, the vector $\mathbf{u}_{i}$
is an approximate eigenvector of $H$ with approximate eigenvalue $\theta_{i}$.
Unlike approximate eigenvalues, in general approximate eigenvectors have
nothing to do with the actual eigenvectors. For $\mathbf{u}_{i}$ to be close
to an eigenvector of $H$, we require the stronger estimates (2.6), which can
be regarded as a version of Mott’s criterion in terms of the profile vectors
encoded by $\mathbf{u}_{1},\dots,\mathbf{u}_{n}$. Localization then follows
provided the $\mathbf{u}_{i}$ are shown to be localized.

In ADK19 , it was showed that there is a one-to-one correspondence between
eigenvalues of $H$ in the semilocalized phase
$[2+o(1),\infty)\setminus\\{\lambda_{1}(H)\\}$ and vertices $x$ of
$\mathbb{G}$ with normalized degree $\alpha_{x}\geqslant 2+o(1)$.
Subsequently, in ADK20 ; ADK21 , the eigenvectors of $H$ in the semilocalized
phase were investigated using the decomposition (2.5). There, the profile
vectors $\mathbf{u}_{i}$ were supported in balls $B_{r}(x)$ around vertices
$x$ of sufficiently large $\alpha_{x}$, where $r\gg 1$. We refer to such
vectors as _local profile vectors_ : they are spatially localized (in the
graph distance) and their supports are disjoint. Examples of such local
profile vectors are $\mathbf{w}_{r}(x)$ and $\mathbf{v}_{r}(x)$ for
$x\in\mathcal{W}$, defined in Definition 1.5 (others were defined in ADK20 ;
ADK21 ).

The local profile vectors are exponentially decaying with a rate $c>0$
depending on $b$ and the energy. The best possible error estimate for
$\lVert(H-\theta_{i})\mathbf{u}_{i}\rVert$ under the condition that
$\mathbf{u}_{i}$ is supported in $B_{r}(x)$ is obtained by choosing
$\mathbf{u}_{i}=\mathbf{w}_{r}(x)$, the top eigenvector of $H|_{B_{r}(x)}$; in
that case the error is purely a boundary term of order $\mathrm{e}^{-cr}$. If
the supports of the profile vectors are separated by more than 1 (in the graph
distance) then it is easy to see that $\lVert
E\rVert\leqslant\max_{i}\lVert(H-\theta_{i})\mathbf{u}_{i}\rVert$ (see also
our formulation of Mott’s criterion (1.2)). Hence, the best possible error
estimate for $\lVert E\rVert$ is $\mathrm{e}^{-cr}$. Since the diameter of
$\mathbb{G}$ is $\frac{\log N}{\log d}(1+o(1))$ with high probability, the
best bound resulting from this approach is $\lVert E\rVert\lesssim N^{-c/\log
d}=N^{-o(1)}$ for some constant $c>0$. However, inside the semilocalized phase
this bound is always much larger than the typical eigenvalue spacing
$N^{-\eta}$ for some $\eta>0$. Recalling the condition (2.6a), we conclude
that any approach to prove localization in the semilocalized phase that uses
local profile vectors is doomed to fail.

The reason why any approach based on local profile vectors fails is that local
profile vectors (such as $\mathbf{w}_{r}(x)$) are supported on balls
containing a comparatively small set of vertices, and the mass of the true
eigenvectors outside of such balls is not small enough to be fully negligible.
This leads us to introduce the _global profile vectors_ $\mathbf{u}(x)$,
$x\in\mathcal{W}$, from Definition 2.1, with associated approximate
eigenvalues $\lambda(x)$. They are defined as the second eigenvector-
eigenvalue pair of the matrix $H^{(\mathcal{V}\setminus\\{x\\})}$. Thus,
$\Theta=\operatorname{diag}((\lambda(x))_{x\in\mathcal{W}})$ and the first
$n=\lvert\mathcal{W}\rvert$ columns of $U$ are given by the orthonormalization
of the family $(\mathbf{u}(x))_{x\in\mathcal{W}}$. The global profile vector
$\mathbf{u}(x)$ and the best possible local profile vector $\mathbf{w}_{r}(x)$
are each defined as eigenvectors of the graph after removal of a set of
vertices, $\lvert\mathcal{V}\rvert-1\sim N^{\mu}\ll N$ vertices for the former
and $\lvert B_{r}(x)^{c}\rvert\sim N$ vertices for the latter. This suggests
that $\mathbf{u}(x)$ is a better approximation of a true eigenvector of $H$.
The price to pay is that its definition is less explicit, and, crucially, the
family $(\mathbf{u}(x))_{x\in\mathcal{W}}$ is not orthogonal owing to the
global profile vectors having nonzero overlaps. As explained below, the need
to control the overlaps of the global profile vectors presents a serious
complication.

The proof of Theorem 1.1 consists of three main steps:

  1. (i)

exponential decay for $\mathbf{u}(x)$ around $x$,

  2. (ii)

$\|E\|\leqslant N^{-\zeta}$ and $\operatorname{spec}(X)$ is separated from
$I$,

  3. (iii)

$\min_{x\neq y\in\mathcal{W}}|\lambda(x)-\lambda(y)|\geqslant N^{-\eta}$,

for some constants $\zeta>\eta>0$ (see also Section 2.3.4 below). These items
corresponds to Propositions 2.2, 2.3, and 2.4, respectively. We outline their
proofs in Sections 2.3.1, 2.3.2, and 2.3.3, respectively.

#### 2.3.1. Exponential decay of $\mathbf{u}(x)$

First we explain the need to introduce the two different vertex sets
$\mathcal{W}\subset\mathcal{V}$. In the definition of $\lambda(x)$ and
$\mathbf{u}(x)$, all vertices in $\mathcal{V}\setminus\\{x\\}$ are removed,
while the profile vectors $\mathbf{u}(x)$ are only considered for $x$ in the
smaller set $\mathcal{W}$. The difference between $\mathcal{W}$ and
$\mathcal{V}$ is used precisely to obtain a spectral gap for
$H^{(\mathcal{V}\setminus\\{x\\})}$ around $\lambda(x)$, $x\in\mathcal{W}$.

To show exponential decay of $\mathbf{u}(x)$, we use its definition, a simple
computation, and a truncated Neumann series expansion to obtain

$\displaystyle\mathbf{u}(x)|_{\mathcal{V}^{c}}$
$\displaystyle=c_{x}\bigg{(}1-\frac{H^{(\mathcal{V})}}{\lambda(x)}\bigg{)}^{-1}\mathbf{1}_{S_{1}(x)}$
(2.7)
$\displaystyle=c_{x}\sum_{k=0}^{n-1}\bigg{(}\frac{H^{(\mathcal{V})}}{\lambda(x)}\bigg{)}^{k}\mathbf{1}_{S_{1}(x)}+c_{x}\bigg{(}1-\frac{H^{(\mathcal{V})}}{\lambda(x)}\bigg{)}^{-1}\bigg{(}\frac{H^{(\mathcal{V})}}{\lambda(x)}\bigg{)}^{n}\mathbf{1}_{S_{1}(x)}\,,$

where
$c_{x}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\frac{\langle\mathbf{1}_{x}\mspace{2.0mu},\mathbf{u}(x)\rangle}{\lambda(x)\sqrt{d}}$.
Each term of the sum is supported in $B_{n}(x)$ and, thus, vanishes when
restricting to $B_{n}(x)^{c}$. Hence, as
$\lvert\langle\mathbf{1}_{x}\mspace{2.0mu},\mathbf{u}(x)\rangle\rvert\lesssim
1$, $\lVert\mathbf{1}_{S_{1}(x)}\rVert=\sqrt{d\alpha_{x}}$, and
$\lVert(\lambda(x)-H^{(\mathcal{V})})^{-1}\rVert\lesssim 1$ by the spectral
gap of $H^{(\mathcal{V}\setminus\\{x\\})}$ around
$\lambda(x)=\lambda_{2}(H^{(\mathcal{V}\setminus\\{x\\})})$ mentioned above,
we obtain $\|\mathbf{u}(x)|_{B_{n}(x)^{c}}\|\lesssim\sqrt{\alpha_{x}}\,q^{n}$
with $q=\lambda(x)^{-1}\|H^{(\mathcal{V})}|_{B_{n+1}(x)}\|<1$. This is the
desired exponential decay. We remark that in (2.7) we establish exponential
decay of the Green function of $H^{(\mathcal{V})}$ evaluated at $\lambda(x)$,
using that $\lambda(x)$ is away from the spectrum of $H^{(\mathcal{V})}$. This
is an instance of a Combes-Thomas estimate, and we translate it to an
exponential decay for the eigenvector $\mathbf{u}(x)$. Furthermore, we show
that $\lambda(x)$ is isolated in the spectrum of
$H^{(\mathcal{V}\setminus\\{x\\})}$ and, thus, perturbation theory implies
that $\mathbf{u}(x)=\mathbf{w}_{r}(x)+o(1)$.

The rate obtained from the above argument is far from optimal, but an
extension of this argument does yield the optimal rate of decay for
$\lVert\mathbf{u}(x)|_{B_{i}(x)^{c}}\rVert$ for small enough $\mu$. To that
end, we choose $n=Ci$ for a large constant $C>0$ in (2.7), which makes the
remainder term in (2.7) with $n=Ci$ subleading. It remains to estimate the
terms $(H^{(\mathcal{V})})^{k}{\mathbf{1}_{S_{1}(x)}}$ for $k=i$, …, $Ci$,
since they vanish for $k<i$ when restricted to $B_{i}(x)^{c}$. For $k\geqslant
i$, we relate $(H^{(\mathcal{V})})^{k}{\mathbf{1}_{S_{1}(x)}}$ to the number
of a family of walks on the graph $\mathbb{G}$. We obtain optimal bounds on
this number by a path counting argument, exploiting the tree structure of
$\mathbb{G}|_{B_{r}(x)}$, a precise bound on the degrees in
$B_{r}(x)\setminus\\{x\\}$ and the concentration of the sphere sizes $\lvert
S_{i}(x)\rvert$ for $i\leqslant r$.

#### 2.3.2. Approximate eigenvalues

We now sketch how (ii) is proved. In contrast to the case of local profile
vectors discussed above, the proof of $\lVert
E\rVert\lesssim\max_{x\in\mathcal{W}}\lVert(H-\lambda(x))\mathbf{u}(x)\rVert$
requires also a control of the nonzero overlaps
$\langle\mathbf{u}(x)\mspace{2.0mu},H\mathbf{u}(y)\rangle$ for $x\neq y$. By
exponential decay of $\mathbf{u}(x)$, it is easy to see that these overlaps
are $N^{-o(1)}$, but, as explained above, a polynomial bound $N^{-c}$ is
required to prove localization. The construction of $\mathbf{u}(x)$ and
$\lambda(x)$ and a simple computation reveal that

$(H-\lambda(x))\mathbf{u}(x)=\sum_{y\in{\mathcal{V}}\setminus\\{x\\}}\varepsilon_{y}(x)\mathbf{1}_{y},\qquad\qquad\varepsilon_{y}(x)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\frac{1}{\sqrt{d}}\sum_{t\in
S_{1}(y)}\langle\mathbf{1}_{t},\mathbf{u}(x)\rangle\,.$ (2.8)

Then the main idea to estimate $\varepsilon_{y}(x)$ is the following
elementary bound. Let $\mathcal{T}$ be a finite set. For any
$(u_{t})_{t\in\mathcal{T}}\in\mathbb{C}^{\mathcal{T}}$ and any random
$T\subset\mathcal{T}$ we have

$\mathbb{E}\Biggl{[}\sum_{t\in T}\lvert
u_{t}\rvert^{2}\Biggr{]}=\sum_{t\in\mathcal{T}}\mathbb{E}[\mathbbm{1}_{t\in
T}]\lvert u_{t}\rvert^{2}\leqslant\max_{t\in\mathcal{T}}\mathbb{P}(t\in
T)\sum_{t\in\mathcal{T}}\lvert u_{t}\rvert^{2}\,.$ (2.9)

Heuristically, by the independence of the edges in the Erdős-Rényi graph, the
edges between $\mathcal{V}\setminus\\{x\\}$ and
$(\mathcal{V}\setminus\\{x\\})^{c}$ are sampled independently of the subgraphs
$\mathbb{G}|_{({\mathcal{V}}\setminus\\{x\\})^{c}}$ and
$\mathbb{G}|_{\mathcal{V}\setminus\\{x\\}}$ and are, therefore, independent of
$\mathbf{u}(x)$. Hence, (2.8), (2.9) and $\lvert S_{1}(y)\rvert\lesssim\log N$
yield

$\mathbb{E}\big{[}|\varepsilon_{y}(x)|^{2}\big{|}A^{(y)}\big{]}\leqslant\frac{1}{d}\,\mathbb{E}\bigg{[}|S_{1}(y)|\sum_{t\in
S_{1}(y)}\langle\mathbf{1}_{t},\mathbf{u}(x)\rangle^{2}\bigg{|}A^{(y)}\bigg{]}\lesssim\frac{(\log
N)^{2}}{Nd}\|\mathbf{u}(x)\|^{2}=N^{-1+o(1)}\,.$

From $|{\mathcal{V}}|=N^{\mu+o(1)}$ and Chebyshev’s inequality, we therefore
conclude $\|(H-\lambda(x))\mathbf{u}(x)\|^{2}\leqslant N^{2\mu-1+o(1)}$ with
high probability.

Since $(\mathbf{u}(x))_{x\in\mathcal{W}}$ is not an orthogonal family, we
choose the first columns of $U$ in (2.5) as the Gram-Schmidt
orthonormalization $(\mathbf{u}^{\perp}(x))_{x\in\mathcal{W}}$ of
$(\mathbf{u}(x))_{x\in\mathcal{W}}$ (with respect to a fixed order on
$\mathcal{W}$), i.e.

$\mathbf{u}^{\perp}(x)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\frac{\mathbf{u}(x)-\Pi_{<x}\mathbf{u}(x)}{\lVert\mathbf{u}(x)-\Pi_{<x}\mathbf{u}(x)\rVert}\,,$
(2.10)

where $\Pi_{<x}$ denotes the orthogonal projection onto
$\operatorname{span}\\{\mathbf{u}(y)\colon y\in\mathcal{W},\,y<x\\}$. It
remains to show that, for any $x\in\mathcal{W}$,
$\lVert(H-\lambda(x))\mathbf{u}^{\perp}(x)\rVert$ is also bounded by an
inverse power of $N$. The denominator in (2.10) is $\gtrsim 1$ since
$\langle\mathbf{1}_{x}\mspace{2.0mu},\mathbf{u}(x)\rangle\gtrsim 1$ and
$\langle\mathbf{1}_{y}\mspace{2.0mu},\mathbf{u}(x)\rangle=0$ for all $y\neq
x$. Moreover, $H-\lambda(x)$ applied to the numerator of (2.10) is bounded by
a negative power of $N$, since
$\lVert(H-\lambda(x))\mathbf{u}(x)\rVert\leqslant N^{\mu-1/2+o(1)}$ as shown
above, and $\lVert\overline{\Pi}\\!\,_{<x}H{\Pi}_{<x}\rVert\leqslant
N^{\mu-1/2+o(1)}$ where
$\overline{\Pi}\\!\,_{<x}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=1-\Pi_{<x}$.
The latter bound is proved using the above estimate on
$\lVert(H-\lambda(x))\mathbf{u}(x)\rVert$. Given this construction and the
bounds explained above, we extend $(\mathbf{u}^{\perp}(x))_{x\in\mathcal{W}}$
to an orthonormal basis and choose these vectors as columns of $U$. In
particular, the first $n=\lvert\mathcal{W}\rvert$ columns of $U$ are given by
$(\mathbf{u}^{\perp}(x))_{x\in\mathcal{W}}$.

What remains is to show that $\operatorname{spec}(X)$ is separated from $I$.
To that end, we decompose its domain of definition into the span of
$\mathbf{w}_{1}$, the eigenvector of $H$ associated with its largest
eigenvalue, and its orthogonal complement. This largest eigenvalue and the
overlaps between $\mathbf{w}_{1}$ and $\mathbf{u}^{\perp}(x)$ for all
$x\in\mathcal{W}$ can be controlled relatively precisely, and we omit
$\mathbf{w}_{1}$ from the remaining explanations below. It suffices to show
that $\lambda_{1}(X)\leqslant\Lambda(\alpha^{*})+o(1)$, by the definitions of
$\mathcal{V}$ and $\mathcal{W}$. This upper bound on $\lambda_{1}(X)$ is
equivalent to

$\lambda_{1}(\overline{\Pi}\\!\,_{\mathcal{W}}H\overline{\Pi}\\!\,_{\mathcal{W}})\leqslant\Lambda(\alpha^{*})+o(1)\,,$
(2.11)

where
$\overline{\Pi}\\!\,_{\mathcal{W}}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=1-\Pi_{\mathcal{W}}$
and $\Pi_{\mathcal{W}}$ is the orthogonal projection onto
$\operatorname{span}\\{\mathbf{u}^{\perp}(x)\colon x\in\mathcal{W}\\}$. An
estimate of the form (2.11) was first derived in ADK20 , except that there the
projection was defined in terms local profile vectors. Since we are using the
global profile vectors $\mathbf{u}^{\perp}(x)$, in our case this estimate is
considerably more involved. The rough strategy is to make a link between
(2.11) and a corresponding estimate for local profile vectors, which was
already established in ADK20 using bounds on the non-backtracking matrix of
$H$, an Ihara-Bass type identity, and a local delocalization result for
approximate eigenvectors.

To that end, let $Q$ be the orthogonal projection onto the complement of
$\bigcup_{y\in\mathcal{V}\setminus\mathcal{W}}B_{2r_{\star}-1}(y)$, where
$r_{\star}\asymp\sqrt{\log N}$ is chosen as in (ADK20, , eq. (1.8)). In
particular, the local profile vectors $\mathbf{v}(x)$ from ADK20 satisfy
$\operatorname{supp}\mathbf{v}(x)\subset B_{r_{\star}}(x)$ for every
$x\in\mathcal{V}$. We denote by $\Pi_{Q}$ the projection onto
$\operatorname{span}\\{Q\mathbf{u}^{\perp}(x)\colon x\in\mathcal{W}\\}$. If we
obtain a small enough upper bound on $\lVert\Pi_{\mathcal{W}}-\Pi_{Q}\rVert$
then it suffices to show
$\lambda_{1}(\overline{\Pi}\\!\,_{Q}H\overline{\Pi}\\!\,_{Q})\leqslant\Lambda(\alpha^{*})+o(1)$,
where
$\overline{\Pi}\\!\,_{Q}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=1-\Pi_{Q}$.
To get a sufficient estimate for $\lVert\Pi_{\mathcal{W}}-\Pi_{Q}\rVert$, we
need that $\mathbf{u}^{\perp}(x)|_{B_{r}(y)}$ is polynomially small in $N$ for
$x\neq y$ as a summation over $x,y\in\mathcal{W}$ is required. This is
achieved through an argument motivated by (2.9). Let $\Pi_{\mathbf{v}}$ be the
orthogonal projection onto $\operatorname{span}\\{\mathbf{v}(x)\colon
x\in\mathcal{V}\setminus\mathcal{W}\\}$. By definition of $Q$ and
$\operatorname{supp}\mathbf{v}(x)\subset B_{r_{\star}}(x)$, $\Pi_{Q}$ and
$\Pi_{\mathbf{v}}$ commute. Thus,
$\lambda_{1}(\overline{\Pi}\\!\,_{Q}H\overline{\Pi}\\!\,_{Q})\leqslant\max\\{\lambda_{1}(\Pi_{\mathbf{v}}H\Pi_{\mathbf{v}}),\lambda_{1}(\overline{\Pi}\\!\,_{Q}\overline{\Pi}\\!\,_{\mathbf{v}}H\overline{\Pi}\\!\,_{\mathbf{v}}\overline{\Pi}\\!\,_{Q})\\}+o(1)$,
where
$\overline{\Pi}\\!\,_{\mathbf{v}}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=1-\Pi_{\mathbf{v}}$.
By ADK20 ,
$\lambda_{1}(\Pi_{\mathbf{v}}H\Pi_{\mathbf{v}})\leqslant\Lambda(\alpha^{*})+o(1)$.
For eigenvectors of $H$ which are orthogonal to the local profile vectors
$\mathbf{v}(x)$ and whose associated eigenvalues are large enough, we obtain a
weak delocalization estimate by following an argument in ADK20 . This weak
delocalization estimate shows that
$\lambda_{1}(\overline{\Pi}\\!\,_{Q}\overline{\Pi}\\!\,_{\mathbf{v}}H\overline{\Pi}\\!\,_{\mathbf{v}}\overline{\Pi}\\!\,_{Q})\leqslant\Lambda(\alpha^{*})+o(1)$
if
$\lambda_{1}(\overline{\Pi}\\!\,_{\mathcal{W}}H^{(\mathcal{V}\setminus\mathcal{W})}\overline{\Pi}\\!\,_{\mathcal{W}})\leqslant\Lambda(\alpha^{*})+o(1)$.
The last bound is finally obtained by a careful analysis of the spectrum of
$H^{(\mathcal{V}\setminus\mathcal{W})}$, which is based on viewing it as a
perturbation of
${\Pi}_{\mathcal{W}}H^{(\mathcal{V}\setminus\mathcal{W})}{\Pi}_{\mathcal{W}}+\overline{\Pi}\\!\,_{\mathcal{W}}H^{(\mathcal{V}\setminus\mathcal{W})}\overline{\Pi}\\!\,_{\mathcal{W}}$
and analysing $H^{(\mathcal{V}\setminus\mathcal{W})}$ on
$\operatorname{ran}\Pi_{\mathcal{W}}$ in detail.

#### 2.3.3. Eigenvalue spacing

We now sketch how to prove (iii). To that end, we fix $a\neq b\in\mathcal{W}$.
To prove that $\lambda(a)$ and $\lambda(b)$ are not too close to each other,
we choose an appropriate radius $r$ on the scale $\frac{\log N}{\log d}$ of
the diameter of $\mathbb{G}$. Then we fix the two subgraphs
$\mathbb{G}|_{B_{r}(b)}$ and $\mathbb{G}|_{B_{r}(b)^{c}}$ and show that
resampling the edges between $S_{r}(b)$ and $B_{r}(b)^{c}$ results in a
substantial change of $\lambda(b)$ while $\lambda(a)$ remains almost
unchanged: we establish simultaneous _anticoncentration_ for $\lambda(b)$ and
_concentration_ for $\lambda(b)$, which yields anticoncentration for their
difference. The edges between $S_{r}(b)$ and $B_{r}(b)^{c}$ form an
independent family of Bernoulli random variables by definition of the Erdős-
Rényi graph.

On a more formal level, we work conditionally on
$\mathcal{F}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\sigma(B_{r}(b),A|_{B_{r}(b)},A|_{B_{r}(b)^{c}})$
and prove the following two statements in order to obtain a lower bound on
$|\lambda(a)-\lambda(b)|$.

  1. (a)

$\lambda(a)$ fluctuates little under resampling of the edges between
$S_{r}(b)$ and $B_{r}(b)^{c}$, i.e. the _concentration_ estimate

$\mathbb{P}(|\lambda(a)-z|\ll N^{-\eta}|\mathcal{F})\geqslant
1-N^{-\eta/2+o(1)}$

holds if $z$ is the second largest eigenvalue of $H^{(\mathcal{V}\cup
B_{r}(b)\setminus\\{a\\})}$, which is $\mathcal{F}$–measurable.

  2. (b)

$\lambda(b)$ fluctuates a lot under resampling of the edges between $S_{r}(b)$
and $B_{r}(b)^{c}$, i.e. the _anticoncentration_ estimate

$\mathbb{P}(|\lambda(b)-z|\geqslant N^{-\eta}|\mathcal{F})\geqslant
1-N^{-\eta/2+o(1)}$

holds for any $\mathcal{F}$–measurable spectral parameter $z$ in $I$ (see the
definition of $I$ after (2.6b)).

We justify (a) by replacing $\mathbf{u}(a)$ with an $\mathcal{F}$–measurable
version. This allows for a use of (2.9) in a similar fashion as in the first
part of Section 2.3.2 and reveals that, conditionally on $\mathcal{F}$,
$\lambda(a)$ is concentrated around the second largest eigenvalue of
$H^{(\mathcal{V}\cup B_{r}(b)\setminus\\{a\\})}$ since $\lvert B_{r}(b)\rvert$
is not too large due to our choice of $r$.

The proof of (b) is much more elaborate. We start by noting that $\lambda(b)$
is characterized by the equation

$\lambda(b)+\frac{1}{d}\sum_{x,y\in
S_{1}(b)}(H^{(\mathcal{V})}-\lambda(b))^{-1}_{xy}=0\,,$ (2.12)

as follows from Schur’s complement formula. The main strategy is to derive a
recursive family of equations for the Green function, starting from (2.12) and
extending to increasingly large spheres around $b$, to which Kesten’s self-
improving anticoncentration result can be applied. To quantify
anticoncentration, we use _Lévy’s concentration function_

$Q(X,L)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\sup_{t\in\mathbb{R}}\mathbb{P}(X\in[t-L,t+L])\,,$
(2.13)

where $X$ is a random variable and $L>0$ is deterministic.

######  Proposition 2.8 (Theorem 2 of Kesten1969 ).

There exists a universal constant $K$ such that for any independent random
variables $X_{1},\ldots,X_{n}$ satisfying $Q(X_{i},L)\leqslant 1/2$ we have

$Q\bigg{(}\sum_{i\in[n]}X_{i},L\bigg{)}\leqslant\frac{K}{\sqrt{n}}\max_{i\in[n]}Q(X_{i},L)\,.$
(2.14)

This result is an improvement due to Kesten Kesten1969 of a classical
anticoncentration result of Doeblin, Lévy, Kolmogorov, and Rogozin. Kesten’s
insight was that such an estimate can be made self-improving, as manifested by
the factor $\max_{i\in[n]}Q(X_{i},L)$ on the right-hand side. This factor is
crucial for our argument, as it allows us to successively improve the upper
bound on $Q$.

We now explain more precisely how the expression of $\lambda(b)$ in terms of a
large number of Green function entries is obtained. We shall tacitly use that
$\mathbb{G}|_{B_{r}(b)}$ is a tree, which can be easily shown to be true with
high probability. Applying Schur’s complement formula at $x\in S_{i}(b)$,
using standard resolvent identities, and arguing similarly as in (2.9) to
control errors yields

$\frac{1}{G_{xx}(i-1,z)}=-z-\frac{1}{d}\sum_{y\in
S_{1}^{+}(x)}G_{yy}(i,z)+o(1)\,,$ (2.15)

where
$G_{xx}(i,z)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=(H^{(B_{i}(b)\cup\mathcal{V})}-z)_{xx}^{-1}$
and $S_{1}^{+}(x)=S_{1}(x)\cap S_{i+1}(b)$ is the set of children of $x$ in
the tree $\mathbb{G}|_{B_{r}(x)}$ rooted at $b$. The error $o(1)$ is
polynomially small in $N$; it comprises error terms arising from removing
vertices from $H$ and neglecting all off-diagonal Green function entries.

Setting the error term in (2.15) to zero, we obtain a recursive equation for
the idealized Green function entries $(g_{x}(z))_{x\in
B_{r}(b)\setminus\\{b\\}}$, given by

$\frac{1}{g_{x}(z)}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\begin{cases}-z-\frac{1}{d}\sum_{y\in
S_{1}^{+}(x)}G_{yy}(r,z)&\text{ if }x\in S_{r}(b)\\\ -z-\frac{1}{d}\sum_{y\in
S_{1}^{+}(x)}g_{y}(z)&\text{ if }x\in
B_{r-1}(b)\setminus\\{b\\}\,,\end{cases}$ (2.16)

which is an approximate version of the recursion (2.15) for the actual Green
function entries. The recursion begins at the boundary of the ball $B_{r}(b)$
and propagates inwards. We note that, for any $1\leqslant i\leqslant r$,
conditioned on $\mathcal{F}$, the family $(g_{x}(z))_{x\in S_{i}(b)}$ is
independent if $\mathbb{G}|_{B_{r}(b)}$ is a tree and $z$ is
$\mathcal{F}$–measurable. From (2.15), (2.16) and $r\asymp\frac{\log N}{\log
d}$, it is not hard to conclude by induction that, for large enough $\eta>0$,
with high probability,
$g_{x}(z)=G_{xx}(0,z)+o(N^{-\eta})=(H^{(\mathcal{V})}-z)^{-1}_{xx}+o(N^{-\eta})$
for all $x\in S_{1}(b)$. Hence, if we can prove that
$Q(g_{x}(z),N^{-\eta})\leqslant N^{-c}$ for all $x\in S_{1}(b)$ and some
constant $c>0$, then a union bound over $a\neq b\in\mathcal{W}$,
$\lvert\mathcal{W}\rvert\asymp N^{\mu}$, the smallness of the off-diagonal
entries of $(H^{(\mathcal{V})}-\lambda(b))^{-1}$ as argued after (2.15), and
(2.12) imply anticoncentration for $\lambda(b)-z$. This is (b), which together
with (a) implies that $\min_{a\neq
b\in\mathcal{W}}\lvert\lambda(a)-\lambda(b)\rvert\geqslant N^{-\eta}$ with
high probability, i.e. (iii).

Therefore, to complete the sketch of (iii), what remains is to prove
$Q(g_{x}(z),N^{-\eta})\leqslant N^{-c}$ for all $x\in S_{1}(b)$, whose proof
we sketch now. Throughout the entire argument we condition on $\mathcal{F}$
and use that $\mathbb{G}|_{B_{r}(x)}$ is a tree. To begin the recursion, we
first show that $Q(g_{x},d^{-1})\leqslant 1/2$ for any $x\in S_{r}(b)$. This
follows from the first case of (2.16), using a weak lower bound on the entries
$G_{yy}(r,z)$ and anticoncentration from the fact that the size of
$S_{1}^{+}(x)$ is a binomial random variable conditioned on $\mathcal{F}$.

Next, let $x\in S_{i}(b)$ for $1\leqslant i\leqslant r-1$. By using the second
case in (2.16) and Proposition 2.8, we iteratively refine the resolution, i.e.
decrease the second argument of $Q$, and decrease the upper bound on $Q$,
which are $d^{-1}$ and $1/2$, respectively, at the starting point. Indeed,
conditioning on $A|_{B_{i}(b)}$, the second case in (2.16) and rescaling the
second argument of $Q$ yield

$\displaystyle Q\big{(}g_{x}(z),(T^{2}d)^{-r+i}\big{)}$
$\displaystyle\leqslant Q\bigg{(}\sum_{y\in
S_{1}^{+}(x)}g_{y}(z),(T^{2}d)^{-r+i+1}\bigg{)}$
$\displaystyle\leqslant\frac{K}{\sqrt{\lvert S_{1}^{+}(x)\rvert}}\max_{y\in
S_{1}^{+}(x)}Q\big{(}g_{y}(z),(T^{2}d)^{-r+i+1}\big{)}\,,$ (2.17)

where we applied Proposition 2.8 using the independence of $(g_{y}(z))_{y\in
S_{1}^{+}(x)}$ in the second step. Here, we also used that $Q(f(X),L)\leqslant
Q(X,T^{-2}L)$ if
$f(t)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\frac{1}{t}$ and
$X\in[T^{-1},T]$ since the derivative of $f$ is bounded from below by $T^{-2}$
on this interval, and that, with high probability, $g$ lies in $[T^{-1},T]$
for $T\asymp\sqrt{\frac{\log N}{d}}$.

The estimate (2.17) yields the desired self-improvement provided that $\lvert
S_{1}^{+}(x)\rvert$ is large enough. However, $\lvert S_{1}^{+}(x)\rvert$ is
not large enough for all vertices $x$ in $B_{r}(b)$ (and in fact consistently
applying (2.17) at all vertices yields an anticoncentration bound at the root
$b$ that is far from optimal and too weak to conclude localization).
Sometimes, a better bound than (2.17) can be obtained by replacing Kesten’s
estimate (2.14) with the trivial estimate

$Q\bigg{(}\sum_{i\in[n]}X_{i},L\bigg{)}\leqslant\min_{i\in[n]}Q(X_{i},L)\,,$
(2.18)

which follows immediately from the independence of the random variables
$X_{i}$. Although this estimate lacks the factor $K/\sqrt{n}$ from (2.14), it
replaces the maximum with a minimum. Thus, an important ingredient in our
recursive self-improving anticoncentration argument is an algorithm that
determines which of (2.14) or (2.18) is to be used at any given vertex $x\in
B_{r}(b)$. It relies on the notion of _robust vertices_.

Recursively, a vertex $x\in B_{r}(b)$ is called _robust_ if $x\in S_{r}(b)$ or
$S_{1}^{+}(x)$ contains at least $d/2$ robust vertices. We denote the set of
robust vertices by $\mathcal{R}$. An important auxiliary result is that the
root $b$ is robust with high probability, which in particular implies that
$S_{i}(b)\cap\mathcal{R}$ is large for any $i\leqslant r$. Therefore, we can
restrict to $x\in S_{i}(b)\cap\mathcal{R}$ and proceed similarly as in (2.17)
to obtain

$Q(g_{x}(z),(T^{2}d)^{-r+i})\leqslant Q\bigg{(}\sum_{y\in
S_{1}^{+}(x)\cap\mathcal{R}}g_{y}(z),(T^{2}d)^{-r+i+1}\bigg{)}\leqslant\frac{K\sqrt{2}}{\sqrt{d}}\max_{y\in
S_{1}^{+}(x)\cap\mathcal{R}}Q\big{(}g_{y}(z),(T^{2}d)^{-r+i+1}\big{)}\,,$

where in the first step we used (2.18). Thus, we obtain
$Q(g_{x}(z),(T^{2}d)^{-r})\leqslant(K\sqrt{2d^{-1}})^{r-1}$ for all $x\in
S_{1}(b)$ and, therefore, by choosing $r$ such that $(T^{2}d)^{r+1}=N^{\eta}$,
we arrive at $Q(g_{x}(z),N^{-\eta})\leqslant N^{-\eta/2+o(1)}$ for all $x\in
S_{1}(b)$. This is the desired anticoncentration bound, (b), which, as
explained above, implies (iii).

#### 2.3.4. The three main exponents of $N$

Throughout this paper we use the three exponents $\mu$, $\zeta$, $\eta>0$ to
control three central quantities of the argument. We summarize their roles
here for easy reference.

  * •

$N^{\mu}$ is the typical size of the vertex sets $\mathcal{V}$ and
$\mathcal{W}$ (cf. Proposition 3.2 (i)), as the parameter $\mu$ is introduced
to control $\alpha^{*}$ (see (1.6)). Consequently, $N^{\mu}$ is also the
typical number of eigenvalues of $H$ satisfying (1.7). Therefore, the factor
$N^{\mu}$ emerges from union bounds when a property is required for all
$x\in\mathcal{V}$ or $x\in\mathcal{W}$.

  * •

$N^{-\zeta}$ is the upper bound on the eigenvalue approximation that we
establish in Proposition 2.3, i.e. on the distance between $\lambda(x)$ and
the eigenvalues of $H$ or, more precisely, the upper bound on
$\lVert(H-\lambda(x))\mathbf{u}(x)\rVert$. Proposition 2.3 requires the
condition $\zeta<1/2-3\mu/2$.

  * •

$N^{-\eta}$ is the lower bound on the eigenvalue spacing, or correspondingly
$\min_{x\neq y\in\mathcal{W}}\lvert\lambda(x)-\lambda(y)\rvert$, that we prove
in Proposition 2.4. Since the typical eigenvalue spacing is $N^{-\mu}$ in the
interval we consider, we clearly need $\mu<\eta$. In fact, our proof of
Proposition 2.4 requires the stronger condition $8\mu<\eta$ for technical
reasons as well as $\mu<1/24$.

To apply perturbation theory in the proof of Theorem 1.1, we need that the
error in the eigenvalue approximation $N^{-\zeta}$ be smaller than the
eigenvalue spacing $N^{-\eta}$. This means that $\eta<\zeta$.

### 2.4. Localization profile – proof of Theorem 1.6

Theorem 1.6 is an immediate consequence of the following result.

######  Proposition 2.9 (Local approximation for $\mathbf{u}(x)$).

Let $\mu\in[0,1/3)$. Then, with high probability, the following holds for all
$x\in\mathcal{W}$. If $r\in\mathbb{N}$ satisfies

$\log d\ll r\leqslant\min\bigg{\\{}\frac{1}{6}\frac{\log N}{\log
d},\min\bigg{\\{}\frac{1}{5}-\frac{\mu}{4},\frac{1}{3}-\mu\bigg{\\}}\frac{\log
N}{\log d}-2\bigg{\\}}\,,$ (2.19)

then

  1. (i)

$\mathbf{u}(x)=\mathbf{v}_{r}(x)+o(1)$,

  2. (ii)

$\mathbf{u}(x)=\mathbf{w}_{r}(x)+o(1)$.

Part (i) is proved in Section 3.2 below. Part (ii) follows from Corollary 4.2
below, since $\Lambda(\alpha_{x})\geqslant 2$.

###### Proof of Theorem 1.6.

From (2.3) in the proof of Theorem 1.1, we know that
$\mathbf{w}=\mathbf{u}(x)+O(N^{-\varepsilon})$ for a unique $x\in\mathcal{W}$
and some small enough $\varepsilon>0$. Therefore, Theorem 1.6 follows from
Proposition 2.9. ∎

### 2.5. Mobility edge – proof of Theorem 1.7

Part (i) follows from Theorem 1.1, since
$\inf\\{\alpha>0\mathrel{\vbox{\hbox{.}\hbox{.}}}\mathbb{P}(\alpha_{1}\geqslant\alpha)\leqslant
N^{-23/24}\\}\leqslant 2$ if $d\geqslant\frac{23}{24}b_{*}\log N$, by Lemma
E.1 below. Part (ii) was proved in (ADK_delocalized, , Theorem 1.1 (ii)).

### 2.6. Localization length – proof of Theorem 1.8

For any eigenvector $\mathbf{w}$ we introduce the function

$q(u)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\sum_{y}\mathrm{d}(u,y)\langle\mathbf{1}_{y}\mspace{2.0mu},\mathbf{w}\rangle^{2}\,,$

so that $\ell(\mathbf{w})=\min_{u}q(u)$.

For the localized phase, suppose that $\lambda$ is an eigenvalue satisfying
$\lvert\lambda\rvert\geqslant 2+\kappa$ with associated eigenvector
$\mathbf{w}$. Denote by $x$ the unique vertex associated with $\mathbf{w}$
from Theorems 1.1 and 1.6. Then the following estimates hold on the
intersection of the high-probability events of these two theorems. By Theorem
1.1, there exists a constant $R\equiv R_{\kappa}$ such that

$q(u)\geqslant\mathrm{d}(u,x)\langle\mathbf{1}_{x}\mspace{2.0mu},\mathbf{w}\rangle^{2}\geqslant
R\frac{\alpha_{x}-2}{2(\alpha_{x}-1)}+o(1)\geqslant\frac{\alpha_{x}}{\alpha_{x}-2}\qquad\text{for
all }u\in B_{R}(x)^{c}\,,$ (2.20)

where the third inequality holds for large enough constant $R$. Moreover, for
any $\varepsilon>0$ there exists a constant $R^{\prime}\in\mathbb{N}$ such
that for $u\in B_{R}(x)$ we have

$\displaystyle q(u)$ $\displaystyle=\sum_{y\in
B_{R^{\prime}}(x)}\mathrm{d}(u,y)\langle\mathbf{1}_{y}\mspace{2.0mu},\mathbf{w}\rangle^{2}+\sum_{y\in
B_{R^{\prime}}(x)^{c}}\mathrm{d}(u,y)\langle\mathbf{1}_{y}\mspace{2.0mu},\mathbf{w}\rangle^{2}$
$\displaystyle=\sum_{y\in
B_{R^{\prime}}(x)}\mathrm{d}(u,y)\langle\mathbf{1}_{y}\mspace{2.0mu},\mathbf{w}\rangle^{2}+O(\varepsilon)$
$\displaystyle=\sum_{y\in
B_{R^{\prime}}(x)}\mathrm{d}(u,y)\langle\mathbf{1}_{y}\mspace{2.0mu},\mathbf{v}_{r}(x)\rangle^{2}+O(\varepsilon)+o(1)\,,$
(2.21)

where the second step follows from the estimate $\mathrm{d}(u,y)\leqslant
R+\mathrm{d}(x,y)$ and the exponential decay from Theorem 1.1, and the third
step from Theorem 1.6 with some $\log d\ll r\ll\frac{\log N}{\log d}$.

To analyse the sum, we abbreviate
$k\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\mathrm{d}(x,u)$ and
introduce the set
$T_{i}(u,x)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=S_{i}(x)\cap
S_{i+k}(u)$ for $0\leqslant i\leqslant r$, which is the set of vertices in
$S_{i}(x)$ whose geodesic to $x$ does not pass through $u$. By Proposition 3.2
(ii) below, the graph $\mathbb{G}|_{B_{r}(x)}$ is a tree, which implies

$\mathrm{d}(u,y)=\begin{cases}k+i&\text{if }y\in T_{i}(u,x)\\\ \lvert
k-i\rvert&\text{if }y\in S_{i}(x)\setminus T_{i}(u,x)\,.\end{cases}$ (2.22)

Next, we estimate $\lvert S_{i}(x)\setminus T_{i}(u,x)\rvert$. For $1\leqslant
i\leqslant k$, the set $S_{i}(x)\setminus T_{i}(u,x)$ consists of the unique
vertex on the geodesic from $x$ to $u$ at distance $i$ from $x$. For $i>k$, we
have $S_{i}(x)\setminus T_{i}(u,x)=S_{i}(x)\cap S_{i-k}(u)$. Here we used the
tree structure of $\mathbb{G}|_{B_{r}(x)}$. Hence, we conclude that for $i>k$
we have $\lvert S_{i}(x)\setminus T_{i}(u,x)\rvert\leqslant\lvert
S_{i-k}(u)\rvert\lesssim(\log N)d^{i-k-1}$, by Proposition 3.1.

Next, by (ADK20, , Lemma 5.4), with high probability we have $\lvert
S_{i}(x)\rvert=\lvert S_{1}(x)\rvert d^{i-1}(1+o(1))$ for $1\leqslant
i\leqslant r$. Since $\lvert S_{1}(x)\rvert\geqslant\alpha^{*}d\geqslant 2d$,
we conclude that $\lvert S_{i}(x)\rvert\geqslant d^{i}$ for $i\leqslant r$.
Putting all of these estimates together, we conclude for all $1\leqslant
i\leqslant r$ that

$\frac{\lvert S_{i}(x)\setminus T_{i}(u,x)\rvert}{\lvert
S_{i}(x)\rvert}\lesssim\begin{cases}d^{-i}&\text{if }1\leqslant i\leqslant
k\\\ (\log N)d^{-k-1}&\text{if }k<i\leqslant r\,.\end{cases}$

Since $T_{i}(u,x)=S_{i}(x)$ for $k=0$ or $i=0$, using the condition (1.5) we
conclude that

$\frac{\lvert S_{i}(x)\setminus T_{i}(u,x)\rvert}{\lvert S_{i}(x)\rvert}=o(1)$
(2.23)

for all $u\in B_{R}(x)$ and $0\leqslant i\leqslant r$.

Next, using (2.22) and recalling the definition (1.11), we write the above sum
as

$\displaystyle\sum_{y\in
B_{R^{\prime}}(x)}\mathrm{d}(u,y)\langle\mathbf{1}_{y}\mspace{2.0mu},\mathbf{v}_{r}(x)\rangle^{2}$
$\displaystyle=\sum_{i=0}^{R^{\prime}}\Biggl{(}\sum_{y\in
T_{i}(u,x)}(k+i)\langle\mathbf{1}_{y}\mspace{2.0mu},\mathbf{v}_{r}(x)\rangle^{2}+\sum_{y\in
S_{i}(x)\setminus T_{i}(u,x)}\lvert
k-i\rvert\langle\mathbf{1}_{y}\mspace{2.0mu},\mathbf{v}_{r}(x)\rangle^{2}\Biggr{)}$
$\displaystyle=\sum_{i=0}^{R^{\prime}}\biggl{(}(k+i)\,u_{i}(\alpha_{x})^{2}\frac{\lvert
T_{i}(u,x)\rvert}{\lvert S_{i}(x)\rvert}+\lvert
k-i\rvert\,u_{i}(\alpha_{x})^{2}\frac{\lvert S_{i}(x)\setminus
T_{i}(u,x)\rvert}{\lvert S_{i}(x)\rvert}\biggr{)}$
$\displaystyle=\sum_{i=0}^{R^{\prime}}(k+i)u_{i}(\alpha_{x})^{2}+o(1)\,,$

where in the last step we used (2.23), the fact that $R^{\prime}$ is constant,
and $\sum_{i=0}^{r-1}u_{i}(\alpha_{x})^{2}=1$. The latter sum is clearly
minimized for $k=0$. Recalling (2.21), we therefore conclude that for any
$u\in B_{R}(x)$ we have

$q(u)\geqslant q(x)+O(\varepsilon)+o(1)\,,\qquad
q(x)=\sum_{i=1}^{\infty}iu_{i}(\alpha_{x})^{2}+O(\varepsilon)+o(1)$

for large enough $R^{\prime}$ depending on $\varepsilon$. Since
$\varepsilon>0$ was arbitrary, and recalling (2.20), by taking the minimum
over $u\in[N]$, it therefore suffices to show that

$\sum_{i=1}^{\infty}iu_{i}(\alpha_{x})^{2}=\frac{\alpha_{x}}{2(\alpha_{x}-2)}+o(1)=\frac{\lvert\lambda\rvert}{2\sqrt{\lambda^{2}-4}}+o(1)\,.$
(2.24)

The first equality of (2.24) is an elementary computation using the definition
(1.10), recalling the normalization $\sum_{i=0}^{r-1}u_{i}(\alpha)^{2}=1$ and
that $r\gg 1$. The second equality of (2.24) follows from the estimate
$\lvert\lambda\rvert=\Lambda(\alpha_{x})+o(1)$ by Remark 1.2, which can be
inverted to obtain
$\frac{1}{\alpha_{x}}=\frac{1}{2}\bigl{(}1-\frac{\sqrt{\lambda^{2}-4}}{\lvert\lambda\rvert}\bigr{)}+o(1)$.

For the delocalized phase, suppose that $\lambda$ is an eigenvalue satisfying
$\lvert\lambda\rvert\leqslant 2-\kappa$ with associated eigenvector
$\mathbf{w}$. We use (ADK_delocalized, , Theorem 1.1 (ii)) to deduce that with
probability $1-O(N^{-10})$ we have
$\lVert\mathbf{w}\rVert_{\infty}^{2}\leqslant N^{-1+o(1)}$. Hence, with
probability $1-O(N^{-9})$ we have, for any $x\in[N]$ and $r\geqslant 0$,

$q(x)\geqslant\sum_{y\in
B_{r}(x)}\mathrm{d}(x,y)\,\langle\mathbf{1}_{y}\mspace{2.0mu},\mathbf{w}\rangle^{2}+r\sum_{y\in
B_{r}(x)^{c}}\langle\mathbf{1}_{y}\mspace{2.0mu},\mathbf{w}\rangle^{2}\\\
\geqslant r\biggl{(}1-\sum_{y\in
B_{r}(x)}\langle\mathbf{1}_{y}\mspace{2.0mu},\mathbf{w}\rangle^{2}\biggr{)}\geqslant
r\biggl{(}1-N^{-1+o(1)}\lvert B_{r}(x)\rvert\biggr{)}\,.$

Next, we deduce from (ChungLu_diameter, , Lemma 1) that for any constant
$\varepsilon>0$ there is a constant $\delta>0$ such that, with high
probability, if $r\leqslant(1-\varepsilon)\frac{\log N}{\log d}$ then $\lvert
B_{r}(x)\rvert\leqslant N^{1-\delta}$ for all $x\in[N]$. Choosing
$r\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\lfloor(1-\varepsilon)\frac{\log
N}{\log d}\rfloor$, we conclude that, for any $\varepsilon>0$, with high
probability, for all eigenvectors $\mathbf{w}$ with eigenvalue $\lambda$
satisfying $\lvert\lambda\rvert\leqslant 2-\kappa$, we have
$\ell(\mathbf{w})\geqslant(1-\varepsilon+o(1))\frac{\log N}{\log d}$. Since
$\varepsilon>0$ was an arbitrary constant, we conclude the stronger lower
bound $\ell(\mathbf{w})\geqslant(1-o(1))\frac{\log N}{\log
d}=\operatorname{diam}(\mathbb{G})(1+o(1))$, where the last step follows from
ChungLu_diameter . The complementary upper bound
$\ell(\mathbf{w})\leqslant\operatorname{diam}(\mathbb{G})$ follows by
definition of $\operatorname{diam}(\mathbb{G})$, since
$\mathrm{d}(x,y)\leqslant\operatorname{diam}(\mathbb{G})$ for all $x,y\in[N]$
(here we used that under our assumption on $d$, the graph $\mathbb{G}$ is with
high probability connected). This concludes the proof.

## 3\. Preliminaries

The rest of this paper is devoted to the proofs of Propositions 2.2, 2.3 and
2.4. We begin with a short section that collects some basic properties of the
graph $\mathbb{G}$ and its spectrum.

### 3.1. Properties of the graph

In this subsection, we collect some basic local properties of the Erdős-Rényi
graph $\mathbb{G}$ around vertices in $\mathcal{V}$.

######  Proposition 3.1.

Suppose that $\sqrt{\log N}\ll d\leqslant 3\log N$. With high probability, the
following holds.

  1. (i)

$\max_{x\in[N]}|S_{1}(x)|\leqslant 10\log N$.

  2. (ii)

$|B_{i}(x)|\lesssim\max\\{\lvert S_{1}(x)\rvert,d\\}d^{i-1}$ for all $x\in[N]$
and all $i\in\mathbb{N}$ with $i\leqslant\frac{1}{3}\frac{\log N}{\log d}$.

Item (i) is a simple application of Bennett’s inequality and (ii) follows from
ADK19 ; ADK20 ; a detailed proof is given in Section A below. In particular,
by the assumption $d\gg\sqrt{\log N}$, we get from Proposition 3.1 (i) that

$\Lambda(\alpha_{x})\lesssim\sqrt{\alpha_{x}}\lesssim\sqrt{\frac{\log
N}{d}}\ll\sqrt{d}$ (3.1)

for all $x\in[N]$ on the high-probability event from Proposition 3.1.

######  Proposition 3.2.

Let $\mu\in[0,1/3)$ be a constant. Suppose that $\sqrt{\log N}\ll d\leqslant
3\log N$. With high probability, for any $r\in\mathbb{N}$ satisfying

$1\leqslant
r\leqslant\min\bigg{\\{}\frac{1}{5}-\frac{\mu}{4},\frac{1}{3}-\mu\bigg{\\}}\frac{\log
N}{\log d}\,,$ (3.2)

the following holds.

  1. (i)

$|\mathcal{V}|\leqslant N^{\mu+o(1)}$.

  2. (ii)

$\mathbb{G}|_{B_{r}(x)}$ is a tree for all $x\in\mathcal{V}$.

  3. (iii)

$B_{r}(x)\cap B_{r}(y)=\emptyset$ for all $x,y\in{\mathcal{V}}$ satisfying
$x\neq y$.

  4. (iv)

Let $\nu\in[0,1]$. If $1-\mu-\nu-r\frac{\log d}{\log N}\gtrsim 1$ then $\lvert
S_{1}(y)\rvert\leqslant\alpha^{*}(\nu)d$ for all
$y\in\bigcup_{x\in\mathcal{V}}(B_{r}(x)\setminus\\{x\\})$.

These statements are all consequences of ADK19 ; ADK21 ; we explain the
details of the proof of Proposition 3.2 in Section A below.

### 3.2. Properties of the spectrum

In this subsection we collect basic spectral properties of $H$ and some of its
submatrices.

######  Definition 3.3.

Let $\mathbf{w}_{1}$ be a normalized eigenvector of $H$ with nonnegative
entries associated with the largest eigenvalue $\lambda_{1}(H)$ of $H$.

Note that, with high probability, $\mathbf{w}_{1}$ is unique and coincides
with the Perron-Frobenius eigenvector of the giant component of $\mathbb{G}$.

######  Proposition 3.4.

Suppose (1.5). With high probability the following holds.

  1. (i)

For any $\mu\in[0,1]$ we have
$\max\\{\lambda_{2}(H^{(\mathcal{V})}),-\lambda_{N}(H^{(\mathcal{V})})\\}\leqslant\Lambda(\alpha^{*})+o(1)$.

  2. (ii)

Fix $\mu\in[0,1/3)$. If $X\subset\bigcup_{x\in\mathcal{V}}B_{r}(x)$ with
$r\in\mathbb{N}$ as in (3.2), then $\lambda_{1}(H^{(X)})$ and the
corresponding eigenvector $\mathbf{w}$ of $H^{(X)}$ satisfy

$\lambda_{1}(H^{(X)})=\sqrt{d}(1+o(1)),\qquad\qquad\biggl{\lVert}\mathbf{w}-\frac{\mathbf{1}_{X^{c}}}{\lvert
X^{c}\rvert^{1/2}}\biggr{\rVert}=o(1)\,.$

  3. (iii)

Fix $\mu\in[0,1)$. If $x\in\mathcal{V}$, $r\in\mathbb{N}$ satisfies $\log d\ll
r\leqslant\frac{1}{6}\frac{\log N}{\log d}$ and $X\subset[N]$ satisfies $X\cap
B_{r}(x)=\emptyset$, then

$\lVert(H^{(X)}-\Lambda(\alpha_{x}))\mathbf{v}_{r}(x)\rVert=o(1)\,,$

where $\mathbf{v}_{r}(x)$ was defined in (1.11).

  4. (iv)

Fix $\mu\in[0,4/5)$. For any $r\in\mathbb{N}$ satisfying
$r\ll\frac{d}{\log\log N}$, there is a normalized vector $\mathbf{q}$ with
$\operatorname{supp}\mathbf{q}\subset\big{(}\bigcup_{x\in\mathcal{V}}B_{r+1}(x)\big{)}^{c}$
such that

$\lVert(H-\sqrt{d})\mathbf{q}\rVert\lesssim
d^{-1/2},\qquad\qquad\lVert\mathbf{w}_{1}-\mathbf{q}\rVert\lesssim
d^{-1},\qquad\qquad\lVert\mathbf{q}-N^{-1/2}\mathbf{1}_{[N]}\rVert\lesssim
d^{-1/2}\,.$

These results follow essentially from ADK19 ; ADK20 ; ADK21 ; the detailed
proof is presented in Section D below.

######  Definition 3.5.

We denote by $\Omega$ the intersection of the high-probability events of
Propositions 3.1, 3.2 and 3.4.

In particular, on $\Omega$ the estimate (3.1) holds.

######  Corollary 3.6.

Fix $\mu\in[0,1/3)$. On $\Omega$, the following holds for all
$x\in\mathcal{W}$ and all $X\subset[N]$. If $X\cap B_{r}(x)=\emptyset$ and
$\mathcal{V}\setminus\\{x\\}\subset X\subset\bigcup_{y\in\mathcal{V}}B_{r}(y)$
for some $r\in\mathbb{N}$ satisfying $\log d\ll
r\leqslant\min\big{\\{}\frac{1}{6},\frac{1}{5}-\frac{\mu}{4},\frac{1}{3}-\mu\big{\\}}\frac{\log
N}{\log d}$ then

$\lambda_{1}(H^{(X)})=\sqrt{d}(1+o(1)),\qquad\qquad\lambda_{2}(H^{(X)})=\Lambda(\alpha_{x})+o(1),\qquad\qquad\lambda_{3}(H^{(X)})\leqslant\Lambda(\alpha^{*})+o(1)\,.$

Corollary 3.6 with $X=\mathcal{V}\setminus\\{x\\}$ directly implies that, on
$\Omega$,

$\lambda(x)=\lambda_{2}(H^{(\mathcal{V}\setminus\\{x\\})})=\Lambda(\alpha_{x})+o(1)\,.$
(3.3)

###### Proof of Corollary 3.6.

The statement about $\lambda_{1}(H^{(X)})$ is identical to Proposition 3.4
(ii). By eigenvalue interlacing, we have

$\lambda_{3}(H^{(X)})\leqslant\lambda_{3}(H^{({\mathcal{V}}\setminus\\{x\\})})\leqslant\lambda_{2}(H^{({\mathcal{V}})})\leqslant\Lambda(\alpha^{*})+o(1)\,,$

where for the last inequality we used Proposition 3.4 (i). Finally,
Proposition 3.4 (iii) implies that there exists an eigenvalue of $H^{(X)}$ at
distance $o(1)$ from $\Lambda(\alpha_{x})$. Because of the estimates on
$\lambda_{1}(H^{(X)})$ and $\lambda_{3}(H^{(X)})$ just proven, and because
$\Lambda(\alpha_{x})\geqslant\Lambda(\alpha^{*})+\kappa/2$ for
$x\in\mathcal{W}$ (recall (2.2)) as well as $\Lambda(\alpha_{x})\ll\sqrt{d}$
by (3.1), this eigenvalue has to be $\lambda_{2}(H^{(X)})$. ∎

###### Proof of Proposition 2.9 (i).

We show that the conclusion of Proposition 2.9 (i) holds on $\Omega$. The
proof uses a spectral gap of $H^{(\mathcal{V}\setminus\\{x\\})}$ around
$\lambda(x)=\lambda_{2}(H^{(\mathcal{V}\setminus\\{x\\})})$, that
$\mathbf{v}_{r}(x)$ is an approximate eigenvector of
$H^{(\mathcal{V}\setminus\\{x\\})}$ by Proposition 3.4 (iii), and perturbation
theory. Indeed, from Corollary 3.6 with $X=\mathcal{V}\setminus\\{x\\}$,
recalling the definition of $\mathcal{W}$ (see (2.2)), we obtain that
$\lambda_{2}(H^{(\mathcal{V}\setminus\\{x\\})})$ is separated from the other
eigenvalues of $H^{(\mathcal{V}\setminus\\{x\\})}$ by a positive constant.
Owing to (3.3), Proposition 3.4 (iii) with $X=\mathcal{V}\setminus\\{x\\}$ and
Lemma E.2 below imply $\lVert\mathbf{u}(x)-\mathbf{v}_{r}(x)\rVert=o(1)$, i.e.
Proposition 2.9 (i). ∎

We conclude the following corollary from Proposition 2.9 (i) and its proof.

######  Corollary 3.7.

Fix $\mu\in[0,1/3)$. On $\Omega$ we have
$\langle\mathbf{1}_{x}\mspace{2.0mu},\mathbf{u}(x)\rangle=\sqrt{\frac{\alpha_{x}-2}{2(\alpha_{x}-1)}}+o(1)\gtrsim
1$ for all $x\in\mathcal{W}$.

###### Proof.

We first note that for any $r\to\infty$ as $N\to\infty$, we have
$u_{0}(\alpha_{x})=\sqrt{\frac{\alpha_{x}-2}{2(\alpha_{x}-1)}}+o(1)$ by
(1.10). By Proposition 2.9 (i) and its proof,
$\langle\mathbf{1}_{x}\mspace{2.0mu},\mathbf{u}(x)\rangle=\langle\mathbf{1}_{x}\mspace{2.0mu},\mathbf{v}_{r}(x)\rangle+o(1)=u_{0}(\alpha_{x})+o(1)\gtrsim
1$ on $\Omega$, where in second step we used the definition (1.11), and in the
last step we used that $\alpha_{x}\geqslant 2+\kappa$, so that the sequence
$(u_{i}(\alpha_{x}))_{i}$ from (1.10) is exponentially decaying in $i$,
uniformly in $r$. ∎

### 3.3. Properties of the Green function

In this subsection, we fix $\mu\in[0,1/3)$. Define

$\mathcal{J}=[\Lambda(\alpha^{*})+\kappa/4,\sqrt{d}/2]\,.$

We shall use that whenever $z\in\mathcal{J}$, all Green functions appearing in
our proof are bounded, which is the content of the following result.

######  Lemma 3.8.

Suppose (1.5) and (3.2). On $\Omega$, for $z,z^{\prime}\in\mathcal{J}$ and
$X\subset[N]$ satisfying $\mathcal{V}\subset
X\subset\bigcup_{x\in\mathcal{V}}B_{r}(x)$, we have

$\displaystyle\lVert(H^{(X)}-z)^{-1}\rVert$
$\displaystyle\leqslant{8}/\kappa\,,$ (3.4)
$\displaystyle\lVert(H^{(X)}-z)^{-1}-(H^{(X)}-z’)^{-1}\rVert$
$\displaystyle\leqslant(8/\kappa)^{2}\,|z-z’|\,.$ (3.5)

###### Proof of Lemma 3.8.

Since $H^{(X)}$ is a minor of $H^{(\mathcal{V})}$ up to the addition of a zero
block, eigenvalue interlacing and Proposition 3.4 (i) and (ii) imply

$\lambda_{2}(H^{(X)})\leqslant\lambda_{2}(H^{(\mathcal{V})})\leqslant\Lambda(\alpha^{*})+\kappa/8\qquad\text{and}\qquad\lambda_{1}(H^{(X)})=\sqrt{d}(1+o(1))\geqslant\sqrt{d}/2+\kappa/8\,.$

Therefore, $\text{dist}(z,\text{Spec}(H^{(X)}))\geqslant\kappa/8$ for any
$z\in\mathcal{J}$, which proves (3.4). The Lipschitz bound (3.5) follows from
(3.4) and the resolvent identity. ∎

######  Lemma 3.9.

Suppose (1.5) and (3.2). On $\Omega$, for any $\mathcal{V}\subset
X\subset\bigcup_{x\in\mathcal{V}}B_{r}(x)$, $z\in\mathcal{J}$, and $y\notin
X$, we have

$-(H^{(X)}-z)^{-1}_{yy}\geqslant(3z)^{-1}\,.$

###### Proof of Lemma 3.9.

Denoting by $\lambda_{1}\geqslant\lambda_{2}\geqslant\dots$ and
$\mathbf{w}_{1},\mathbf{w}_{2},\dots$ the eigenvalues and eigenvectors of
$H^{(X)}$, respectively, we have

$-(H^{(X)}-z)^{-1}_{yy}=\frac{\langle\mathbf{1}_{y}\mspace{2.0mu},\mathbf{w}_{1}\rangle^{2}}{z-\lambda_{1}}+\sum_{2\leqslant
i\leqslant
N}\frac{\langle\mathbf{1}_{y}\mspace{2.0mu},\mathbf{w}_{i}\rangle^{2}}{z-\lambda_{i}}\geqslant\frac{1}{z-\lambda_{N}}(1-\langle\mathbf{1}_{y}\mspace{2.0mu},\mathbf{w}_{1}\rangle^{2})-\mathopen{}\mathclose{{}\left|\frac{\langle\mathbf{1}_{y}\mspace{2.0mu},\mathbf{w}_{1}\rangle^{2}}{\lambda_{1}-z}}\right|\,,$
(3.6)

where in the second step we used $z-\lambda_{N}\geqslant z-\lambda_{i}>0$ for
all $i\geqslant 2$, which follows from eigenvalue interlacing, Proposition 3.4
(i), and the condition $z\in\mathcal{J}$.

To estimate the right-hand side of (3.6), we use Proposition 3.2 (i) and
Proposition 3.1 (ii) as well as (3.2) to estimate $\lvert
X\rvert\leqslant\sum_{x\in\mathcal{V}}\lvert B_{r}(x)\rvert\leqslant
N^{1/3+o(1)}$ on $\Omega$. From Proposition 3.4 (ii) we therefore deduce that

$\langle\mathbf{1}_{y}\mspace{2.0mu},\mathbf{w}_{1}\rangle^{2}=\lvert
X^{c}\rvert^{-1/2}+o(1)=o(1)\,.$ (3.7)

We conclude that the first term on the right-hand side of (3.6) is bounded
from below by $((2+o(1))z)^{-1}$, as $z-\lambda_{N}\leqslant 2z$ from
Proposition 3.4 (i). The second term on the right-hand side of (3.6) is
estimated using (3.7) as well as
$\lvert\lambda_{1}-z\rvert\gtrsim\sqrt{d}\geqslant z$ by Proposition 3.4 (ii)
and $z\in\mathcal{J}$. ∎

## 4\. Exponential decay of $\mathbf{u}(x)$ and proof of Proposition 2.2

In this section we establish the exponential decay of $\mathbf{u}(x)$ around
the vertex $x$. In particular, Proposition 2.2 is a direct consequence of
Proposition 4.1 below. Moreover, we prove in Corollary 4.2 below that
$\mathbf{u}(x)$ is well approximated by $\mathbf{w}_{r}(x)$, the eigenvector
of $H|_{B_{r}(x)}$ corresponding to its largest eigenvalue. This implies
Proposition 2.9 (ii).

Throughout this section we use the high-probability event $\Omega$ from
Definition 3.5.

### 4.1. Simple exponential decay of $\mathbf{u}(x)$

In this subsection we establish exponential decay at some positive but not
optimal rate.

######  Proposition 4.1.

Suppose that (1.5) holds. Then there is a constant $c\in(0,1)$ such that, for
each fixed $\mu\in[0,1/3)$, on $\Omega$, for all $x\in\mathcal{W}$,

$\lVert\mathbf{u}(x)|_{B_{i}(x)^{c}}\rVert\lesssim\sqrt{\alpha_{x}}\,q_{x}^{i}\,,\qquad\qquad
q_{x}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\frac{\Lambda(\alpha^{*}(1/2))+o(1)}{\lambda(x)}\leqslant
1-c\,,$ (4.1)

for all $i\in\mathbb{N}$ satisfying $1\leqslant
i\leqslant\min\big{\\{}\frac{1}{5}-\frac{\mu}{4},\frac{1}{3}-\mu\big{\\}}\frac{\log
N}{\log d}-2$.

###### Proof.

We note that
$\operatorname{supp}\mathbf{u}(x)\subset([N]\setminus\mathcal{V})\cup\\{x\\}$
and decompose
$\mathbf{u}(x)=\langle\mathbf{1}_{x}\mspace{2.0mu},\mathbf{u}(x)\rangle\mathbf{1}_{x}+Q\mathbf{u}(x)$,
where
$Q\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\sum_{y\in[N]\setminus\mathcal{V}}\langle\mathbf{1}_{y}\mspace{2.0mu},\,\cdot\,\rangle\mathbf{1}_{y}$
is the orthogonal projection on the coordinates in $[N]\setminus\mathcal{V}$.
We apply the projection $Q$ to the eigenvalue–eigenvector relation

$\lambda(x)\mathbf{u}(x)=H^{(\mathcal{V}\setminus\\{x\\})}\mathbf{u}(x)=\langle\mathbf{1}_{x}\mspace{2.0mu},\mathbf{u}(x)\rangle\mathbf{1}_{S_{1}(x)}/\sqrt{d}+H^{(\mathcal{V}\setminus\\{x\\})}Q\mathbf{u}(x)\,,$

solve for $Q\mathbf{u}(x)$, and obtain

$Q\mathbf{u}(x)=\frac{\langle\mathbf{1}_{x}\mspace{2.0mu},\mathbf{u}(x)\rangle}{\sqrt{d}}\big{(}\lambda(x)-H^{(\mathcal{V})}\big{)}^{-1}\mathbf{1}_{S_{1}(x)}\,,$
(4.2)

where we used that
$H^{(\mathcal{V}\setminus\\{x\\})}\mathbf{1}_{x}=\mathbf{1}_{S_{1}(x)}/\sqrt{d}$
and $QH^{(\mathcal{V}\setminus\\{x\\})}Q=H^{(\mathcal{V})}$. We also used that
$\lambda(x)-H^{(\mathcal{V})}$ is invertible, which can be seen as follows.
From Proposition 3.4 (ii) with $X=\mathcal{V}$ and $r=0$, we conclude
$\lambda_{1}(H^{(\mathcal{V})})=\sqrt{d}(1+o(1))$ and, hence, (3.3) and
Proposition 3.4 (i) yield that $\lambda(x)$ is not an eigenvalue of
$H^{(\mathcal{V})}$ and

$\operatorname{dist}(\lambda(x),\operatorname{spec}H^{(\mathcal{V})})\gtrsim
1\,.$ (4.3)

Let

$Q_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\sum_{y\in[N]\setminus(\mathcal{V}\cup
B_{i}(x))}\langle\mathbf{1}_{y}\mspace{2.0mu},\,\cdot\,\rangle\mathbf{1}_{y}$

the projection onto the coordinates in $[N]\setminus(\mathcal{V}\cup
B_{i}(x))$. As
$\operatorname{supp}\mathbf{u}(x)\subset([N]\setminus\mathcal{V})\cup\\{x\\}$
and $Q_{i}Q=Q_{i}$, we conclude from (4.2) that

$\mathbf{u}(x)|_{B_{i}(x)^{c}}=Q_{i}\mathbf{u}(x)=Q_{i}Q\mathbf{u}(x)=\frac{\langle\mathbf{1}_{x}\mspace{2.0mu},\mathbf{u}(x)\rangle}{\lambda(x)\sqrt{d}}Q_{i}\bigg{(}1-\frac{H^{(\mathcal{V})}}{\lambda(x)}\bigg{)}^{-1}\mathbf{1}_{S_{1}(x)}\,.$
(4.4)

For any $n\in\mathbb{N}$ we have

$\bigg{(}1-\frac{H^{(\mathcal{V})}}{\lambda(x)}\bigg{)}^{-1}=\sum_{k=0}^{n}\bigg{(}\frac{H^{(\mathcal{V})}}{\lambda(x)}\bigg{)}^{k}+\bigg{(}1-\frac{H^{(\mathcal{V})}}{\lambda(x)}\bigg{)}^{-1}\bigg{(}\frac{H^{(\mathcal{V})}}{\lambda(x)}\bigg{)}^{n+1}\,.$
(4.5)

Since $H^{(\mathcal{V})}$ is a local operator, we conclude that
$Q_{i}(H^{(\mathcal{V})})^{k}\mathbf{1}_{S_{1}(x)}=0$ if $k+1\leqslant i$.
Hence, fixing $i\geqslant 1$ and applying (4.5) with $n=i-1$ to (4.4), we get

$\mathbf{u}(x)|_{B_{i}(x)^{c}}=\frac{\langle\mathbf{1}_{x}\mspace{2.0mu},\mathbf{u}(x)\rangle}{\sqrt{d}}Q_{i}\big{(}\lambda(x)-H^{(\mathcal{V})}\big{)}^{-1}\bigg{(}\frac{H^{(\mathcal{V})}}{\lambda(x)}\bigg{)}^{i}\mathbf{1}_{S_{1}(x)}=O\bigg{(}\frac{\lVert(H^{(\mathcal{V})})^{i}\mathbf{1}_{S_{1}(x)}\rVert}{\sqrt{d}\lambda(x)^{i}}\bigg{)}\,.$
(4.6)

Here, in the last step, we employed
$\lvert\langle\mathbf{1}_{x}\mspace{2.0mu},\mathbf{u}(x)\rangle\rvert\leqslant
1$, $\lVert Q_{i}\rVert\leqslant 1$,
$\lVert(\lambda(x)-H^{(\mathcal{V})})^{-1}\rVert\lesssim 1$ by (4.3).

Let $r\in\mathbb{N}$ be the largest integer satisfying (3.2). We now claim
that, on $\Omega$,

$\lVert
H^{(\mathcal{V})}\mathbf{v}\rVert\leqslant(\Lambda(\alpha^{*}(1/2))+o(1))\lVert\mathbf{v}\rVert$
(4.7)

for any $\mathbf{v}$ such that $\operatorname{supp}\mathbf{v}\subset
B_{r}(x)$. Before proving (4.7), we use it conclude the proof of (4.1).

For $i\leqslant r-2$ we have
$\operatorname{supp}(H^{(\mathcal{V})})^{i}\mathbf{1}_{S_{1}(x)}\subset
B_{r}(x)$, so that iterative applications of (4.7) yield

$\lVert(H^{(\mathcal{V})})^{i}\mathbf{1}_{S_{1}(x)}\rVert\lesssim(\Lambda(\alpha^{*}(1/2))+o(1))^{i}\sqrt{\alpha_{x}}\sqrt{d}\,.$
(4.8)

Hence, the first bound in (4.1) follows from (4.6). We now show the second
bound in (4.1). If $\frac{\log N}{d}\geqslant T$ for a sufficiently large
constant $T$ then $q_{x}\leqslant 1-c$ for some constant $c>0$ by using
Corollary B.3 with $\nu=1/2$, $\lambda(x)\geqslant\Lambda(\alpha^{*}(\mu))$,
$\mu\leqslant 1/3$ and possibly increasing its $T$. If $\frac{\log
N}{d}<T\lesssim 1$ then $\alpha_{x}\lesssim 1$ by Proposition 3.1 (i) and the
estimate $q_{x}\leqslant 1-c$ for some constant $c>0$ follows from
$\Lambda(\alpha_{x})\leqslant 2\sqrt{\alpha_{x}}\lesssim 1$ and
$\lambda(x)=\Lambda(\alpha_{x})+o(1)\geqslant\Lambda(\alpha^{*})+\kappa/4\geqslant\Lambda(\alpha^{*}(1/2))+\kappa/4$,
which is a consequence of (3.3) and the definition of $\mathcal{W}$. This
completes the proof of the second bound in (4.1).

What remains is the proof of (4.7). For any $\mathbf{v}\in\mathbb{R}^{[N]}$,
the Cauchy-Schwarz inequality implies
$\lVert(\mathbb{E}H)^{(\mathcal{V})}\mathbf{v}\rVert\leqslant\sqrt{\frac{d\lvert\operatorname{supp}\mathbf{v}\rvert}{N}}\lVert\mathbf{v}\rVert$.
By Proposition 3.1 (ii) and (3.2), if $\operatorname{supp}\mathbf{v}\subset
B_{r}(x)$ then $\lvert\operatorname{supp}\mathbf{v}\rvert\leqslant
N^{1/5+o(1)}$. Therefore,

$\lVert
H^{(\mathcal{V})}\mathbf{v}\rVert\leqslant\lVert(H-\mathbb{E}H)^{(\mathcal{V})}\mathbf{v}\rVert+o(\lVert\mathbf{v}\rVert)\\\
\leqslant\lVert(H-\mathbb{E}H)^{(\\{y\,:\,\alpha_{y}\geqslant\alpha^{*}(1/2)\\})}\mathbf{v}\rVert+o(\lVert\mathbf{v}\rVert)\leqslant(\Lambda(\alpha^{*}(1/2))+o(1))\lVert\mathbf{v}\rVert\,,$

where in the second step, we used $\mathcal{V}^{c}\cap
B_{r}(x)\subset\\{y\mathrel{\vbox{\hbox{.}\hbox{.}}}\alpha_{y}\geqslant\alpha^{*}(1/2)\\}^{c}$
by Proposition 3.2 (iv) and, in the third step,
$\lVert(H-\mathbb{E}H)^{(\\{y\,:\,\alpha_{y}\geqslant\alpha^{*}(1/2)\\})}\rVert\leqslant\Lambda(\alpha^{*}(1/2))+o(1)$
by Lemma D.1888Note that Lemma D.1 holds on $\Omega$, since Lemma D.1 is used
to prove Proposition 3.4 (i).. This concludes the proof of (4.7). ∎

### 4.2. Approximating $\mathbf{u}(x)$ by $\mathbf{w}_{r}(x)$

From Proposition 4.1 and its proof, we deduce the following result, which
compares $\mathbf{u}(x)$ and $\mathbf{w}_{r}(x)$ from Definition 1.5.

######  Corollary 4.2.

Suppose that (1.5) holds and fix $\mu\in[0,1/3)$. Then, on $\Omega$, for all
$x\in\mathcal{W}$ and $r\in\mathbb{N}$ satisfying (2.19),

$\mathbf{u}(x)=\mathbf{w}_{r}(x)+O\big{(}\alpha_{x}q_{x}^{r}\Lambda(\alpha_{x})^{-1}\big{)}=\mathbf{w}_{r}(x)+o\big{(}\Lambda(\alpha_{x})^{-1}\big{)}\,,$

where $q_{x}$ is the same as in Proposition 4.1.

###### Proof.

We shall apply Lemma E.2 with $M=H|_{B_{r}(x)}$,
$\widehat{\lambda}=\lambda(x)$ and $\mathbf{v}=\mathbf{u}(x)$. First, we check
its conditions by studying the spectral gap of $H|_{B_{r}(x)}$ around its
largest eigenvalue. As $r\leqslant\frac{1}{6}\frac{\log N}{\log d}$, we
conclude from Proposition 3.4 (iii) with $X=B_{r}(x)^{c}$ that
$H|_{B_{r}(x)}=H^{(B_{r}(x)^{c})}$ has an eigenvalue
$\Lambda(\alpha_{x})+o(1)$. The bound (4.7) implies that $\lVert
H|_{B_{r}(x)\setminus\\{x\\}}\rVert\leqslant\lVert
H^{(\mathcal{V})}\rVert\leqslant\Lambda(\alpha^{*}(1/2))+o(1)$, where in the
first step we used Proposition 3.2 (iii). Note that $H|_{B_{r}(x)}$ and
$H|_{B_{r}(x)\setminus\\{x\\}}$ differ by a rank-two matrix, with one positive
and one negative eigenvalue. By eigenvalue interlacing, we therefore deduce
that

$\lambda_{1}(H|_{B_{r}(x)})=\Lambda(\alpha_{x})+o(1),\qquad\qquad\lambda_{2}(H|_{B_{r}(x)})\leqslant\Lambda(\alpha^{*}(1/2))+o(1)\,.$

Thus, the definition of $\mathcal{W}$ in (2.2) implies

$\lambda_{1}(H|_{B_{r}(x)})-\lambda_{2}(H|_{B_{r}(x)})\gtrsim\Lambda(\alpha_{x})\big{(}1-\frac{\Lambda(\alpha^{*}(1/2))}{\Lambda(\alpha^{*}(\mu))+\kappa/2}\big{)}\gtrsim\Lambda(\alpha_{x})\,,$

where the last inequality follows from Corollary B.3 if $\frac{\log
N}{d}\geqslant T$ for some large enough constant $T$, and from
$\Lambda(\alpha^{*}(1/2))+\kappa/2\leqslant\Lambda(\alpha^{*}(\mu))+\kappa/2\leqslant\Lambda(\alpha_{x})\lesssim
1$ (see (3.1)) otherwise. Hence, owing to (3.3), there is
$\Delta\gtrsim\Lambda(\alpha_{x})$ such that $H|_{B_{r}(x)}$ has precisely one
eigenvalue in $[\lambda(x)-\Delta,\lambda(x)+\Delta]$.

Let $P_{r}$ be the orthogonal projection onto the coordinates in $B_{r}(x)$.
The eigenvalue-eigenvector relation
$(H^{(\mathcal{V}\setminus\\{x\\})}-\lambda(x))\mathbf{u}(x)=0$ and
$P_{r}H^{(\mathcal{V}\setminus\\{x\\})}P_{r}=H|_{B_{r}(x)}$ imply

$(H|_{B_{r}(x)}-\lambda(x))\mathbf{u}(x)=-P_{r}H^{(\mathcal{V}\setminus\\{x\\})}(1-P_{r})\mathbf{u}(x)-\lambda(x)(1-P_{r})\mathbf{u}(x)\,.$

Therefore, since $(1-P_{r})\mathbf{u}(x)=\mathbf{u}(x)|_{B_{r}(x)^{c}}$, we
get

$\lVert(H|_{B_{r}(x)}-\lambda(x))\mathbf{u}(x)\rVert\leqslant\lambda(x)\lVert\mathbf{u}(x)|_{B_{r}(x)^{c}}\rVert+\lVert
P_{r}H^{(\mathcal{V}\setminus\\{x\\})}(\mathbf{u}(x)|_{B_{r}(x)^{c}})\rVert\lesssim\alpha_{x}q_{x}^{r}\,.$
(4.9)

In the last step, we used $\lambda(x)\lesssim\alpha_{x}^{1/2}$ and Proposition
4.1 to estimate the first term. For the second term, we used that
$P_{r}H^{(\mathcal{V}\setminus\\{x\\})}(\mathbf{u}(x)|_{B_{r}(x)^{c}})=P_{r}H^{(\mathcal{V}\setminus\\{x\\})}(\mathbf{u}(x)|_{S_{r+1}(x)})$
by the locality of $H^{(\mathcal{V}\setminus\\{x\\})}$ as well as the identity
$H^{(\mathcal{V}\setminus\\{x\\})}(\mathbf{u}(x)|_{S_{r+1}(x)})=H^{(\mathcal{V})}(\mathbf{u}(x)|_{S_{r+1}(x)})$,
which yield

$\lVert
H^{(\mathcal{V}\setminus\\{x\\})}(\mathbf{u}(x)|_{S_{r+1}(x)})\rVert\lesssim\Lambda(\alpha^{*}(1/2))\lVert\mathbf{u}(x)|_{S_{r+1}(x)}\rVert\lesssim\alpha_{x}^{1/2}\lVert\mathbf{u}(x)|_{B_{r}(x)^{c}}\rVert\lesssim\alpha_{x}q_{x}^{r}$

due to (4.7) as
$r+1\leqslant\min\big{\\{}\frac{1}{5}-\frac{\mu}{4},\frac{1}{3}-\mu\big{\\}}\frac{\log
N}{\log d}$,
$\Lambda(\alpha^{*}(1/2))^{2}\leqslant\Lambda(\alpha^{*})^{2}\lesssim\alpha_{x}$,
and Proposition 4.1.

Since $\alpha_{x}\lesssim\frac{\log N}{d}$ by Proposition 3.1 (i),
$q_{x}\leqslant 1-c$ for some constant $c>0$ by Proposition 4.1, $r\gg\log
d\gtrsim\log\big{(}\frac{10\log N}{d}\big{)}$ by (1.5) and
$\alpha_{x}\geqslant 2$, we obtain

$\alpha_{x}q_{x}^{r}\ll 1\lesssim\alpha_{x}^{1/2}\,.$ (4.10)

Therefore, owing to (4.9) and
$\alpha_{x}^{1/2}\asymp\Lambda(\alpha_{x})\lesssim\Delta$, we can now apply
Lemma E.2 with $M=H|_{B_{r}(x)}$, $\widehat{\lambda}=\lambda(x)$ and
$\mathbf{v}=\mathbf{u}(x)$ to conclude
$\mathbf{u}(x)=\mathbf{w}_{r}(x)+O(\alpha_{x}q_{x}^{r}\Lambda(\alpha_{x})^{-1})$
from (4.9) and $\Delta\gtrsim\Lambda(\alpha_{x})$ as well as
$\langle\mathbf{1}_{x}\mspace{2.0mu},\mathbf{u}(x)\rangle\geqslant 0$ and
$\langle\mathbf{1}_{x}\mspace{2.0mu},\mathbf{w}_{r}(x)\rangle\geqslant 0$.
This proves the first equality in Corollary 4.2.

Since $\alpha_{x}q_{x}^{r}\ll 1$ by (4.10), the last equality in Corollary 4.2
follows immediately. ∎

### 4.3. Optimal exponential decay of $\mathbf{u}(x)$

In this subsection we establish an explicit rate of exponential decay of
$\mathbf{u}(x)$. It holds only for a smaller set of eigenvectors near the
spectral edge, requiring $\mu$ to be small enough. As pointed out in Remark
1.4, up to the error $O(\varepsilon)$, this rate is optimal.

######  Proposition 4.3.

Suppose (1.5). Then the following holds.

  1. (i)

(Subcritical regime) There are constants $T\geqslant 1$ and $c>0$ such that if
$\frac{\log N}{d}\geqslant T$ then, on $\Omega$, for any small enough constant
$\varepsilon>0$ and each $\mu\in[0,\varepsilon]$,

$\lVert\mathbf{u}(x)|_{B_{i}(x)^{c}}\rVert\lesssim\sqrt{\alpha_{x}}\bigg{(}\frac{1+O(\varepsilon)}{\sqrt{\alpha_{x}-1}}\bigg{)}^{i+1}$

for all $x\in\mathcal{W}$ and $i\leqslant c\frac{\log N}{(\log
d)\log\frac{10\log N}{d}}$.

  2. (ii)

(Critical regime) There is a constant $c>0$ such that, for any constants
$T\geqslant 1$ and $\varepsilon>0$ with $\varepsilon\leqslant c\kappa$, if
$\frac{\log N}{d}\leqslant T$ and $\mu\in[0,cT^{-1}\varepsilon^{2}]$ then,
with high probability,

$\lVert\mathbf{u}(x)|_{B_{i}(x)^{c}}\rVert\lesssim\sqrt{\alpha_{x}}\bigg{(}\frac{1+O(\varepsilon)}{\sqrt{\alpha_{x}-1}}\bigg{)}^{i+1}$

for all $x\in\mathcal{W}$ and $i\leqslant\frac{c\varepsilon^{2}}{T}\frac{\log
N}{\log d}$.

###### Proof.

Let $x\in\mathcal{W}$. For any $i$, $n\in\mathbb{N}$, we conclude from (4.4)
and (4.5) (see also (4.6)) that

$\lVert\mathbf{u}(x)|_{B_{i}(x)^{c}}\rVert\lesssim\frac{1}{\lambda(x)\sqrt{d}}\biggl{\lVert}Q_{i}\sum_{k=0}^{n}\bigg{(}\frac{H^{(\mathcal{V})}}{\lambda(x)}\bigg{)}^{k}\mathbf{1}_{S_{1}(x)}\biggr{\rVert}+\frac{\lVert(H^{(\mathcal{V})})^{n+1}\mathbf{1}_{S_{1}(x)}\rVert}{\sqrt{d}\lambda(x)^{n+1}}$

since
$\lvert\langle\mathbf{1}_{x}\mspace{2.0mu},\mathbf{u}(x)\rangle\rvert\lesssim
1$, $\lVert Q_{i}\rVert\leqslant 1$ and
$\lVert(\lambda(x)-H^{(\mathcal{V})})^{-1}\rVert\lesssim 1$ by (4.3). We
denote the right-hand side of (3.2) by $r$. In the following, we always assume
that $n+1\leqslant r$ and tacitly use the graph properties listed in
Proposition 3.2. As in the proof of Proposition 4.1 (see (4.8) and use
$q_{x}\leqslant 1-\varepsilon$ by (4.1)), we find some constant
$\varepsilon>0$ such that if $n+1\leqslant r$ then

$\frac{\lVert(H^{(\mathcal{V})})^{n+1}\mathbf{1}_{S_{1}(x)}\rVert}{\sqrt{d}\lambda(x)^{n+1}}\lesssim\sqrt{\alpha_{x}}(1-\varepsilon)^{n+1}\,.$
(4.11)

We shall use the following result, whose proof is given at the end of this
subsection.

######  Claim 4.4.

Suppose that all vertices in $B_{r-1}(x)\setminus\\{x\\}$ have degree at most
$\tau d$, where $2\leqslant 2\sqrt{\tau}<\lambda(x)$. Then for all $n\leqslant
r-1$ and $i\in\mathbb{N}$ we have on $\Omega$

$\frac{1}{\lambda(x)\sqrt{d}}\biggl{\lVert}Q_{i}\sum_{k=0}^{n}\bigg{(}\frac{H^{(\mathcal{V})}}{\lambda(x)}\bigg{)}^{k}\mathbf{1}_{S_{1}(x)}\biggr{\rVert}\lesssim\sqrt{\alpha_{x}}\bigg{(}\frac{2}{\lambda(x)+\sqrt{\lambda(x)^{2}-4\tau}}\bigg{)}^{i+1}\,.$
(4.12)

We now explain how we choose $\tau$ and $n$ in the subcritical and the
critical regimes in order to deduce Proposition 4.3 from Claim 4.4. In the
subcritical regime, i.e. for the proof of (i), we choose
$\tau\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\alpha^{*}(1-3\varepsilon)$
and $n\leqslant\varepsilon\frac{\log N}{\log d}$ for some small enough
constant $\varepsilon>0$. By arguing similarly as in the proof of Corollary
B.3 below, we find a constant $T\geqslant 1$ such that

$\frac{4\tau}{\lambda(x)^{2}}\leqslant\frac{4\alpha^{*}(1-\varepsilon)(1+o(1))}{\Lambda(\alpha^{*}(\mu))^{2}}=O(\varepsilon)<1$
(4.13)

by (3.3) and (2.2) if $\frac{\log N}{d}\geqslant T$. Here, the last inequality
holds if $\varepsilon$ is sufficiently small. Hence, the assumption on $\tau$
in Claim 4.4 holds. Moreover, with our choice of $\tau$, the degrees in
$B_{n}(x)\setminus\\{x\\}$ are bounded by $\tau d$ due to Proposition 3.2 (iv)
and our assumption on $n$. Hence, the assumptions of Claim 4.4 hold. As
$\lambda(x)\lesssim\sqrt{\frac{\log N}{d}}$ by (3.3) and Proposition 3.1 (i),
the right-hand side of (4.11) is bounded by the right-hand side of (4.12) if
$n=iC\log\big{(}\frac{10\log N}{d}\big{)}$ for some sufficiently large
constant $C$. Since we need that $n+1\leqslant r$, this yields the upper bound
on $i$ in (i). From (4.13) and (3.3), we deduce that
$\lambda(x)+\sqrt{\lambda(x)^{2}-4\tau}=\lambda(x)\big{(}1+\sqrt{1-\frac{4\tau}{\lambda(x)^{2}}}\big{)}=\Lambda(\alpha_{x})(1+o(1))(2+O(\varepsilon))\geqslant
2\sqrt{\alpha_{x}-1}(1+O(\varepsilon))^{-1}$, which completes the proof of
(i).

For the proof of (ii), we note that $\mu\leqslant c\varepsilon^{2}T^{-1}<1/3$
for a sufficiently small constant $c>0$ since $T\geqslant 1$,
$\varepsilon\leqslant c\kappa$ and $\kappa\leqslant 1$. We choose
$\tau=1+\varepsilon$ for some constant $\varepsilon>0$. As
$\lambda(x)^{2}-4\tau=(\lambda(x)^{2}-4)(1-\frac{4\varepsilon}{\lambda(x)^{2}-4})>0$
due to (3.3) and (2.2) if $\varepsilon\leqslant c\kappa$ with a small enough
constant $c>0$. This establishes the first condition for (4.12). We set
$R\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\frac{c\varepsilon^{2}}{T}\frac{\log
N}{\log d}$ and conclude from Bennett’s inequality (Lemma E.1 below) and
Proposition 3.2 that

$\mathbb{P}\Big{(}\alpha_{y}\leqslant\tau\text{ for all }x\in\mathcal{W}\text{
and for all }y\in
B_{R}(x)\setminus\\{x\\}\Big{)}\leqslant\exp\bigg{(}\bigg{(}\mu+R\frac{\log
d}{\log N}-\frac{d}{\log N}h(\varepsilon)\bigg{)}\log N\bigg{)}\,,$

where
$h(\varepsilon)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=(1+\varepsilon)\log(1+\varepsilon)-\varepsilon$.
Since $h(\varepsilon)\geqslant 3c\varepsilon^{2}$ for some small enough
constant $c>0$, the upper bound on $\mu$ imposed in the statement, the
definition of $R$ and $\frac{d}{\log N}\geqslant\frac{1}{T}$ imply that the
factor in front of $\log N$ is negative. Therefore, with high probability, we
can apply (4.12) simultaneously for all $x\in\mathcal{W}$. We choose
$n=C(i+1)$ and deduce that if $C>0$ is a large enough constant then the error
in (4.11) is dominated by the right-hand side of (4.12) as $\lambda(x)\lesssim
1$ for $\frac{\log N}{d}\leqslant T$. We recall that $r$ denotes the right-
hand side of (3.2) and note that the condition of (4.11),
$n+1=C(i+1)+1\leqslant r$, can be satisfied by possibly decreasing the
constant $c>0$. Finally, we obtain
$\lambda(x)+\sqrt{\lambda(x)^{2}-4\tau}=\lambda(x)+\sqrt{\lambda(x)^{2}-4\tau}+O(\frac{\varepsilon}{\sqrt{\lambda(x)^{2}-4}})=2\sqrt{\alpha_{x}-1}(1+O(\varepsilon))^{-1}$
similarly as argued above and in the proof of (i) using $\varepsilon\leqslant
c\kappa$ and $\kappa\leqslant 1$. This proves (ii) and, thus, Proposition 4.3.
∎

###### Proof of Claim 4.4.

For $y\in S_{1}(x)$ we denote by $B_{n}^{+}(y)$ the ball of radius $n$ around
$y$ in the graph $\mathbb{G}|_{[N]\setminus\\{x\\}}$, and we write
$S_{n}^{+}(y)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=B_{n}^{+}(y)\setminus
B_{n-1}^{+}(y)$. Since $\mathbb{G}|_{B_{n+1}(x)\setminus\mathcal{V}}$ is a
forest on $\Omega$ and for each $y\in S_{1}(x)$, $\mathbb{G}|_{B_{n}^{+}(y)}$
is a tree, we obtain

$(A^{(\mathcal{V})})^{k}\mathbf{1}_{S_{1}(x)}=\sum_{y\in
S_{1}(x)}\sum_{j=1}^{k+1}\sum_{z\in
S_{j-1}^{+}(y)}\mathbf{1}_{z}N_{k}(y,z)\,,$

where $N_{k}(y,z)$ denotes the number of walks on $\mathbb{G}|_{B_{n}^{+}(y)}$
of length $k$ between $y$ and $z$.

Thus, for $i\geqslant 0$, we conclude

$\displaystyle
Q_{i}\sum_{k=0}^{n}\frac{1}{\lambda(x)^{k}d^{k/2}}(A^{(\mathcal{V})})^{k}\mathbf{1}_{S_{1}(x)}=\,$
$\displaystyle Q_{i}\sum_{y\in S_{1}(x)}\sum_{j=1}^{n+1}\sum_{z\in
S_{j-1}^{+}(y)}\sum_{k=j-1}^{n}\mathbf{1}_{z}\frac{N_{k}(y,z)}{\lambda(x)^{k}d^{k/2}}$
$\displaystyle=\,$ $\displaystyle\sum_{y\in
S_{1}(x)}\sum_{j=i+1}^{n+1}\sum_{z\in
S_{j-1}^{+}(y)}\mathbf{1}_{z}\bigg{(}\sum_{k=j-1}^{n}\frac{N_{k}(y,z)}{\lambda(x)^{k}d^{k/2}}\bigg{)}\,,$

where the second step follows from the definition of $Q_{i}$. Since the sets
$\\{B_{n}^{+}(y)\mathrel{\vbox{\hbox{.}\hbox{.}}}y\in S_{1}(x)\\}$, are
disjoint, we conclude that

$\biggl{\lVert}Q_{i}\sum_{k=0}^{n}\bigg{(}\frac{H^{(\mathcal{V})}}{\lambda(x)}\bigg{)}^{k}\mathbf{1}_{S_{1}(x)}\biggr{\rVert}^{2}=\sum_{y\in
S_{1}(x)}\sum_{j=i+1}^{n+1}\sum_{z\in
S_{j-1}^{+}(y)}\bigg{(}\sum_{k=j-1}^{n}\frac{N_{k}(y,z)}{\lambda(x)^{k}d^{k/2}}\bigg{)}^{2}\,.$
(4.14)

Next, let $z\in S_{j-1}^{+}(y)$ for some $y\in S_{1}(x)$. We note that
$N_{k}(y,z)=0$ if $k-(j-1)$ is odd due to the bipartite structure of a tree.
If this difference is even, then we now show that

$N_{k}(y,z)\leqslant(M^{k})_{1j}(\tau d)^{(k-(j-1))/2}\,,$ (4.15)

where $M$ is the adjacency matrix of $\mathbb{N}^{*}$ (regarded as a graph
where consecutive numbers are adjacent), see (E.2) below for a precise
definition, under the assumption that the degree of each vertex in
$\mathbb{G}|_{B_{n}^{+}(y)}$ is bounded by $\tau d$.

For the proof of (4.15), we introduce the set of walks on $\mathbb{N}^{*}$

$W_{k}(j)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\\{\text{walks
}\gamma\text{ on }\mathbb{N}^{*}\text{ of length }k\text{ such that
}\gamma(0)=1\text{ and }\gamma(k)=j\\}\,,$

and for each $\gamma\in W_{k}(j)$ we introduce the set of walks on
$\mathbb{G}|_{B_{n}^{+}(y)}$ that project down to $\gamma$,

$W_{k}(y,z;\gamma)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\\{\text{walks
}\Gamma\text{ on }\mathbb{G}|_{B_{n}^{+}(y)}\text{ of length }k\text{ such
that }\Gamma(0)=y,\Gamma(k)=z\text{ and
}\mathrm{d}(x,\Gamma(\,\cdot\,))=\gamma\\}\,.$

By definition, any walk $\Gamma\in W_{k}(y,z;\gamma)$ projects down to a walk
$\gamma\in W_{k}(j)$, which implies

$N_{k}(y,z)\leqslant\sum_{\gamma\in W_{k}(j)}\lvert
W_{k}(y,z;\gamma)\rvert\,.$ (4.16)

In order to prove (4.15), we fix $\gamma\in W_{k}(j)$ and estimate $\lvert
W_{k}(y,z;\gamma)\rvert$. For $i\in[j]$, let
$T_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\max\\{t\in\\{0,\dots,k\\}\mathrel{\vbox{\hbox{.}\hbox{.}}}\gamma(t)=i\\}$,
i.e. $T_{i}$ is the last time when $\gamma$ hits $i$. Clearly,
$T_{1}<T_{2}<\ldots<T_{j-1}<T_{j}=k$. See Figure 4.1 for an illustration of
the walks $\gamma$ and $\Gamma$. At each time $T_{i}$ with $i\in[j-1]$, the
walk $\gamma$ takes a step to the right, and by definition of the times
$T_{i}$, any walk $\Gamma\in W_{k}(y,z;\gamma)$ takes a step outwards on the
geodesic from $y$ to $z$. This means that $j-1$ of the $k$ steps of $\Gamma$
are fixed. Of the remaining $k-(j-1)$ steps, half correspond to steps to the
left of $\gamma$, which again correspond to a uniquely determined step of
$\Gamma$ along the unique path back towards $y$. Hence, only $(k-(j-1))/2$ of
the $k$ steps of $\Gamma$ are free to choose. Since the degrees in
$\mathbb{G}|_{B_{n}^{+}(y)}$ are bounded by $\tau d$, we obtain $\lvert
W_{k}(y,z;\gamma)\rvert\leqslant(\tau d)^{(k-(j-1))/2}$. Plugging this
estimate into (4.16) implies (4.15), since $\lvert
W_{k}(j)\rvert=(M^{k})_{1j}$ by definition of $M$.

$x$
---
$y$
---
$z$
---
$1$
---
$0$
---
$T_{1}$
---
$T_{2}$
---
$2$
---
$j$
---
$T_{3}$
---
$T_{4}$
---
$T_{5}$
---
$T_{6}=k$
---
$t$
---
$\gamma(t)$
---
Figure 4.1: An illustration of two walks $\gamma\in W_{k}(j)$ (bottom) and
$\Gamma\in W_{k}(y,z;\gamma)$ (top). Here $k=21$ and $j=6$. By definition of
$W_{k}(y,z;\gamma)$, for each $t\in\\{0,\dots,k\\}$ we have
$\gamma(t)=\mathrm{d}(x,\Gamma(t))$. The time $T_{i}$ is the last time when
$\gamma$ hits $i$. We draw an edge $\\{\Gamma(t),\Gamma(t+1)\\}$ in red if the
choice of the vertex $\Gamma(t+1)$ is uniquely determined by $\gamma$ and in