# Asymptotic absence of poles of Ihara zeta function of large Erdős-Rényi
random graphs

Oleksiy Khorunzhiy

(Received Month XX, 20XX, revised Month XX, 20XX)

###### Abstract

Using recent results on the concentration of the largest eigenvalue and
maximal vertex degree of large random graphs, we show that the infinite
sequence of Erdős-Rényi random graphs $G(n,\rho_{n}/n)$ such that
$\rho_{n}/\log n$ infinitely increases as $n\to\infty$ verifies a version of
the graph theory Riemann Hypothesis.

Key words: random graphs, random matrices, Ihara zeta function, graph theory
Riemann hypothesis

Mathematical Subject Classification 2010: 05C80,11M50,15B52,60B20

Journal of Mathematical Physics, Analysis, Geometry
20XX, Vol. X, No. X, pp. Asymptotic absence of poles of Ihara zeta function of
large Erdős-Rényi random graphs–LABEL:end
doi:

Asymptotic absence of poles of Ihara zeta function of large Erdős-Rényi random
graphs†† © Oleksiy Khorunzhiy, 20XX

Oleksiy Khorunzhiy

##  1 Ihara zeta function and graph theory Riemann hypothesis

Given a finite connected non-oriented graph $\Gamma=(V,E)$ with the vertex set
$V=(\alpha_{1},\dots,\alpha_{n})$ and the edge set $E$, the Ihara zeta
function (IZF) $Z_{\Gamma}(u)$ is determined for sufficiently small $|u|$ by
equality

$Z_{\Gamma}(u)=\prod_{[C]}\left(1-u^{\nu(C)}\right)^{-1},$ (1.1)

where $[C]$ denotes the equivalence class of closed primitive backtrackless
tailless paths $C$ and $\nu(C)=k-1$, $k$ being the length of $C$ [19]. The
$k$-step path over graph
$C=(\alpha_{i_{1}},\alpha_{i_{2}},\dots,\alpha_{i_{k-1}},\alpha_{i_{k}})$,
$\\{\alpha_{i_{l}},\alpha_{i_{l+1}}\\}\in E$ is closed when
$\alpha_{i_{k}}=\alpha_{i_{1}}$. The path $C$ is backtrackless if
$\alpha_{i_{l-1}}\neq\alpha_{i_{l+1}}$ for all $l=2,\dots,k-1$. The path $C$
is tailless if $\alpha_{i_{2}}\neq\alpha_{i_{k-1}}$. The equivalence class
$[C]$ includes $C$ and all paths obtained from $C$ with the help of all cyclic
permutation of its elements. The closed path $C$ is primitive if there is no
smaller path $\tilde{C}$ such that $C=\tilde{C}^{k}$.

Zeta function (1.1) has been introduced by Y. Ihara in the algebraic context
[19]. Ihara’s theorem says that the IZF (1.1) is the reciprocal of a
polynomial and that for sufficiently small $|u|$

$Z_{\Gamma}(u)^{-1}=(1-u^{2})^{r-1}\det\big{(}I+u^{2}(B-I)-uA\big{)},\quad
u\in{\mathbb{C}},$ (1.2)

where $A=(a_{ij})_{i,j=1,\dots,N}$ is the adjacency matrix of $\Gamma$,
$B=\hbox{diag}\left(\sum_{j=1}^{N}a_{ij}\right)$ and

$r-1={\mathrm{\,Tr}}(B-2I)/2.$ (1.3)

Let us note that the Ihara zeta function can also be determined as the
exponential expression [32],

$Z_{\Gamma}(u)=\exp\left\\{\sum_{k\geq 1}{{\cal N}_{k}\over k}u^{k}\right\\},$
(1.4)

where ${\cal N}_{k}$ is the number of classes of closed backtrackless tailless
primitive paths of the length $k$ over the edges of $\Gamma$. The Ihara’s
theorem has been proven initially for $q+1$-regular graphs, then it has been
generalized by Bass to the cases of possibly irregular graphs [2] (see also
[11]).

There exists an analog of the Riemann hypothesis formulated for $q+1$-regular
graphs $\Gamma=X^{(q+1)}$ with the help of the Ihara zeta function. According
to the definition by Stark and Terras [30], a graph $X^{(q+1)}$ verifies the
graph theory Riemann hypothesis (GTRH) iff its Ihara zeta function is such
that

$\hbox{Re\,}s\in(0,1)\ {\hbox{and
}}\left(Z_{X^{(q+1)}}\big{(}q^{-s}\big{)}\right)^{-1}=0\ \ \ \hbox{ imply }\
\hbox{Re\,}s={1\over 2}.$ (1.5)

This relation means that the graph $X^{(q+1)}$ is such that there is no poles
of the Ihara zeta function $Z_{X}(u)$ in the disk $1/q<|u|<1$ excepting those
situated on the circle $|u|={1/\sqrt{q}}$. The following statement is
formulated by Stark and Terras [30] as a corollary of the formula (1.2).

######  Lemma 1.1.

A finite $(q+1)$-regular graph $X^{(q+1)}$ satisfies the Riemann hypothesis
iff for every eigenvalue $\lambda$ of its adjacency matrix $A_{X}$, we have

$|\lambda|\neq q+1\ \ \ \hbox{implies}\ \ \ |\lambda|\leq 2\sqrt{q}.$ (1.6)

We reproduce the proof of this lemma in Section 4 of the present paper. It is
fairly simple and uses an elementary observation that in the case of
$q+1$-regular graphs, relations (1.2) and (1.5) reduce the problem to the
study of zeroes of the quadratic equation

$1+qu^{2}-\lambda u=0,$

whose discriminant is negative if and only if $|\lambda|<2\sqrt{q}$.

Relation (1.5) can be reformulated in more convenient for us form as follows:

for any complex $v\in D_{q}$,

$D_{q}=\left\\{z\in{\mathbb{C}}:{1\over\sqrt{q}}<|z|<\sqrt{q}\right\\},$ (1.7)

the following statement

$\left(Z_{X^{(q+1)}}\left({v\over\sqrt{q}}\right)\right)^{-1}=0\quad\hbox{implies}\quad|v|=1$
(1.8)

is true. This means that the regular graph $X^{(q+1)}$ verifies the GTRH if
and only if the function

$\Phi^{(q+1)}(v)=Z_{X^{(q+1)}}\left({v\over\sqrt{q}}\right)$ (1.9)

has no poles in the region $v\in D_{1}^{(q)}\cup D_{2}^{(q)}$, where

$D_{1}^{(q)}=\left\\{v\in{\mathbb{C}}:1/\sqrt{q}<|v|<1\right\\}\quad{\hbox{and}}\quad
D_{2}^{(q)}=\left\\{v\in{\mathbb{C}}:1<|v|<\sqrt{q}\right\\}.$ (1.10)

Relation (1.6) represents a widely known in graph theory and applications the
second eigenvalue conjecture (see [1] and references therein). This condition
means that the distance between the maximal and the second maximal in absolute
value eigenvalues of a $q+1$-regular graph is greater than $q+1-2\sqrt{q}$.
The $(q+1)$-regular graphs that satisfy condition (1.6) are determined by
Lubotzky, Phillips and Sarnak as the Ramanujan graphs [25] (see also the
review [28] and references therein). The Ramanujan graphs are known to be good
expanders that make good communication networks (see e.g. [13, 28]). This
property can be explained by the observation that the diameter of a
$(q+1)$-regular graph is minimized by minimizing the second maximal eigenvalue
because the maximal eigenvalue is always equal to $q+1$ [8, 29, 28]. It is
proved by Friedman [12, 14] the proportion of $q+1$-regular graphs with $n$
vertices such that (1.6) is true with $2\sqrt{q}$ replaced by
$2\sqrt{q}+\varepsilon$ goes to 1 as $n\to\infty$ for any $\varepsilon>0$.

The notion of the Ramanujan graphs mostly concerns the regular graphs. Several
extensions of this notion has been considered [26, 30]. A definition of the
Ramanujan graphs in the case of non-regular graphs has been proposed by
Lubotzky [26]. It is given in terms of the eigenvalues of the adjacency matrix
of a graph $\Gamma$, its spectral radius and the spectral radius of the
adjacency operator on the universal covering tree of $\Gamma$.

The case when $\Gamma$ is chosen at random from the set of all possible graphs
of $n$ vertices has been considered in [20]. More precisely, the eigenvalue
distribution of the matrix $I+H(u)=I+u^{2}(B-I)-uA$ has been studied, where
$A$ is the adjacency matrix of the Edős-Rényi random graphs $G(n,\rho_{n}/n)$
(see the next section for the rigorous definition of the ensemble $G(n,p)$).
It is shown that in the limit $n\to\infty$ and $\rho_{n}/\log n\to\infty$ the
limiting eigenvalue distribution of $H(u)$ with properly normalized parameter
$u=v/\sqrt{\rho_{n}}$ exists and its density is given by a shift of the Wigner
semi-circle distribution. Then one can show that the limit of the mean value
of ${1\over n}\log Z_{\Gamma}(v/\sqrt{\rho_{n}})$, if it exists, satisfies a
version of (1.5).

Another approach allowing to include the case of non-regular random graphs
into consideration is based on the following representation of zeta function
(1.1),

$Z_{\Gamma}(u)^{-1}=\det(I-uW_{\Gamma}),$ (1.11)

where $W_{\Gamma}$ is the non-backtracking matrix of $\Gamma$ (see [16, 30]
and references therein). Representation (1.11) is known as the Ihara-Bass
formula and can be serve as the basis of the proof of the Ihara theorem (1.2)
for connected graphs.

Regarding representation (1.11), Stark and Terras defined $\Gamma$ to satisfy
the graph theory Riemann hypothesis if the matrix $W_{\Gamma}$ has no
eigenvalues with the absolute values inside of the interval
$(\sqrt{r_{W_{\Gamma}}},r_{W_{\Gamma}})$, where $r_{W_{\Gamma}}$ is the
Perron-Frobenius eigenvalue of $W_{\Gamma}$. In paper [5], the spectral
properties of the non-backtracking matrix $W_{\Gamma}$ of the the Erdős-Rényi
random graphs $\Gamma\in G(n,p_{n})$ have been studied. It is shown that the
graphs $\Gamma\in G(n,\alpha/n)$ verify a weak Ramanujan property in the sense
that in the limit $n\to\infty$, they satisfy with high probability the graph
theory Riemann hypothesis formulated above [18]. More precisely, it is proved
that $r_{W_{\Gamma}}\sim\alpha$ and all other eigenvalues $\lambda$ of
$W_{\Gamma}$ verify $|\lambda|\leq\sqrt{\alpha}+o(1)$ with high probability as
$n\to\infty$. It is stated that in this sense, the Erdős-Rényi random graphs
$G(n,\alpha/n)$ asymptotically satisfy the graph theory Riemann hypothesis
[5]. In this work the term ”with high probability” to indicate the situation
when one or another statement is true with probability $1+o(1)$, $n\to\infty$
i.e. tending to 1 as $n$ infinitely increases. This shows that the results of
[5] are much in the spirit of statements by Friedman cited above. It should be
also noted that the results of [5] as well as those of [12, 14] are obtained
with the help of the study of moments of non-backtracking matrix $W_{\Gamma}$.

The limiting eigenvalue distribution of non-backtracking matrices $W_{\Gamma}$
of Erdős-Rényi random graphs $G(n,p)$ have been also studied in the asymptotic
regimes when either $p\approx Const$ or $p=o(1)$ as $n\to\infty$ [33]. More
fine spectral characteristics of $W_{\Gamma}$ such as the presence of isolated
eigenvalues inside and outside of the bulk of the spectrum of $W_{\Gamma}$
have been considered in [9] for a generalization of the Erdős-Rényi random
graphs $G(n,\alpha/n)$ in the case when $\alpha/\log n\to\infty$ as
$n\to\infty$. It is shown, in particular, that with probability $1-o(1)$ all
eigenvalues of $W_{\Gamma}$ are located on the distance $o(\sqrt{\alpha})$ of
a circle of radius $\sqrt{\alpha-1}$ excepting two ones that are close to $1$
and $\alpha$ as $n\to\infty$. Since eigenvalues of $W_{\Gamma}$ determine
uniquely the poles of $Z_{\Gamma}(u)$ (1.11), the results of [9] can be
interpreted in the sense that the proportion of Erdős-Rényi random graphs that
verify the graph theory Riemann hypothesis (1.5) tends to one as $n\to\infty$.
This formulation put [9] in line with the works [12, 14] and [5]. The results
of [9] are obtained on the base of the known facts from spectral properties of
the adjacency matrices $A_{\Gamma}$ of random graphs combined with the
concentration results on the elements of $B$ and perturbation theorems by
Bauer and Fike allowing one to study the spectrum of the non-backtracking
matrix $W_{\Gamma}$ on the base of the knowledge of that of the adjacency
matrix $A_{\Gamma}$ (see also [5]).

In this paper, we follow the approach of [20] based on the study of the
spectrum of $I+u^{2}(B-I)-uA$ of the right-hand side of (1.2). This method
seems to be more simple and transparent than that using the non-backtracking
matrix $W_{\Gamma}$. Using classical perturbation theorems of the Weyl type
for singular values of matrices, concentration properties of $B$ [22] and
recent results on the concentration of the maximal eigenvalue of $A_{\Gamma}$
[27], we prove a statement that can be regarded as an improvement of that of
[9]. Namely, we show that the infinite series of probabilities of the events
that the normalized zeta function $Z_{\Gamma}(v/\sqrt{\rho_{n}})$ of the
Erdős-Rényi random graphs $G(n,\rho_{n}/n)$ in the asymptotic regime when
$\rho_{n}\gg\log n$ has a pole in any domain close to
$D=\\{v\in{\mathbb{C}}:|v|\neq 1\\}$ converges. The result obtained in the
present paper can be regarded as a one more confirmation of the conjecture
that almost all Erdős-Rényi random graphs $\\{G(n,p_{n})\\}_{n\geq 1}$
satisfy, in the limit $n\to\infty$, $np_{n}/\log n\to\infty$, a version of the
graph theory Riemann hypothesis.

##  2 Ihara zeta function of Erdős-Rényi random graphs

Let us consider a family of jointly independent random variables

${{\cal A}}_{n,\rho}=\\{a_{ij}^{(n,\rho)},\ 1\leq i<j\leq n\\}$

that have the probability distribution

$a_{ij}^{(n,\rho)}=\begin{cases}1,&\text{with probability $p_{n}=\rho/n$},\\\
0,&\text{with probability $1-{\rho/n}\,$}\end{cases},\ \ 0<\rho<n.$

We assume that the family ${\cal A}_{n,\rho}$ is determined on a probability
space $\Omega_{n,\rho}$ and denote by ${\mathbb{E}}={\mathbb{E}}_{n,\rho}$ the
mathematical expectation with respect to the probability measure
$P=P_{n,\rho}$ generated by ${\cal A}_{n,\rho}$.

The ensemble of real symmetric random matrices $A^{(n,\rho)}$ with elements

$\left(A^{(n,\rho)}\right)_{ij}=\begin{cases}a^{(n,\rho)}_{ij},&\text{if
$i<j$},\\\ a^{(n,\rho)}_{ji},&\text{if $i>j$},\\\ 0,&\text{if
$i=j$},\end{cases}\quad i,j\in\\{1,\dots,n\\}$ (2.1)

can be regarded as the adjacency matrix of a non-oriented random graph
$\Gamma^{(n,\rho)}$. The family of such random graphs
$\\{\Gamma^{(n,\rho)}\\}$ is usually denoted by $G(n,p_{n})$, where we have
taken $p_{n}=\rho/n$. This family is equivalent in many aspects to the
ensemble of random Erdős-Rényi graphs [10] and is often referred simply as the
Erdős-Rényi random graphs (see monograph [4]).

Given $\Gamma^{(n,\rho)}$, we consider the corresponding right-hand side of
(1.2) an say that it determines the Ihara zeta function of $\Gamma^{(n,\rho)}$
despite of the fact that this graph can be disconnected,

$(1-u^{2})^{r-1}\,\det\big{(}I+u^{2}(B^{(n,\rho)}-I)-uA^{(n,\rho)}\big{)}=\left(Z_{\Gamma^{(n,\rho)}}(u)\right)^{-1},\quad
u\in{\mathbb{C}},$ (2.2)

where

$\left(B^{(n,\rho)}\right)_{ij}=\,\delta_{ij}\
\sum_{k=1}^{n}\,a^{(n,\rho)}_{ik}.$ (2.3)

According to (1.3), we have denoted in (2.2)

$r=\,{1\over 2}\,\sum_{i,j=1}^{n}a^{(n,\rho)}_{ij}\,-n+1.$ (2.4)

We study IZF (2.2) in the limiting transition $n\to\infty$ when the average
value of the vertex degree of $\Gamma^{(n,\rho_{n})}$ given by
$(B^{(n,\rho_{n})})_{ii}$ (2.3) goes to infinity more rapidly than $\log n$.
This means that

$n\to\infty,\quad\rho_{n}/\log n=\chi_{n}\to\infty.$ (2.5)

We denote this limiting transition by $(\rho,\chi)_{n}\to\infty$. Writing
(2.5), we assume that an infinite sequence $(\chi_{n})_{n\geq 1}$ is
determined and $\rho_{n}$ is given by relation

$\rho_{n}=\chi_{n}\log n,\quad n\geq 1.$

In what follows, we omit the subscript in $\rho_{n}$ when no confusion can
arise.

In paper [20], it is shown that in the limit (2.5), it is natural to consider
(2.4) with the spectral parameter $u$ normalized by the square root of
$\rho=\rho_{n}$. Thereby we introduce a normalized version of Ihara zeta
function (2.2) with the spectral parameter $u=v/\sqrt{\rho}$

$\tilde{Z}^{(n,\rho)}(v,\omega)=Z_{\Gamma^{(n,\rho)}(\omega)}\left({v\over\sqrt{\rho}}\right),\quad\omega\in\Omega_{n,\rho_{n}},\quad
v\in{\mathbb{C}},$

where

$\left(Z_{\Gamma^{(n,\rho)}}\left({v\over\sqrt{\rho}}\right)\right)^{-1}=\left(1-{v^{2}\over\rho}\right)^{r-1}\det\left(-vH^{(n,\rho)}\right),$
(2.6)

where

$H^{(n,\rho)}(v)=I+{v^{2}\over\rho}\left(B^{(n,\rho)}-I\right)-{1\over\sqrt{\rho}}A^{(n,\rho)}.$

Our main result is given by the following statement.

######  Theorem 2.1.

Let $D_{\varepsilon,\varepsilon^{\prime}}$ with
$\varepsilon,\varepsilon^{\prime}>0$ be a union of two complex domains

$D^{(1)}_{\varepsilon,\varepsilon^{\prime}}=\\{z\in{\mathbb{C}}:\varepsilon^{\prime}<|z|<1-\varepsilon\\}\quad{\hbox{and}}\quad
D^{(2)}_{\varepsilon,\varepsilon^{\prime}}=\\{z\in{\mathbb{C}}:1+\varepsilon<|z|<1/\varepsilon^{\prime}\\}.$
(2.7)

We consider two subsets
$\Phi^{(1)}_{n,\rho}\left(\varepsilon,\varepsilon^{\prime}\right)$ and
$\Phi^{(2)}_{n,\rho}\left(\varepsilon,\varepsilon^{\prime}\right)$ determined
by relation

$\Phi^{(i)}_{n,\rho}\left(\varepsilon,\varepsilon^{\prime}\right)=\left\\{\omega\in\Omega:\,{\hbox{there
exists}}\ v\in D^{(i)}_{\varepsilon,\varepsilon^{\prime}}\ {\hbox{such that
}}\ \left(\tilde{Z}^{(n,\rho)}(v,\omega)\right)^{-1}=0\right\\},$ (2.8)

for $i=1$ and $i=2$. With the choice of

$\varepsilon_{n}={2\over(\chi_{n})^{1/8}}\quad{\hbox{and
}}\quad\varepsilon^{\prime}_{n}={1\over\sqrt{\rho_{n}}(1-\kappa)},\quad\kappa>0,$
(2.9)

the following series of probabilities converge,

$\sum_{n\geq
1}P_{n,\rho_{n}}\left(\Phi^{(i)}_{n,\rho_{n}}\left(\varepsilon_{n},\varepsilon^{\prime}_{n}\right)\right)<\infty,\quad
i=1,2$ (2.10)

under asymptotic condition (2.5).

We prove Theorem 2.1 in Section 3 below. Let us note that we can prove
slightly more powerful statement by adding to the complex domains
$D^{(i)}_{\varepsilon,\varepsilon^{\prime}}$ (2.7) real intervals

$I^{(1)}_{\hat{\varepsilon},\varepsilon^{\prime}}=\\{v\in{\mathbb{R}}:\varepsilon^{\prime}<v<1-\hat{\varepsilon}\\}\quad{\hbox{and}}\quad
I^{(2)}_{\hat{\varepsilon},\varepsilon^{\prime}}=\\{v\in{\mathbb{R}}:1+\hat{\varepsilon}<v<1/\varepsilon^{\prime}\\},$

where $\varepsilon^{\prime}=\varepsilon^{\prime}_{n}$ is given by (2.9) and

$\hat{\varepsilon}_{n}={\hat{h}\over(\chi_{n})^{1/4}}$ (2.11)

with sufficiently large $\hat{h}>0$. We concentrate ourself on the main case
of complex domains, the case of real $v$ is briefly discussed at the end of
Section 3.

Let us formulate a corollary of Theorem 2.1 that characterizes the points of
the complex plane in the form close to (1.10).

######  Corollary 2.2.

For any given

$v\in D^{(1)}\cup
D^{(2)}=\\{z:z\in{\mathbb{C}},0<|z|<1\\}\cup\\{z:z\in{\mathbb{C}},1<|z|\\},$

the following series of probabilities converges,

$\sum_{n\geq
1}P_{n,\rho_{n}}\left(\left\\{\omega\in\Omega_{n,\rho_{n}}:\left(\tilde{Z}^{(n,\rho_{n})}(v,\omega)\right)^{-1}=0\right\\}\right)<\infty,$
(2.12)

where $\rho_{n}=\chi_{n}\log n$, $\chi_{n}\to\infty$ as $n\to\infty$.

The proof of this statement follows immediately from the proof of Theorem 2.1.

Let us note that the statement of Corollary 2.2 can be formulated in its
equivalent form,

$\sum_{n\geq
1}P_{n,\rho_{n}}\left(\left\\{\omega:\left(Z_{\Gamma^{(n,\rho_{n})}}\left({v\over\sqrt{\rho}_{n}}\right)\right)^{-1}=0\right\\}\right)=+\infty\quad{\hbox{implies}}\quad|v|=1.$
(2.13)

This shows that Corollary 2.2 can be regarded as a direct analog of the
statement (1.8) in the case of large random graphs.

Let us outline the proof of Theorem 2.1. Definition (2.6) shows that if
$v^{2}\neq\rho$, then the function $Z_{\Gamma^{(n,\rho)}}$ has a pole at $v$
if and only if

$v\left(1-{1\over\rho}\right)+v-\lambda_{j}\left({1\over\sqrt{\rho}}A+v\left({1\over\rho}B-I\right)\right)=0$
(2.14)

for some $j$, where $\lambda_{j}(M)$ denotes the $j$-th eigenvalue of $M$. If
one accepts that the expression in last braces asymptotically vanishes

$\|{1\over\rho}B-I\|=o(1),$ (2.15)

then it can be regarded as a small perturbation of the eigenvalues of
$\tilde{A}=A/\sqrt{\rho}$. Neglecting the corresponding term in the right-hand
side of (2.14) as well as the vanishing term $-1/\rho$ in the first braces of
(2.14), one could say that (2.14) is equivalent to the condition that

${1\over v}+v-\lambda_{j}(\tilde{A})=0$ (2.16)

for some $j\in\\{1,\dots,n\\}.$ It is known since [15, 23] that the normalized
adjacency matrices of the Erdős-Rényi random graphs $G(n,\rho/n)$ have all
eigenvalues, excepting the maximal one $\lambda_{1}(\tilde{A})$,
asymptotically bounded in absolute value by $2+\delta_{n}$ in the limit
$n\to\infty$, $\rho\gg\log n$, where $\delta_{n}$ tends to zero. Therefore the
probability of the event (2.16) rapidly decays for all $j\in\\{2,\dots,n\\}$
as $n\to\infty$ for any $v$ verifying $|v|\neq 1$. It is worthy note that
important part of this proposition is that it can be proved uniformly with
respect to complex $v$ belonging to growing domains $D^{(1)}$ and $D^{(2)}$
(2.7). To do this, we use an important property of the ellipsoidal curves of
the form

${\cal E}_{r}=\left\\{w(z)=z+{1\over z},\ z=re^{i\varphi},\
0\leq\varphi<2\pi\right\\}$ (2.17)

and the distance between the points of real axis and ${\cal E}_{r}$.

To establish convergence of the series (2.10), we use recent results on the
concentration properties of eigenvalues of adjacency matrices of random graphs
[3, 27]. Relation (2.15) reflects the concentration property of diagonal
elements of $B-I$

$\max_{1\leq i\leq
n}\left|{1\over\rho}\left(B^{(n,\rho)}\right)_{ii}-1\right|=o(1),\quad
n,\rho\to\infty$ (2.18)

that is also well known in the literature (for example, see monograph [4] and
paper [22]). Convergence (2.18) can be interpreted as asymptotic regularity of
the Erdős-Rényi random graphs when the average vertex degree goes to infinity.
Taking into account this observation, one can say that the proof of Theorem
2.1 is equivalent in certain sense to the proof of a stochastic version of
Lemma 1.1 by Stark and Terras.

##  3 Proof of Theorem 2.1

Let us rewrite definition (2.7) in the form

$H^{(n,\rho_{n})}(v)=\tilde{A}^{(n,\rho_{n})}-\gamma^{(n,\rho_{n})}(v)I-v\hat{B}^{(n,\rho_{n})},$
(3.1)

where $\hat{B}=\tilde{B}-I(n-1)/n$,

$\left(\tilde{B}^{(n,\rho)}\right)_{ij}={1\over\rho}\left(B^{(n,\rho)}\right)_{ij}$

and

$\left(\tilde{A}^{(n,\rho)}\right)_{ij}={1\over\sqrt{\rho}}\,a^{(n,\rho)}_{ij},\quad
i,j\in\\{1,\dots,n\\}.$

We have also denoted

$\gamma^{(n,\rho_{n})}(v)={1-v^{2}/\rho\over v}+{v(n-1)\over n}=v+{1\over
v}-v\left({1\over n}+{1\over\rho_{n}}\right).$

The poles of $\tilde{Z}^{(n,\rho)}(v,\omega)$ (2.6) with $v^{2}\neq\rho$
correspond to zeroes of the determinant of $H^{(n,\rho)}$. Introducing the
subset

$\Phi_{n,\rho}(v)=\\{\omega:\ \det(H^{(n,\rho)}(v))=0\\},$ (3.2)

we can write that subsets $\Phi^{(i)}$ of (2.8) are given by relations

$\Phi^{(i)}_{n,\rho}(\varepsilon_{n},\varepsilon^{\prime}_{n})=\cup_{v\in
D^{(i)}_{\varepsilon_{n},\varepsilon^{\prime}_{n}}}\Phi_{n,\rho}(v),\quad
i=1,2.$

It should be noted that $\Phi^{(1)}$ and $\Phi^{(2)}$ are determined as
uncountable unions of measurable events; since the probability space
$\Omega_{n,\rho}$ generated by (2.1) can be viewed as a discrete set, we
conclude that $\Phi^{(i)}$ are both measurable. In what follows, we replace
denotations of events $\\{\omega:\Upsilon(\omega)\\}$ simply by
$\\{\Upsilon\\}$. We will omit the superscripts $n$ and $\rho$ in
$H^{(n,\rho)}$ and everywhere below, when no confusion can arise. We prove
relation (2.10) with $i=2$ in the full extent. The proof of (2.10) in the case
of $i=1$ is given in less details.

###  3.1 Proof of Theorem 2.1 in the case of $i=2$.

The following elementary statement shows that the study of $\det(H(v))$ (3.1)
can be reduced to the study of the product of singular values of $H(v)$. We
denote these singular values by

$\sigma_{1}(H(v))\leq\sigma_{2}(H(v))\leq\dots\leq\sigma_{n}(H(v)).$ (3.3)

Here and below we omit the superscripts $n$ and $\rho_{n}$ everywhere when no
confusion can arise.

######  Lemma 3.1.

For any $v\in{\mathbb{C}}$, the equivalence

$\det(H(v))\neq 0\iff\prod_{k=1}^{n}\sigma_{k}(H(v))\neq 0$ (3.4)

is true.

  * Proof.Since $\tilde{A}$ is a real symmetric matrix and $\hat{B}$ is a real diagonal one, then we can write for hermitian conjugate that

$\big{(}H(v)\big{)}^{*}_{ij}=\overline{\big{(}H(v)\big{)}_{ji}}=(1-\delta_{ji})\tilde{A}_{ji}-\bar{v}\delta_{ji}\hat{B}_{ii}-\overline{\gamma(v)}=\big{(}H(\bar{v})\big{)}_{ij}$

and therefore

$H^{*}(v)=H(\bar{v})\quad\hbox{and}\quad\overline{H(v)}=H(\bar{v}).$

It is easy to see that $\lambda(v)$ is an eigenvalue of $H(v)$ if and only if
$\overline{\lambda(v)}$ is the eigenvalue of $H(\bar{v})$. Then

$\det(H(v))\neq 0\iff\det(H(\bar{v}))\neq 0\iff\det(H^{*}(v)H(v))\neq 0.$

The last statement is equal to that of the right-hand side of (3.4). Let us
note that the last condition of (3.4) is equivalent to $\sigma_{1}(H(v))\neq
0$ because of (3.3) and due to positivity of $\sigma_{i}(H(v))$, $1\leq i\leq
n$. Lemma 3.1 is proved. ∎

The study of singular values of $H(v)$ (3.3) can be reduced to the study of
singular values of $\tilde{A}-\gamma(v)I$ (3.1) due to the concentration
property (2.15) of the diagonal matrix $\hat{B}$. Using the Weyl’s inequality
for singular values of $n$-dimensional matrices $X$ and $Y$ (see [7] and [31],
Exercice 22),

$|\sigma_{i}(X+Y)-\sigma_{i}(X)|\leq\|Y\|,\quad i=1,\dots,n,$ (3.5)

where $\|Y\|$ is the operator norm of $Y$, we obtain that

$|\sigma_{i}(H^{(n,\rho)}(v))-\sigma_{i}(\tilde{A}^{(n,\rho)}-\gamma^{(n,\rho)}(v)I)|\leq\|v\hat{B}\|=|v|\max_{i=1,\dots,n}|\hat{\Delta}_{i}^{(n,\rho)}|,\quad
i=1,\dots,n,$ (3.6)

where

$\hat{\Delta}^{(n,\rho)}_{i}=\tilde{b}^{(n,\rho)}_{ii}-{n-1\over
n}={1\over\rho}\sum_{j\in\\{1,\dots,n\\},\ j\neq i}\
\left(a^{(n,\rho)}_{ij}-{\rho\over n}\right).$

We denote

$\hat{\Delta}_{\max}^{(n,\rho)}=\max_{i=1,\dots,n}|\hat{\Delta}_{i}^{(n,\rho)}|.$
(3.7)

We have seen above that $\Phi(v)=\\{\sigma_{1}(H(v))=0\\}$ and that

$\\{\sigma_{1}(H(v))=0\\}\subseteq\left\\{\sigma_{1}(\tilde{A}-\gamma^{(n,\rho)}(v)I)\leq|v|\hat{\Delta}_{\max}^{(n,\rho)}\right\\}.$
(3.8)

Elementary calculation shows that

$\displaystyle\sigma_{i}(\tilde{A}-\gamma^{(n,\rho)}(v)I)$
$\displaystyle=\lambda_{i}\big{(}(\tilde{A}-\gamma^{(n,\rho)}(v)I)(\tilde{A}-\gamma^{(n,\rho)}(v)I)^{*}\big{)}$
$\displaystyle=\lambda_{i}\big{(}(\tilde{A}-\alpha(v)I)^{2}\big{)}+\beta(v)^{2},$
(3.9)

where $\alpha(v)$ and $\beta(v)$ are the real and imaginary parts of
$\gamma(v)$, respectively. Diagonalizing $\tilde{A}-\alpha(v)I$, we deduce
from (3.9) that

$\sigma_{i}(\tilde{A}-\gamma^{(n,\rho)}(v)I)=\big{(}\lambda_{i}(\tilde{A})-\alpha(v)\big{)}^{2}+\beta(v)^{2}=|\lambda_{i}(\tilde{A})-\gamma(v)|^{2}.$
(3.10)

It follows from (3.8) and (3.10) that for any $v\in
D^{(2)}_{\varepsilon,\varepsilon^{\prime}}$,

$\displaystyle\Phi_{n,\rho}(v)$
$\displaystyle\subseteq\left\\{\min_{i=1,\dots,n}{|\lambda_{i}(\tilde{A})-\gamma^{(n,\rho)}(v)|^{2}\over|v|}\leq\hat{\Delta}_{\max}^{(n,\rho)}\right\\}$
$\displaystyle\subseteq\left\\{\inf_{v\in
D^{(2)}_{\varepsilon,\varepsilon^{\prime}}}\
\min_{i=1,\dots,n}{|\lambda_{i}(\tilde{A})-\gamma^{(n,\rho)}(v)|^{2}\over|v|}\leq\hat{\Delta}_{\max}^{(n,\rho)}\right\\}=R^{(n,\rho)}(\varepsilon,\varepsilon^{\prime}).$
(3.11)

Then

$\Phi^{(2)}_{n,\rho}(\varepsilon,\varepsilon^{\prime})=\cup_{v\in
D^{(2)}_{\varepsilon,\varepsilon^{\prime}}}\\{\sigma_{1}(H(v))=0\\}\subseteq
R^{(n,\rho)}(\varepsilon,\varepsilon^{\prime}),$ (3.12)

where we omitted $\varepsilon$ and $\varepsilon^{\prime}$ in $R$. Let us note
that the minimums of (3.11) can be taken in arbitrary order, in particular
such that

$\inf_{v\in
D^{(2)}_{\varepsilon,\varepsilon^{\prime}}}=\inf_{1+\varepsilon<r<1/\varepsilon^{\prime}}\
\ \inf_{0\leq\varphi<2\pi}.$

We denote these minimums by $M_{r}^{(2)}$ and $M_{\varphi}$ respectively.

In (3.11), the term $|\lambda_{i}(\tilde{A})-\gamma^{(n,\rho)}(v)|^{2}$ is a
squared distance between real $\lambda_{i}(\tilde{A})$ and the complex number

$\gamma^{(n,\rho)}(v)=v(1-\tau)+{1\over v},\quad\tau={1\over
n}+{1\over\rho}\,.$ (3.13)

Let us note that the application
$\gamma^{(n,\rho)}(\cdot):{\mathbb{C}}\to{\mathbb{C}}$ can be viewed as a
slightly modified version of the Zhukovsky transform $w(z)$ (2.17). For given
$r$, the points

${\cal E}(\dot{a},\dot{b})=\left\\{\gamma^{(n,\rho)}(re^{i\varphi}),\quad
0\leq\varphi<2\pi\right\\}$

form an ellipsoid in the complex plane ${\mathbb{R}}^{2}=\\{(x,y):x=\Re w,\
y=\Im w\\}$. An important property of the minimal distance from an ellipsoid
to a given real point $\lambda$ is studied in Section 4.

We write that

$R^{(n,\rho)}(\varepsilon,\varepsilon^{\prime})\subseteq R^{(n,\rho)}_{1}\cup
R^{(n,\rho)}_{2},$ (3.14)

where

$R^{(n,\rho)}_{1}=\left\\{M^{(2)}_{r}\,M_{\varphi}\
{|\lambda_{1}(\tilde{A})-\gamma(re^{i\varphi})|^{2}\over
r}\leq\hat{\Delta}_{\max}^{(n,\rho)}\right\\}$

and

$R^{(n,\rho)}_{2}=\left\\{M^{(2)}_{r}\,M_{\varphi}\ \min_{i=2,\dots,n}\
{|\lambda_{i}(\tilde{A})-\gamma(re^{i\varphi})|^{2}\over
r}\leq\hat{\Delta}_{\max}^{(n,\rho)}\right\\}.$

Let us study first the term $R^{(n,\rho)}_{2}$. To do this, we consider the
matrix

$\breve{A}^{(n,\rho)}={1-\delta_{ij}\over\sqrt{\rho}}\left(a^{(n,\rho)}_{ij}-{\rho\over
n}\right).$ (3.15)

It is known [15] that

$\lambda_{1}(\breve{A})\geq\lambda_{2}(\tilde{A})\geq\cdots\geq\lambda_{n}(\tilde{A})\geq\lambda_{n}(\breve{A}).$
(3.16)

For completeness, we reproduce in Section 4 the proof of (3.16) by Füredi and
Komlós [15]. It follows from (3.16) that

$\min_{i=2,\dots,n}\ {|\lambda_{i}(\tilde{A})-\gamma(re^{i\varphi})|^{2}\over
r}\geq\min_{i=1,\dots,n}\
{|\lambda_{i}(\breve{A})-\gamma(re^{i\varphi})|^{2}\over r}.$

Let us introduce the set

$\Upsilon_{\delta}=\\{\omega:\lambda_{\max}(\breve{A})\leq
2+\delta\\},\quad\delta>0.$

Then we can write an obvious inclusion

$R^{(n,\rho)}_{2}\subseteq(R^{(n,\rho)}_{2}\cap\Upsilon_{\delta})\cup\bar{\Upsilon}_{\delta}.$
(3.17)

We choose $\delta$ and $\varepsilon$ such that the point $2+\delta$ lies
inside the minimal ellipsoid,

$2+\delta<\min_{1+\varepsilon<r}\gamma(r),-$

(see relation (4.9) of Section 4 for more details). In Section 4 we show that
(see Lemma 4.2)

$M_{\varphi}{|\lambda_{i}(\breve{A})-\gamma(re^{i\varphi})|^{2}}I_{\Upsilon_{\delta}}\geq
M_{\varphi}{|\lambda_{\max}(\breve{A})-\gamma(re^{i\varphi})|^{2}}I_{\Upsilon_{\delta}},$

where $I_{\upsilon}$ is the indicator function of $\Upsilon$. It is also
proved in Lemma 4.2 that the minimal distance between
$\lambda_{\max}(\breve{A})$ and ellipsoid ${\cal E}(\dot{a},\dot{b})$ is
attained at the right extremum of ${\cal E}(\dot{a},\dot{b})$ given by
$\dot{a}=\gamma(r)$ (see (4.7)),

$M_{\varphi}{|\lambda_{\max}(\breve{A})-\gamma(re^{i\varphi})|^{2}}I_{\Upsilon_{\delta}}={|\lambda_{\max}(\breve{A})-\gamma(r)|^{2}}I_{\Upsilon_{\delta}}\geq|(2+\delta)-\gamma(r)|^{2}.$

Finally, the minimal value of $|(2+\delta)-\gamma(r)|^{2}/r$ with respect to
$r\in(1+\varepsilon,1/\varepsilon^{\prime})$ is given by the value

$\min_{1+\varepsilon<r<1/\varepsilon^{\prime}}{|(2+\delta)-\gamma(r)|^{2}\over
r}=F^{(1)}(2+\delta,\varepsilon,\varepsilon^{\prime},\tau)={(\varepsilon^{2}-\delta(1+\varepsilon)-\tau(1+\varepsilon)^{2})^{2}\over(1+\varepsilon)^{3}},$

see Lemma 4.2. Taking into account obvious inclusion,

$R^{(n,\rho)}_{2}\cap\Upsilon_{\delta}\subseteq\left\\{M_{r}^{(2)}\,M_{\varphi}{|\lambda_{\max}(\breve{A})-\gamma(re^{i\varphi})|^{2}\over
r}I_{\Upsilon_{\delta}}\leq\hat{\Delta}_{\max}^{(n,\rho)}\right\\},$

we can write that

$P\left(R^{(n,\rho)}_{2}\cap\Upsilon_{\delta}\right)\leq
P\left(\hat{\Delta}_{\max}^{(n,\rho)}\geq
F^{(1)}(2+\delta,\varepsilon,\varepsilon^{\prime},\tau)\right).$ (3.18)

It is proved in [22] that if $\rho_{n}=\chi_{n}\log n$ with
$\chi_{n}\to\infty$ as $n\to\infty$, then for any positif $\nu$ the following
upper bound holds,

$P\left(\hat{\Delta}_{\max}^{(n,\rho_{n})}>\nu\right)\leq{1\over
n^{\log(\nu\sqrt{\chi_{n}}(1+o(1)))}}\ ,\quad n\to\infty.$ (3.19)

We see that in the limit (2.5) when $\chi_{n}$ infinitely increases, we can
consider (3.19) with vanishing $\nu_{n}\to 0$ such that
$\nu_{n}\geq{3/\sqrt{\chi_{n}}}.$ This allows us to choose $\varepsilon$ in
the right-hand side of (3.18) such that $\varepsilon\to 0$ as $n\to\infty$. In
this case
$F^{(1)}(2+\delta,\varepsilon,\varepsilon^{\prime},\tau)=\varepsilon^{4}(1+o(1))$
for vanishing $\delta$ such that $\delta=o(\varepsilon^{2})$ (see relation
(4.13) of Section 4). Then the choice of $\varepsilon_{n}=2\chi_{n}^{-1/8}$
(2.9) is sufficient to conclude that

$\sum_{n=1}^{\infty}P(R_{2}^{(n,\rho_{n})}\cap\Upsilon_{\delta_{n}})<\infty,\quad\delta_{n}=o(\varepsilon_{n}^{2}),$
(3.20)

where $\rho_{n}$ satisfies conditions (2.5).

Let us show that

$\sum_{n\geq
1}P(\bar{\Upsilon}_{\delta_{n}})<\infty\quad{\hbox{with}}\quad\delta_{n}={1\over\chi_{n}^{3/8}}\
.$ (3.21)

It is easy to see that starting from some $n_{0}$, random matrix
$\breve{A}^{(n,\rho_{n})}$ (3.15) satisfies conditions of Theorem 2.7 of [3].
According to this theorem, there exists a constant $C>0$ such that

${\mathbb{E}}\|\breve{A}^{(n,\rho)}\|<2+{C\over\sqrt{\chi_{n}}},\quad(\rho,\chi)_{n}\to\infty.$
(3.22)

Adding to this result the general concentration inequality

$P\left(\left|\|\breve{A}^{(n,\rho)}\|-{\mathbb{E}}\|\breve{A}^{(n,\rho)}\|\right|\geq
t\right)\leq{2\over n^{c\chi_{n}t^{2}}},\quad t>0$ (3.23)

with some $c>0$ [6], we get the following asymptotic upper bound

$P\left(\|\breve{A}\|\geq 2+\delta\right)\leq
P\left(\left|\|\breve{A}\|-{\mathbb{E}}\|\breve{A}\|\right|\geq\delta-{C\over\sqrt{\chi_{n}}}\right)\leq{2\over
n^{c\chi_{n}(\delta/2)^{2}}}.$ (3.24)

It follows from (3.22) that

$\bar{\Upsilon}_{\delta}=\\{\lambda_{\max}(\breve{A})>2+\delta\\}\subseteq\\{\lambda_{\max}(\breve{A})-{\mathbb{E}}\lambda_{\max}(\breve{A})>\delta-C/\sqrt{\chi_{n}}\\}.$

Then, using (3.23), we get

$P(\bar{\Upsilon}_{\delta})\leq\left(|\lambda_{\max}(\breve{A})-{\mathbb{E}}\lambda_{\max}(\breve{A})|>\delta-C/\sqrt{\chi_{n}}\right)\leq{2n^{2\delta
cC\sqrt{\chi_{n}}}\over n^{c\chi_{n}\delta^{2}}\cdot n^{cC^{2}}}.$ (3.25)

Relation (3.25) shows that (3.21) is true, as well as (3.20). Then it follows
from (3.17) that

$\sum_{n\geq 1}P\left(R^{(n,\rho_{n})}_{2}\right)<\infty.$ (3.26)

Let us study the subset $R^{(n,\rho)}_{1}$ (3.14). We denote

$\Psi_{\kappa}=\left\\{\lambda_{1}(\tilde{A})\geq\sqrt{\rho}(1-\kappa)\right\\}$
(3.27)

and observe that

$R_{1}^{(n,\rho)}\subseteq(R_{1}^{(n,\rho)}\cap\Psi_{\kappa})\cup\bar{\Psi}_{\kappa}.$
(3.28)

Regarding the subset $R_{1}^{(n,\rho)}\cap\Psi_{\kappa}$, we can repeat the
previous reasoning based on the properties of an ellipsoid and write that

$R_{1}^{(n,\rho)}\cap\Psi_{\kappa}\subseteq\left\\{\min_{1+\varepsilon<r<1/\varepsilon^{\prime}}\
{|\sqrt{\rho}(1-\kappa)-\gamma(r)|^{2}\over
r}\leq\hat{\Delta}_{\max}^{(n,\rho)}\right\\}.$ (3.29)

With the help of the second part of Lemma 4.2, we deduce from (3.29) that

$P(R_{1}^{(n,\rho)}\cap\Psi_{\kappa})\leq
P\left(\hat{\Delta}_{\max}^{(n,\rho)}\geq
F^{(2)}(\sqrt{\rho}(1-\kappa),\varepsilon,\varepsilon^{\prime},\tau)\right),$
(3.30)

where

$F^{(2)}\left(\sqrt{\rho}(1-\kappa),\varepsilon,\varepsilon^{\prime},\tau)\right)=\varepsilon^{\prime}\left((\varepsilon^{\prime})^{2}(1-\tau)-q\varepsilon^{\prime}+1\right)^{2},$

under condition

$1/\varepsilon^{\prime}<{q+\sqrt{q^{2}-4(1-\tau)}\over 2},\quad
q=\sqrt{\rho}(1-\kappa).$ (3.31)

If $\varepsilon^{\prime}=(\sqrt{\rho}(1-h))^{-1}$, and $\kappa<h$ then (3.31)
is verified and

$F^{(2)}\left(\sqrt{\rho}(1-\kappa),\varepsilon,\varepsilon^{\prime},\tau)\right),=\sqrt{\rho}(h-\kappa)^{2}(1+o(1)).$

Substituting this relation into the right-hand side of (3.30), we obtain the
following upper bound,

$P(R_{1}^{(n,\rho)}\cap\Psi_{\kappa})\leq
P\left(\hat{\Delta}_{\max}^{(n,\rho)}\geq\sqrt{\rho}(h-\kappa)^{2}\right).$

It follows from the last estimate and (3.19) that for any $h>\kappa$ we have

$P(R_{1}^{(n,\rho)}\cap\Psi_{\kappa})\leq{1\over
n^{\log(\sqrt{\chi_{n}\rho_{n}}(h-\kappa)^{2}(1+o(1))}}.$

Therefore we can write that

$\sum_{n\geq 1}P(R_{1}^{(n,\rho)}\cap\Psi_{\kappa})<\infty.$ (3.32)

Let us estimate the probability of $\bar{\Psi}_{\kappa}$. The maximal
eigenvalue of the adjacency matrix $A^{(n,\rho_{n})}$ (2.1) of the Erdős-Rényi
random graphs $G(n,p_{n})$ has been studied by Krivelevich and Sudakov [23].
It follows from the results of [23] that with large probability, the maximal
eigenvalue is greater than $(1+o(1))\max\left(\sqrt{D_{\max}},np_{n}\right)$,
where $D_{\max}$ is the maximal vertex degree of the graph
$\Gamma^{(n,\rho_{n})}$, that is

$P\left\\{\omega:\
\lambda_{1}\left(A^{(n,\rho_{n})}(\omega)\right)\geq\max\left(\sqrt{\max_{i=1,\dots,n}b^{(n,\rho_{n})}_{ii}},\rho_{n}\right)(1+o(1))\right\\}\to
1,$

in the limit $(\rho,\chi)_{n}\to\infty$ (2.5). Then we can write that

${\mathbb{E}}\lambda_{1}(\tilde{A}^{(n,\rho_{n})})\geq(1+o(1))\sqrt{\rho_{n}},\quad(\rho,\chi)_{n}\to\infty.$
(3.33)

In paper [27], the following inequality

$P\left(\sup_{\rho_{n}>C\log
n}\left|\lambda_{1}(\tilde{A}^{(n,\rho_{n})})-{\mathbb{E}}\lambda_{1}(\tilde{A}^{(n,\rho_{n})})\right|>{t\over\sqrt{\rho_{n}}}\right)\leq
4e^{-t^{2}/32}$ (3.34)

is proved for all $t>C$. Taking into account that $\rho_{n}=\chi_{n}\log n$
and choosing $t^{2}=s^{2}\rho_{n}$, we deduce from (3.34) that

$P\left(\left|\lambda_{1}(\tilde{A}^{(n,\rho_{n})})-{\mathbb{E}}\lambda_{1}(\tilde{A}^{(n,\rho_{n})})\right|>s\right)\leq{4\over
n^{\chi_{n}\,s^{2}/32}}.$ (3.35)

It follows from (3.33) that

$\bar{\Psi}_{\kappa}\subseteq\left\\{\lambda_{1}(\tilde{A})\leq\sqrt{\rho}(1-\kappa)\right\\}\subseteq\left\\{{\mathbb{E}}\lambda_{1}(\tilde{A})-\lambda_{1}(\tilde{A})\leq\sqrt{\rho}\kappa(1+o(1))\right\\}$

Then (3.35) implies the following upper bound,

$P\left(\bar{\Psi}_{\kappa}\right)\leq
P\left(|{\mathbb{E}}\lambda_{1}(\tilde{A})-\lambda_{1}(\tilde{A})|\geq\sqrt{\rho}\kappa(1+o(1))\right)\leq{4\over
n^{\chi_{n}\rho_{n}\kappa^{2}(1+o(1))/32}}.$

Then clearly

$\sum_{n\geq 1}P(\bar{\Psi}_{\kappa})<\infty$

for any $\kappa>0$. Taking into account this convergence, as well as (3.28),
(3.32) and (3.35), we conclude that

$\sum_{n\geq 1}P\left(R^{(n,\rho_{n})}_{1}\right)<\infty.$

Combining this relation with (3.27) and remembering (3.12), we conclude that
relation (2.10) is true in the case of $i=2$.

###  3.2 Proof of Theorem 2.1 in the case of $i=1$.

We can write in analogy with (3.11) that

$\Phi(v)\subseteq\left\\{\inf_{v\in
D^{(1)}_{\varepsilon,\varepsilon^{\prime}}}\
\min_{i=1,\dots,n}{|\lambda_{i}(\tilde{A})-\gamma^{(n,\rho)}(v)|^{2}\over|v|}\leq\hat{\Delta}_{\max}^{(n,\rho)}\right\\}=S^{(n,\rho)}(\varepsilon,\varepsilon^{\prime}).$
(3.36)

We introduce the subsets $S^{(n,\rho)}_{1}$ and $S^{(n,\rho)}_{2}$ similarly
to (3.14) and (3.15), where the minimum $M^{(2)}_{r}$ is replaced by
$M^{(1)}_{r}=\inf_{\varepsilon^{\prime}<r<1-\varepsilon}$. Then we can write
that

$S_{2}^{(n,\rho)}\cap\Upsilon_{\delta}\subseteq\left\\{M_{r}^{(1)}\,M_{\varphi}{|\lambda_{\max}(\breve{A})-\gamma(re^{i\varphi})|^{2}\over
r}I_{\Upsilon_{\delta}}\leq\hat{\Delta}_{\max}^{(n,\rho)}\right\\},$

and therefore

$P(S^{(n,\rho)}_{2}\cap\Upsilon_{\delta})\leq
P(\hat{\Delta}_{\max}^{(n,\rho)}\geq
G^{(1)}(2+\delta,\varepsilon,\varepsilon^{\prime},\tau)).$ (3.37)

Relation (4.19) shows that
$G^{(1)}(2+\delta,\varepsilon,\varepsilon^{\prime},\tau)=\varepsilon^{4}(1+o(1))$
as $\varepsilon\to 0$ and then

$\sum_{n=1}^{\infty}P(S_{2}^{(n,\rho)}\cap\Upsilon_{\delta})<\infty$ (3.38)

with the same choice of $\varepsilon_{n}=2(\chi_{n})^{-1/8}$ (2.9) and
$\delta_{n}=(\chi_{n})^{-3/8}$ as in the previous subsection.

Let us study $S_{1}^{(n,\rho)}$. Repeating the arguments of the previous
subsection, we can write that

$S_{1}^{(n,\rho)}\cap\Psi_{\kappa}\subseteq\left\\{\min_{\varepsilon^{\prime}<r<1-\varepsilon}\
{|\sqrt{\rho}(1-\kappa)-\gamma(r)|^{2}\over
r}\leq\hat{\Delta}_{\max}^{(n,\rho)}\right\\}$

and by Lemma 4.3, we have

$P(S_{1}^{(n,\rho)}\cap\Psi_{\kappa})\leq
P\left(\hat{\Delta}_{\max}^{(n,\rho)}\geq
G^{(2)}(\sqrt{\rho}(1-\kappa),\varepsilon,\varepsilon^{\prime},\tau)\right),$
(3.39)

Choosing $1/\varepsilon^{\prime}=\sqrt{\rho}(1-h)$, obtain we obtain with the
help of (4.20) an upper estimate

$P(S_{1}^{(n,\rho)}\cap\Psi_{\kappa})\leq
P\left(\hat{\Delta}_{\max}^{(n,\rho)}\geq\rho^{3/2}(1-h)(h-\kappa)^{2}\right).$

Then (3.19) implies convergence

$\sum_{n\geq 1}P(S_{1}^{(n,\rho)}\cap\Psi_{\kappa})<\infty.$ (3.40)

The upper bounds for the probabilities $P(\bar{\Upsilon}_{\delta})$ and
$P(\bar{\Psi}_{\kappa})$ in the case of $i=1$ are the same as in the case of
$i=2$. Relations (3.38), (3.40) together with (3.21) and (3.35) show that
convergence (2.10) is true in the case of $i=1$. Theorem 2.1 is proved.

###  3.3 The case of real $v$.

Regarding the particular case $v\in\mathbb{R}$, we can use the following
inequalities instead of (3.6),

$|\lambda_{i}(H^{(n,\rho)}(v))-\lambda_{i}(\tilde{A}^{(n,\rho)}-\gamma^{(n,\rho)}(v)I)|\leq|v|\,\hat{\Delta}^{(n,\rho)}_{\max},\quad
i=1,\dots,n,$ (3.41)

where eigenvalues of $H^{(n,\rho)}$ and $\tilde{A}^{(n,\rho)}$ are ordered in,
say, decreasing order. Relation (3.41) is a corollary of more precise Weyl’s
inequality for hermitian matrices (see e.g. [17]). Using (3.41), we can write
that

$\left\\{\omega:\det(H(v))=0\right\\}=\cup_{i=1}^{n}\left\\{\omega:\lambda_{i}(H(v))=0\right\\}$

and

$\left\\{\omega:\lambda_{i}(H(v))=0\right\\}\subseteq\left\\{{|\lambda_{i}(\tilde{A})-\gamma(v)|\over|v|}\leq\hat{\Delta}^{(n,\rho)}_{\max}\right\\}.$

Then, in complete analogy with (3.2), (3.11) and (3.12), we get inclusions

$\hat{\Phi}^{(2)}_{n,\rho}(\hat{\varepsilon},\varepsilon^{\prime})=\cup_{1+\hat{\varepsilon}<v<1/\varepsilon^{\prime}}\left\\{\omega:\det(H(v))=0\right\\}\subseteq\hat{R}^{(n,\rho)}_{1}\cup
R^{(n,\rho)}_{2},$

where

$\hat{R}_{1}^{(n,\rho)}=\left\\{M_{v}^{(2)}{|\lambda_{1}(\tilde{A})-\gamma(v)|\over|v|}\leq\hat{\Delta}^{(n,\rho)}_{\max}\right\\}$

and

$\hat{R}_{2}^{(n,\rho)}=\left\\{M_{v}^{(2)}\min_{i=2,\dots,n}{|\lambda_{i}(\tilde{A})-\gamma(v)|\over|v|}\leq\hat{\Delta}^{(n,\rho)}_{\max}\right\\}$

with $M_{v}^{(2)}=\min_{1+\hat{\varepsilon}<v<1/\varepsilon^{\prime}}$.
Regarding the last event, we can repeat all computations of the previous
subsection with $F^{(1)}(2+\delta,\varepsilon,\varepsilon^{\prime},\tau)$
replaced by

$\hat{F}^{(1)}(2+\delta,\hat{\varepsilon},\varepsilon^{\prime},\tau)={\varepsilon^{2}-\delta(1+\varepsilon)-\tau(1+\varepsilon)^{2}\over(1+\varepsilon)^{3}}=O(\hat{\varepsilon}^{2}),\quad\hat{\varepsilon}\to
0,$

in the asymptotic regime when $\delta=\hat{\varepsilon}^{2}/h$ with
sufficiently large $h$. In this case relations (3.18) and (3.19) take the form

$P(\hat{R}^{(n,\rho)}_{2}\cap\Upsilon_{\delta})\leq
P\left(\hat{\Delta}_{\max}^{(n,\rho)}\geq\hat{\varepsilon}^{2}\right)\leq{1\over
n^{\log(\hat{\varepsilon}^{2}\sqrt{\chi_{n}}(1+o(1)))}}\ ,\quad n\to\infty.$
(3.42)

It is easy to see that (2.11) is sufficient for the convergence of the series
(3.42),

$\sum_{n\geq
1}P\left(\hat{R}^{(n,\rho_{n})}_{2}\cap\Upsilon_{\delta_{n}}\right)<\infty,\quad\delta_{n}=\hat{\varepsilon}_{n}^{2}/h.$
(3.43)

It follows from the upper bound (3.25) that to have the series of
$P(\bar{\Upsilon}_{\delta_{n}})$ convergent, we need to make the value
$\chi_{n}\delta_{n}^{2}$ sufficiently large. This observation together with
the last condition of (3.43) shows that the rate (2.11) is close to the
optimal one from the technical point of view.

##  4 Auxiliary results and statements

###  4.1 Proof of Lemma 1.1 by Stark and Terras

We reproduce here the proof of Lemma 1.1 given by Stark and Terras [30]. It is
based on the observation that for finite $(q+1)$-regular graph relation (1.3)
takes the form

$\left(Z_{X^{(q+1)}}(u)\right)^{-1}=(1-u^{2})^{r-1}\prod_{j=1}^{n}\left(1-u\lambda_{j}+qu^{2}\right),$
(4.1)

where $\lambda_{1}\leq\dots\leq\lambda_{n}$ are eigenvalues of $A$. Then the
poles of $Z_{X^{(q+1)}}(u)$ are given by zeros of quadratic polynomials
$1-u\lambda_{j}+qu^{2}$, $1\leq j\leq n$.

One can write

$1-u\lambda_{j}+qu^{2}=(1-\alpha_{j}u)(1-\beta_{j}u)$

with $\alpha_{j}\beta_{j}=q$ and $\alpha_{j}+\beta_{j}=\lambda_{j}$. Then
$\alpha_{j}$ and $\beta_{j}$ are given by the roots of the quadratic equation

$x^{2}-\lambda_{j}x+q=0$

and therefore

$\alpha_{j},\beta_{j}={\lambda_{j}+\sqrt{\lambda_{j}^{2}-4q}\over 2}.$ (4.2)

Thus the values $\alpha_{j}$ and $\beta_{j}$ are complex conjugate if and only
if

$|\lambda_{j}|\leq 2\sqrt{q}.$ (4.3)

and in this case

$|\alpha_{j}|^{2}=|\beta_{j}|^{2}=q.$

The last equalities mean that if $s=\sigma+i\tau$ is such that

$q^{s}=\alpha_{j}\quad{\hbox{or}}\quad q^{s}=\beta_{j},$ (4.4)

then $Re(s)=\sigma=1/2$. If $|\lambda_{j}|=q+1$, then it follows from (4.2)
and (4.3) that $Re(s)=0$ or $1$. Finally, if $|\lambda_{j}|\neq q+1$, then
$|\lambda_{j}|<q+1$ that therefore (4.4) implies inequalities $0<Re(s)<1$.
This argument completes the proof of equivalence between (1.5) and (1.6).

###  4.2 Distance property of ellipsoid.

Let ${{\cal E}}(a,b)$ denote the family of points on ${\mathbb{R}}^{2}$

${\cal E}(a,b)=\left\\{(s,t):s,t\in{\mathbb{R}},\ \left({s\over
a}\right)^{2}+\left({t\over b}\right)^{2}=1\right\\}.$

We assume that $b<a$. Given $x\in[0,a]$, we determine the distance ${\cal
D}(x)$ between the point $(x,0)$ and the ellipse ${\cal E}(a,b)$ by the
formula

${\cal D}(x)^{2}=\min_{(s,t)\in{\cal
E}(a,b)}((s-x)^{2}+t^{2})=\min_{s\in[-a,a]}\phi(x,s),$

where

$\phi(x,s)=(s-x)^{2}+b^{2}-b^{2}{s^{2}/a^{2}}.$

######  Lemma 4.1.

There exists a critical point $x_{0}=a(1-b^{2}/a^{2})$ such that

${\cal D}(x)^{2}=\begin{cases}b^{2}\left(1-{\displaystyle
x^{2}\over\displaystyle a^{2}-b^{2}}\right),&\text{if $0\leq x\leq x_{0}$},\\\
(a-x)^{2},&\text{if $x_{0}\leq x\leq a$ }\end{cases}$ (4.5)

  * Proof.The proof of Lemma 4.1 is based on the elementary analysis of the derivative

${\partial\over\partial s}\phi(x,s)=2(s-x)-2b^{2}s/a^{2}.$

If $x\in[0,x_{0}]$, then this derivative equals to zero at the point
$\tilde{s}=\tilde{s}(x)=x/(1-b^{2}/a^{2})$ and

${\cal D}(x)^{2}=\phi(x,\tilde{s}(x)).$

If $x\in[x_{0},a]$, then the derivative $\phi_{s}^{\prime}(x,s)$ has no zero
on the interval $s\in[0,a]$ and therefore

${\cal D}(x)^{2}=\phi(x,a)=(a-x)^{2}.$

This means that if $x<x_{0}$, then the corresponding point
$\tilde{l}=(\tilde{s},\tilde{t})$ is such that $\tilde{t}>0$; if $x\geq
x_{0}$, then the point $\tilde{s}$ coincides with the right extremity of the
ellipsoid, $\tilde{s}=a$ for all $x\geq x_{0}$. The derivative of ${\cal
D}(x)^{2}$ is a discontinuous function and that the distance ${\cal D}(x)^{2}$
shows a kind of ”phase transition” of the first order at $x=x_{0}$. ∎

Let us point out that the distance ${\cal D}(x)$ (5.5) is a decreasing
function for all $x\in[0,a]$ and for any $s\in[0,a]$,

$\min_{x\in[0,s]}{\cal D}(x)={\cal D}(s).$ (4.6)

Now we turn to the case of $\gamma^{(n,\rho)}(v)$ (3.13). Denoting
$s=Re(\gamma^{(n,\rho)}(v))$ and $t=Im(\gamma^{(n,\rho)}(v))$, we observe that
the family of points

$\dot{\cal E}={\cal
E}(\dot{a},\dot{b})=\left\\{\gamma^{(n,\rho)}(re^{i\varphi}),\quad
0\leq\varphi<2\pi\right\\}$

is given by an ellipsoid with the half-axes

$\dot{a}=r(1-\tau)+{1\over r},\quad\dot{b}=r(1-\tau)-{1\over r}.$

Regarding the difference between $\lambda\in{\mathbb{R}}$ and
$\gamma^{(n,\rho)}$, we see that its absolute value is bounded from below by
the distance (4.5)

$|\lambda-\gamma^{(n,\rho)}|^{2}\geq{\cal D}(\lambda)^{2}$

with $a$ and $b$ replaced by $\dot{a}$ and $\dot{b}$, respectively. Taking
into account that

$\dot{x}_{0}={\dot{a}^{2}-\dot{b}^{2}\over\dot{a}}={4(1-\tau)\over
r(1-\tau)+1/r},$

one can easily see that if

$\varepsilon<{1}\quad{\hbox{and}}\quad\tau<{1},$

then $\dot{x}_{0}<2+\delta$. Therefore we can write a version of (4.6),

$\min_{\lambda\in[0,2+\delta]}\
\min_{\varphi\in[0,2\pi)}|\lambda-\gamma^{(n,\rho)}|^{2}=\left(r(1-\tau)+{1\over
r}-2-\delta\right)^{2}.$ (4.7)

Elementary analysis of the function

$\gamma(x)=x(1-\tau)+{1\over x}$

shows that if

$\varepsilon>{1\over\sqrt{1-\tau}}-1\quad{\hbox{and}}\quad\varepsilon>\varepsilon_{0}={(2\tau+\delta)+\sqrt{4\delta+\delta^{2}+4\tau}\over
2(1-\tau)},$ (4.8)

then

$\inf_{1+\varepsilon<x}\gamma(x)>2+\delta.$ (4.9)

Regarding (4.7), we see that it remains to study the minimal value of the
function

$f(x)={1\over x}{\left(x(1-\tau)+{1\over
x}-q\right)^{2}}={\big{(}x^{2}(1-\tau)-qx+1\big{)}^{2}\over x^{3}}$

over the interval $x\in(1+\varepsilon,1/\varepsilon^{\prime})$ in the case
when $q=2+\delta$. Elementary analysis shows that the derivative
$f^{\prime}(x)$ has four zeroes,

$x_{1,2}={q\mp\sqrt{q^{2}-4(1-\tau)}\over 2(1-\tau)}\quad{\hbox{and}}\quad
x_{3,4}={-q\mp\sqrt{q^{2}+12(1-\tau)}\over 2(1-\tau)},$

such that $x_{3}<0<x_{1}<x_{4}<1$ and

$1<x_{2}={q+\sqrt{q^{2}-4(1-\tau)}\over 2(1-\tau)}.$

We will also need to minimize $f(x)$ in the case when
$q=\sqrt{\rho}(1-\kappa)$.

######  Lemma 4.2.

Let positive $\varepsilon$ and $\varepsilon^{\prime}$ verify inequality
$1+\varepsilon<1/\varepsilon^{\prime}$. If $q$ is greater than $2-\tau$ and
such that $x_{2}<1+\varepsilon$, then

$F^{(1)}(q,\varepsilon,\varepsilon^{\prime},\tau)=\inf_{1+\varepsilon<x<1/\varepsilon^{\prime}}f(x)=f(1+\varepsilon)={\left((1+\varepsilon)^{2}(1-\tau)-q(1+\varepsilon)+1\right)^{2}\over(1+\varepsilon)^{3}}.$
(4.10)

If $q$ is greater than $2+\tau$ and such that $1/\varepsilon^{\prime}<x_{2}$,
then

$F^{(2)}(q,\varepsilon,\varepsilon^{\prime},\tau)=\inf_{1+\varepsilon<x<1/\varepsilon^{\prime}}f(x)=f(1/\varepsilon^{\prime})={1\over\varepsilon^{\prime}}{\left((1-\tau)-q\varepsilon^{\prime}+(\varepsilon^{\prime})^{2}\right)^{2}}.$
(4.11)

  * Proof.Proof of Lemma 4.2 is based on the observation that $f(x)$ has a local minimum at $x_{2}$ and is strictly decreasing on the interval $[1,x_{2})$ and strictly increasing on the interval $(x_{2},+\infty)$. Simple computations show that (4.10) and (4.11) are true. ∎

Regarding our main asymptotic regime when

$\varepsilon,\delta,\tau\to 0,\quad\delta=o(\varepsilon^{2}),\quad{\hbox{and
}}\quad\tau=o(\delta),$ (4.12)

we conclude that condition (4.8) and the conditions of Lemma 4.2 are satisfied
and deduce from (4.10) that asymptotic relation

$F^{(1)}(2+\delta,\varepsilon,\varepsilon^{\prime},\tau)=\varepsilon^{4}(1+o(1)),\quad\varepsilon\to
0$ (4.13)

is true.

Regarding (4.11) in the case when $q=\sqrt{\rho}(1-\kappa)$ and
$1/\varepsilon^{\prime}=\sqrt{\rho}(1-h)$, we conclude that in the limit of
infinite $\rho$, condition $\kappa<h$ is sufficient for inequality
$1/\varepsilon^{\prime}<x_{2}$ to hold asymptotically. Simple computation
shows that in this case

$F^{(2)}(\sqrt{\rho}(1-\kappa),\varepsilon,\varepsilon^{\prime},\tau)=\sqrt{\rho}\,{(h-\kappa)^{2}}(1+o(1)),\quad\rho\to\infty.$
(4.14)

Let us study the minimum of $\gamma(x)$ over the interval
$r\in(\varepsilon^{\prime},1-\varepsilon)$. The first observation is that if

$\varepsilon>{-(2\tau+\delta)+\sqrt{\delta^{2}+4\delta+4\tau}\over
2(1-\tau)},$ (4.15)

then the following analogue of (4.9) is verified,

$\min_{0<x<1-\varepsilon}\gamma(x)>2+\delta.$ (4.16)

######  Lemma 4.3.

Let positive $\varepsilon$ and $\varepsilon^{\prime}$ verify inequality
$\varepsilon^{\prime}<1-\varepsilon$. If $q$ is greater than $2+\tau$ and such
that $1-\varepsilon<x_{1}$, then

$G^{(1)}(q,\varepsilon,\varepsilon^{\prime},\tau)=\inf_{\varepsilon^{\prime}<x<1-\varepsilon}f(x)=f(1-\varepsilon)={\left(\varepsilon^{2}-\delta(1+\varepsilon)-\tau(1+\varepsilon)^{2}\right)^{2}\over(1-\varepsilon)^{3}}.$
(4.17)

If $q$ is such that $x_{1}<\varepsilon^{\prime}$, then

$G^{(2)}(q,\varepsilon,\varepsilon^{\prime},\tau)=\inf_{\varepsilon^{\prime}<x<1-\varepsilon}f(x)=f(\varepsilon^{\prime})={\left((\varepsilon^{\prime})^{2}(1-\tau)-q\varepsilon^{\prime}+1\right)^{2}\over(\varepsilon^{\prime})^{3}}.$
(4.18)

  * Proof.The proof of Lemma 4.3 is based on elementary computations that we do not present here. ∎

Regarding the asymptotic regime (4.12), we see that condition (4.15) and
conditions of Lemma 4.3 are verified. Then we conclude that

$G^{(1)}(2+\delta,\varepsilon,\varepsilon^{\prime},\tau)=\varepsilon^{4}(1+o(1)),\quad\varepsilon\to
0.$ (4.19)

Regarding (4.18) in the case when $q=\sqrt{\rho}(1-\kappa)$ and
$1/\varepsilon^{\prime}=\sqrt{\rho}(1-h)$, we conclude that in the limit of
infinite $\rho$, condition $\kappa<h$ is sufficient for inequality
$\varepsilon^{\prime}>x_{1}$ to hold asymptotically. Then relation

$G^{(2)}\left(\sqrt{\rho}(1-\kappa),\varepsilon,\varepsilon^{\prime},\tau\right)=\rho^{3/2}(1-h)(h-\kappa)^{2}(1+o(1))$
(4.20)

is true in the asymptotic regime (4.12).

###  4.3 Proof of Füredi-Komlós inequalities.

For completeness, we reproduce the proof of inequalities (3.16) resulting from
two lemmas below [15].

######  Lemma 4.4.

If $\tilde{A}=(a_{ij})$ is an $n\times n$ real symmetric matrix, and
$\breve{A}=\tilde{A}-tJ$ (where $J$ is the matrix with all $1$ entries), then

$\lambda_{2}(\tilde{A})\leq\lambda_{1}(\breve{A}).$

  * Proof.Relation $\lambda_{1}(\tilde{A})=\max_{\|{{\mathbf{x}}}\|=1}{\mathbf{x}}\tilde{A}{\mathbf{x}}$ and the Courant-Fischer theorem imply that

$\lambda_{2}(\tilde{A})=\min_{{\mathbf{v}}}\
\max_{({\mathbf{x}},{\mathbf{v}})=0,\,\|{\mathbf{x}}\|=1}{\mathbf{x}}\tilde{A}{\mathbf{x}},$

and therefore

$\lambda_{2}(\tilde{A})\leq\
\max_{({\mathbf{x}},{\mathbf{1}})=0,\,\|{\mathbf{x}}\|=1}{\mathbf{x}}\tilde{A}{\mathbf{x}}=\
\max_{({\mathbf{x}},{\mathbf{1}})=0,\,\|{\mathbf{x}}\|=1}{\mathbf{x}}(\breve{A}+tJ){\mathbf{x}}$
$=\
\max_{({\mathbf{x}},{\mathbf{1}})=0,\,\|{\mathbf{x}}\|=1}{\mathbf{x}}\breve{A}{\mathbf{x}}\leq\lambda_{1}(\breve{A}),$

since $({\mathbf{x}},{\mathbf{1}})=0$ implies $J{\mathbf{x}}={\mathbf{0}}$.
Lemma 4.4 is proved. ∎

######  Lemma 4.5.

If $\tilde{A}=(a_{ij})$ is a real symmetric matrix, and
$\breve{A}=\tilde{A}-tJ$, $t>0$, then

$\lambda_{-\infty}(\tilde{A})\geq\lambda_{-\infty}(\breve{A}).$

  * Proof.For $t>0$ the matrix $tJ$ is positive definite (i.e. ${\mathbf{x}}tJ{\mathbf{x}}\geq 0$ for all ${\mathbf{x}}\in{\mathbf{R}}^{n}$), hence

$\lambda_{-\infty}(\tilde{A})=\min_{\|{\mathbf{x}}\|=1}{\mathbf{x}}\tilde{A}{\mathbf{x}}\geq\min_{\|{\mathbf{x}}\|=1}{\mathbf{x}}\breve{A}{\mathbf{x}}+\min_{\|{\mathbf{x}}\|=1}{\mathbf{x}}tJ{\mathbf{x}}$
$\geq\min_{\|{\mathbf{x}}\|=1}{\mathbf{x}}\breve{A}{\mathbf{x}}=\lambda_{-\infty}(\breve{A}).$

Lemma 4.5 is proved. ∎

### Acknowledgments.

The author would like to thank the anonymous referee for valuable remarks and
discussion that helped me much to improve the paper.

## References

  * [1] N. Alon, Eigenvalues and expanders, Combinatorica 6 (1986), 83–96.
  * [2] H. Bass, The Ihara-Selberg zeta function of a tree lattice, Internat. J. Math. 3 (1992), 717–797.
  * [3] F. Benaych-Georges, C. Bordenave, and A. Knowles, Spectral radii of sparse random matrices, Ann. Inst. Henri Poincaré Probab. Stat. 56 (2020), no. 3, 2141–2161.
  * [4] B. Bollobaś, Random graphs, 2nd edition, Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 2001.
  * [5] C. Bordenave, M. Lelarge, L. Massoulié, Nonbacktracking spectrum of random graphs: community detection and nonregular ramanujan graphs, Ann. Probab.  46 (2018), 1–71.
  * [6] S. Boucheron, G. Lugosi and P. Massart, Concentration inequalities: a nonasymptotic theory of independence, Oxford University Press, Oxford, 2013.
  * [7] D. Chafai, Singular values of random matrices, available from: https://djalil.chafai.net/docs/sing.pdf
  * [8] F.R.K. Chung, Diameters and eigenvalues, Journal of the American. Math. Society, 2 (1989), 187–196.
  * [9] S. Coste and Y. Zhu, Eigenvalues of the non-backtracking operator detached from the bulk, preprint https://arxiv.org/abs/1907.05603, Random Matrices Theory Appl.  10 (2021), no. 3, Paper No. 2150028, 21 pp.
  * [10] P. Erdős and A. Rényi, On random graphs. I, Publ. Math. Debrecen 6 (1959), 290–297.
  * [11] D. Foata and D. Zeilberger, A combinatorial proof of Bass’s evaluations of the Ihara-Selberg zeta function for graphs, Transactions AMS 351 (1999), 2257–2274.
  * [12] J. Friedman, On the second eigenvalue and random walks in random $d$-regular graphs, Combinatorica 11 (1991), 331-362.
  * [13] J. Friedman (Ed.), Expanding graphs, DIMACS Series on Discrete Math. and Theor. Comput. Sci., Vol. 10, Amer. Math. Soc., Providence, RI, 1993.
  * [14] J. Friedman, A proof of Alon’s second eigenvalue conjecture and related problems, Mem. Amer. Math. Soc. 195 (2008)
  * [15] Z. Füredi and J. Komlós, The eigenvalues of random symmetric matrices, Combinatorica 1 (1981), 233–241.
  * [16] K. Hashimoto, Zeta functions of finite graphs and representation of $p$-adic groups, Advanced Studies in Pure Mathematics 15 (1989) Automorphic Forms and Geometry of Arithmetic Varieties, pp. 211–280.
  * [17] R. A. Horn and C. R. Johnson, Matrix analysis, Cambridge University Press, 1985.
  * [18] M. D. Horton, H. M. Stark and A. A. Terras, What are zeta functions of graphs and what are they good for? Contemporary Mathematics, Quantum Graphs and Their Applications, (2006) 173–190.
  * [19] Y. Ihara, On discrete subgroups of the two by two projective linear group over $\mathfrak{p}$-adic fields, J. Math. Soc. Japan 18 (1966) 219–235.
  * [20] O. Khorunzhiy, On eigenvalue distribution of random matrices of Ihara zeta function of large random graphs, J. Mathem. Physics, Analysis, Geom. 13 (2017), 268–282.
  * [21] O. Khorunzhiy, Limiting eigenvalue distribution of random matrices of Ihara zeta function of long-range percolation graphs, Random Matrices Theory Appl. 7 (2018), no. 3, 1850007, 32 pp.
  * [22] O. Khorunzhiy, On asymptotic properties of Bell polynomials and concentration of vertex degree of large random graphs, J. Theor. Probab. (2020), available at https://doi.org/10.1007/s10959-020-01025-w
  * [23] M. Krivelevich and B. Sudakov, The largest eigenvalue of sparse random graphs, Combin. Probab. Comput. 12 (2003), 61–72.
  * [24] D. Lenz, F. Pogorzhelski, and M. Schmidt, The Ihara zeta function for infinite graphs, Trans. Amer. Math. Soc. 371 (2019), 5668–5729.
  * [25] A. Lubotzky, R. Phillips and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), 261–277.
  * [26] A. Lubotzky, Cayley graphs: eigenvalues, expanders and random walks, Surveys in combinatorics, London Math. Soc. Lecture Notes 18 (1995), 155–189.
  * [27] G. Lugosi, S. Mendelson and N. Zhivotovsky, Concentration of the spectral norm of Erdős-Rényi random graphs, Bernoulli, 26 (2020), 2253–2274.
  * [28] M. Ram Murty, Ramanujan graphs, J. Ramanujan Math. Soc. 18 (2003), 1–20.
  * [29] G. Quenell, Spectral diameter estimates for $k$-regular graphs, Advances in Math. 106 (1994) 122–148.
  * [30] H. M. Stark and A. A. Terras, Zeta Functions of Finite Graphs and Coverings, Adv. Math. 121 (1996), 124–165.
  * [31] T. Tao, Eigenvalues and sums of Hermitian matrices, available at: https://terrytao.wordpress.com/tag/weyl-inequalities/, 254A, Notes 3a
  * [32] A. Terras, Zeta functions of graphs: a stroll through the garden, Cambridge Studies in Advanced Mathematics, 128 Cambridge University Press Cambridge (2011).
  * [33] K. Wang and Ph. M. Wood, Limiting empirical spectral distribution for the non-backtracking matrix of an Erdős-Rényi graph, preprint, https://arxiv.org/abs/1710.11015