# Asymptotic Absence of Poles of Ihara Zeta Function of Large Erdős–Rényi Random Graphs

Oleksiy Khorunzhiy

► To cite this version:

Oleksiy Khorunzhiy. Asymptotic Absence of Poles of Ihara Zeta Function of Large Erdős–Rényi Random Graphs. Journal of Mathematical Physics, Analysis, Geometry, 2022, 18 (3), pp.382-405. 10.15407/mag18.03.382 . hal-04477175

HAL Id: hal-04477175

https://cnrs.hal.science/hal-04477175

Submitted on 4 Jun 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Asymptotic Absence of Poles of Ihara Zeta Function of Large Erdős–Rényi Random Graphs

Oleksiy Khorunzhiy

► To cite this version:

Oleksiy Khorunzhiy. Asymptotic Absence of Poles of Ihara Zeta Function of Large Erdős–Rényi Random Graphs. Journal of Mathematical Physics, Analysis, Geometry, 2022, 18 (3), pp.382-405. 10.15407/mag18.03.382 . hal-04477175

HAL Id: hal-04477175

https://cnrs.hal.science/hal-04477175v1

Submitted on 4 Jun 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Journal of Mathematical Physics, Analysis, Geometry
20XX, Vol. X, No. X, pp. 1–??
doi:

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

Oleksiy Khorunzhiy

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

## 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]} (1 - u^{\nu(C)})^{-1}, \qquad (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 (I + u^2(B - I) - uA), \quad u \in \mathbb{C}, \qquad (1.2)$$

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

$$r - 1 = \text{Tr}(B - 2I)/2. \qquad (1.3)$$
Journal of Mathematical Physics, Analysis, Geometry
20XX, Vol. X, No. X, pp. 1–??
doi:

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

Oleksiy Khorunzhiy

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

## 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]} (1 - u^{\nu(C)})^{-1}, \qquad (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 (I + u^2(B - I) - uA), \quad u \in \mathbb{C}, \qquad (1.2)$$

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

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

<footnote>© Oleksiy Khorunzhiy, 20XX</footnote>
Let us note that the Ihara zeta function can also be determined as the exponential expression [32],

$$Z_{\Gamma}(u) = \exp \left\{ \sum_{k \ge 1} \frac{N_k}{k} u^k \right\}, \qquad (1.4)$$

where $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

$$\mathrm{Re} s \in (0,1) \text{ and } (Z_{X^{(q+1)}}(q^{-s}))^{-1} = 0 \quad \text{imply} \quad \mathrm{Re} s = \frac{1}{2}. \qquad (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 \quad \text{implies} \quad |\lambda| \le 2\sqrt{q}. \qquad (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} : \frac{1}{\sqrt{q}} < |z| < \sqrt{q} \right\}, \qquad (1.7)$$

the following statement

$$(Z_{X^{(q+1)}}\left(\frac{v}{\sqrt{q}}\right))^{-1} = 0 \quad \text{implies} \quad |v| = 1 \qquad (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(\frac{v}{\sqrt{q}}\right) \qquad (1.9)$$
Let us note that the Ihara zeta function can also be determined as the exponential expression [32],

$$Z_{\Gamma}(u) = \exp \left\{ \sum_{k \ge 1} \frac{N_k}{k} u^k \right\}, \qquad (1.4)$$

where $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

$$\mathrm{Re} s \in (0,1) \text{ and } (Z_{X^{(q+1)}}(q^{-s}))^{-1} = 0 \quad \text{imply} \quad \mathrm{Re} s = \frac{1}{2}. \qquad (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 \quad \text{implies} \quad |\lambda| \le 2\sqrt{q}. \qquad (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} : \frac{1}{\sqrt{q}} < |z| < \sqrt{q} \right\}, \qquad (1.7)$$

the following statement

$$(Z_{X^{(q+1)}}\left(\frac{v}{\sqrt{q}}\right))^{-1} = 0 \quad \text{implies} \quad |v| = 1 \qquad (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(\frac{v}{\sqrt{q}}\right) \qquad (1.9)$$
has no poles in the region $v \in D_1^{(q)} \cup D_2^{(q)}$, where

$$D_1^{(q)} = \{v \in \mathbb{C} : 1/\sqrt{q} < |v| < 1\} \quad \text{and} \quad D_2^{(q)} = \{v \in \mathbb{C} : 1 < |v| < \sqrt{q}\}. \quad (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, 28, 29]. 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 Erdő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/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), \quad (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 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
has no poles in the region $v \in D_1^{(q)} \cup D_2^{(q)}$, where

$$D_1^{(q)} = \{v \in \mathbb{C} : 1/\sqrt{q} < |v| < 1\} \quad \text{and} \quad D_2^{(q)} = \{v \in \mathbb{C} : 1 < |v| < \sqrt{q}\}. \quad (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, 28, 29]. 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 Erdő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/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}), \quad (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 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_Γ} \sim α$ and all other eigenvalues $λ$ of $W_Γ$ verify $|λ| \le \sqrt{α} + 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, α/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_Γ$.

The limiting eigenvalue distribution of non-backtracking matrices $W_Γ$ 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_Γ$ such as the presence of isolated eigenvalues inside and outside of the bulk of the spectrum of $W_Γ$ have been considered in [9] for a generalization of the Erdős-Rényi random graphs $G(n, α/n)$ in the case when $α/\log n \to \infty$ as $n \to \infty$. It is shown, in particular, that with probability $1-o(1)$ all eigenvalues of $W_Γ$ are located on the distance $o(\sqrt{α})$ of a circle of radius $\sqrt{α-1}$ excepting two ones that are close to 1 and $α$ as $n \to \infty$. Since eigenvalues of $W_Γ$ determine uniquely the poles of $Z_Γ(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_Γ$ 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_Γ$ on the base of the knowledge of that of the adjacency matrix $A_Γ$ (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_Γ$. 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_Γ$ [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_Γ(v/\sqrt{ρ_n})$ of the Erdős-Rényi random graphs $G(n, ρ_n/n)$ in the asymptotic regime when $ρ_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 \ge 1}$ satisfies, in the limit $n \to \infty$, $np_n/\log n \to \infty$, a version of the graph theory Riemann hypothesis.
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_Γ} \sim \alpha$ and all other eigenvalues $\lambda$ of $W_Γ$ verify $|\lambda| \le \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_Γ$.

The limiting eigenvalue distribution of non-backtracking matrices $W_Γ$ of Erdős-Rényi random graphs $G(n, p)$ have been also studied in the asymptotic regimes when either $p \approx \text{Const}$ or $p = o(1)$ as $n \to \infty$ [33]. More fine spectral characteristics of $W_Γ$ such as the presence of isolated eigenvalues inside and outside of the bulk of the spectrum of $W_Γ$ 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_Γ$ 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_Γ$ determine uniquely the poles of $Z_Γ(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_Γ$ 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_Γ$ on the base of the knowledge of that of the adjacency matrix $A_Γ$ (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_Γ$. 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_Γ$ [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_Γ(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 \ge 1}$ satisfies, 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

$$ \mathcal{A}_{n,\rho} = \{a_{ij}^{(n,\rho)}, 1 \le i < j \le 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}, \quad 0 < \rho < n. $$

We assume that the family $\mathcal{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 $\mathcal{A}_{n,\rho}$.

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

$$ (A^{(n,\rho)})_{ij} = \begin{cases} a_{ij}^{(n,\rho)}, & \text{if } i < j, \\ a_{ji}^{(n,\rho)}, & \text{if } i > j, \\ 0, & \text{if } i = j, \end{cases} \quad i, j \in \{1, \dots, n\} \quad (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) and 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 (I + u^2(B^{(n,\rho)} - I) - uA^{(n,\rho)}) = (Z_{\Gamma^{(n,\rho)}}(u))^{-1}, \quad u \in \mathbb{C}, \quad (2.2) $$

where

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

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

$$ r = \frac{1}{2} \sum_{i,j=1}^{n} a_{ij}^{(n,\rho)} - n + 1. \quad (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. \quad (2.5) $$
## 2. Ihara zeta function of Erdős-Rényi random graphs

Let us consider a family of jointly independent random variables

$$ \mathcal{A}_{n,\rho} = \{a_{ij}^{(n,\rho)}, 1 \le i < j \le 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}, \quad 0 < \rho < n. $$

We assume that the family $\mathcal{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 $\mathcal{A}_{n,\rho}$.

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

$$ (A^{(n,\rho)})_{ij} = \begin{cases} a_{ij}^{(n,\rho)}, & \text{if } i < j, \\ a_{ji}^{(n,\rho)}, & \text{if } i > j, \\ 0, & \text{if } i = j, \end{cases} \quad i, j \in \{1, \dots, n\} \quad (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) and 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 (I + u^2(B^{(n,\rho)} - I) - uA^{(n,\rho)}) = (Z_{\Gamma^{(n,\rho)}}(u))^{-1}, \quad u \in \mathbb{C}, \quad (2.2) $$

where

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

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

$$ r = \frac{1}{2} \sum_{i,j=1}^{n} a_{ij}^{(n,\rho)} - n + 1. \quad (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. \quad (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 \ge 1}$ is determined and $\rho_n$ is given by relation

$$ \rho_n = \chi_n \log n, \quad n \ge 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(\frac{v}{\sqrt{\rho}}\right), \quad \omega \in \Omega_{n,\rho_n}, \quad v \in \mathbb{C}, $$

where

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

where

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

Our main result is given by the following statement.

**Theorem 2.1.** Let $D_{\varepsilon, \varepsilon'}$ with $\varepsilon, \varepsilon' > 0$ be a union of two complex domains

$$ D_{\varepsilon, \varepsilon'}^{(1)} = \{z \in \mathbb{C} : \varepsilon' < |z| < 1 - \varepsilon\} \quad \text{and} \quad D_{\varepsilon, \varepsilon'}^{(2)} = \{z \in \mathbb{C} : 1 + \varepsilon < |z| < 1/\varepsilon'\}. \quad (2.7) $$

We consider two subsets $\Phi_{n,\rho}^{(1)}(\varepsilon, \varepsilon')$ and $\Phi_{n,\rho}^{(2)}(\varepsilon, \varepsilon')$ determined by relation

$$ \Phi_{n,\rho}^{(i)}(\varepsilon, \varepsilon') = \left\{ \omega \in \Omega : \text{there exists } v \in D_{\varepsilon,\varepsilon'}^{(i)} \text{ such that } \left(\tilde{Z}^{(n,\rho)}(v,\omega)\right)^{-1} = 0 \right\}, \quad (2.8) $$

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

$$ \varepsilon_n = \frac{2}{(\chi_n)^{1/8}} \quad \text{and} \quad \varepsilon'_n = \frac{1}{\sqrt{\rho_n(1-\kappa)}}, \quad \kappa > 0, \quad (2.9) $$

the following series of probabilities converge,

$$ \sum_{n \ge 1} P_{n, \rho_n} \left( \Phi_{n, \rho_n}^{(i)} (\varepsilon_n, \varepsilon'_n) \right) < \infty, \quad i = 1, 2 \quad (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_{\varepsilon, \varepsilon'}^{(i)}$ (2.7) real intervals

$$ I_{\hat{\varepsilon}, \varepsilon'}^{(1)} = \{v \in \mathbb{R} : \varepsilon' < v < 1 - \hat{\varepsilon}\} \quad \text{and} \quad I_{\hat{\varepsilon}, \varepsilon'}^{(2)} = \{v \in \mathbb{R} : 1 + \hat{\varepsilon} < v < 1/\varepsilon'\}, $$
We denote this limiting transition by $(\rho, \chi)_n \to \infty$. Writing (2.5), we assume that an infinite sequence $(\chi_n)_{n \ge 1}$ is determined and $\rho_n$ is given by relation

$$ \rho_n = \chi_n \log n, \quad n \ge 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(\frac{v}{\sqrt{\rho}}\right), \quad \omega \in \Omega_{n,\rho_n}, \quad v \in \mathbb{C}, $$

where

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

where

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

Our main result is given by the following statement.

**Theorem 2.1.** Let $D_{\varepsilon, \varepsilon'}$ with $\varepsilon, \varepsilon' > 0$ be a union of two complex domains

$$ D_{\varepsilon, \varepsilon'}^{(1)} = \{z \in \mathbb{C} : \varepsilon' < |z| < 1 - \varepsilon\} \quad \text{and} \quad D_{\varepsilon, \varepsilon'}^{(2)} = \{z \in \mathbb{C} : 1 + \varepsilon < |z| < 1/\varepsilon'\}. \quad (2.7) $$

We consider two subsets $\Phi_{n,\rho}^{(1)}(\varepsilon, \varepsilon')$ and $\Phi_{n,\rho}^{(2)}(\varepsilon, \varepsilon')$ determined by relation

$$ \Phi_{n,\rho}^{(i)}(\varepsilon, \varepsilon') = \left\{ \omega \in \Omega : \text{there exists } v \in D_{\varepsilon,\varepsilon'}^{(i)} \text{ such that } \left(\tilde{Z}^{(n,\rho)}(v,\omega)\right)^{-1} = 0 \right\}, \quad (2.8) $$

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

$$ \varepsilon_n = \frac{2}{(\chi_n)^{1/8}} \quad \text{and} \quad \varepsilon'_n = \frac{1}{\sqrt{\rho_n(1-\kappa)}}, \quad \kappa > 0, \quad (2.9) $$

the following series of probabilities converge,

$$ \sum_{n \ge 1} P_{n, \rho_n} \left( \Phi_{n, \rho_n}^{(i)} (\varepsilon_n, \varepsilon'_n) \right) < \infty, \quad i = 1, 2 \quad (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_{\varepsilon, \varepsilon'}^{(i)}$ (2.7) real intervals

$$ I_{\hat{\varepsilon}, \varepsilon'}^{(1)} = \{v \in \mathbb{R} : \varepsilon' < v < 1 - \hat{\varepsilon}\} \quad \text{and} \quad I_{\hat{\varepsilon}, \varepsilon'}^{(2)} = \{v \in \mathbb{R} : 1 + \hat{\varepsilon} < v < 1/\varepsilon'\}, $$
where $\epsilon' = \epsilon'_n$ is given by (2.9) and

$$ \hat{\epsilon}_n = \frac{\hat{h}}{(\chi_n)^{1/4}} \qquad (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 \ge 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, \qquad (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 \ge 1} P_{n, \rho_n} \left( \left\{ \omega : \left( Z_{\Gamma^{(n, \rho_n)}} \left( \frac{v}{\sqrt{\rho_n}} \right) \right)^{-1} = 0 \right\} \right) = +\infty \quad \text{implies} \quad |v| = 1. \qquad (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 \ne \rho$, then the function $Z_{\Gamma^{(n, \rho)}}$ has a pole at $v$ if and only if

$$ v \left( 1 - \frac{1}{\rho} \right) + v - \lambda_j \left( \frac{1}{\sqrt{\rho}} A + v \left( \frac{1}{\rho} B - I \right) \right) = 0 \qquad (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

$$ \| \frac{1}{\rho} B - I \| = o(1), \qquad (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
where $\varepsilon' = \varepsilon'_n$ is given by (2.9) and

$$ \hat{\varepsilon}_n = \frac{\hat{h}}{(\chi_n)^{1/4}} \qquad (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 \ge 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, \qquad (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 \ge 1} P_{n, \rho_n} \left( \left\{ \omega : \left( Z_{\Gamma^{(n, \rho_n)}} \left( \frac{v}{\sqrt{\rho_n}} \right) \right)^{-1} = 0 \right\} \right) = +\infty \quad \text{implies} \quad |v| = 1. \qquad (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 \ne \rho$, then the function $Z_{\Gamma^{(n, \rho)}}$ has a pole at $v$ if and only if

$$ v \left( 1 - \frac{1}{\rho} \right) + v - \lambda_j \left( \frac{1}{\sqrt{\rho}} A + v \left( \frac{1}{\rho} B - I \right) \right) = 0 \qquad (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

$$ \| \frac{1}{\rho} B - I \| = o(1), \qquad (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

$$ \frac{1}{v} + v - \lambda_j(\tilde{A}) = 0 \qquad (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

$$ \mathcal{E}_r = \left\{ w(z) = z + \frac{1}{z}, \ z = r e^{i\varphi}, \ 0 \le \varphi < 2\pi \right\} \qquad (2.17) $$

and the distance between the points of real axis and $\mathcal{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 \le i \le n} \left| \frac{1}{\rho} (B^{(n, \rho)})_{ii} - 1 \right| = o(1), \quad n, \rho \to \infty \qquad (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)}, \qquad (3.1) $$

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

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

and

$$ (\tilde{A}^{(n, \rho)})_{ij} = \frac{1}{\sqrt{\rho}} a_{ij}^{(n, \rho)}, \quad i, j \in \{1, \dots, n\}. $$
vanishing term $-1/\rho$ in the first braces of (2.14), one could say that (2.14) is equivalent to the condition that

$$ \frac{1}{v} + v - \lambda_j(\tilde{A}) = 0 \qquad (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

$$ \mathcal{E}_r = \left\{ w(z) = z + \frac{1}{z}, \ z = r e^{i\varphi}, \ 0 \le \varphi < 2\pi \right\} \qquad (2.17) $$

and the distance between the points of real axis and $\mathcal{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 \le i \le n} \left| \frac{1}{\rho} (B^{(n, \rho)})_{ii} - 1 \right| = o(1), \quad n, \rho \to \infty \qquad (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)}, \qquad (3.1) $$

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

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

and

$$ (\tilde{A}^{(n, \rho)})_{ij} = \frac{1}{\sqrt{\rho}} a_{ij}^{(n, \rho)}, \quad i, j \in \{1, \dots, n\}. $$
We have also denoted

$$ \gamma^{(n, \rho_n)}(v) = \frac{1 - v^2 / \rho}{v} + \frac{v(n-1)}{n} = v + \frac{1}{v} - v \left( \frac{1}{n} + \frac{1}{\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\}, \quad (3.2) $$

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

$$ \Phi_{n,\rho}^{(i)}(\varepsilon_n, \varepsilon'_n) = \cup_{v \in D_{\varepsilon_n, \varepsilon'_n}^{(i)}} \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)) \le \sigma_2(H(v)) \le \dots \le \sigma_n(H(v)). \quad (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 \quad (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

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

and therefore

$$ H^*(v) = H(\bar{v}) \quad \text{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. $$
We have also denoted

$$ \gamma^{(n, \rho_n)}(v) = \frac{1 - v^2 / \rho}{v} + \frac{v(n-1)}{n} = v + \frac{1}{v} - v \left( \frac{1}{n} + \frac{1}{\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\}, \qquad (3.2) $$

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

$$ \Phi_{n,\rho}^{(i)}(\varepsilon_n, \varepsilon'_n) = \cup_{v \in D_{\varepsilon_n, \varepsilon'_n}^{(i)}} \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)) \le \sigma_2(H(v)) \le \dots \le \sigma_n(H(v)). \qquad (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 \qquad (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

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

and therefore

$$ H^*(v) = H(\bar{v}) \quad \text{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 \le i \le n$. Lemma 3.1 is proved. $\square$

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], Exercise 22),

$$|\sigma_i(X + Y) - \sigma_i(X)| \le \|Y\|, \quad i = 1, \dots, n, \qquad (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)| \le \|v\hat{B}\| = |v| \max_{i=1,\dots,n} |\hat{\Delta}_i^{(n,\rho)}|, \quad i = 1, \dots, n, \qquad (3.6)$$

where

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

We denote

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

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

$$\{\sigma_1(H(v)) = 0\} \subseteq \{\sigma_1(\tilde{A} - \gamma^{(n,\rho)}(v)I) \le |v|\hat{\Delta}_{\max}^{(n,\rho)}\}. \qquad (3.8)$$

Elementary calculation shows that

$$\sigma_i(\tilde{A} - \gamma^{(n,\rho)}(v)I) = \lambda_i((\tilde{A} - \gamma^{(n,\rho)}(v)I)(\tilde{A} - \gamma^{(n,\rho)}(v)I)^*) \\ = \lambda_i((\tilde{A} - \alpha(v)I)^2) + \beta(v)^2, \qquad (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) = (\lambda_i(\tilde{A}) - \alpha(v))^2 + \beta(v)^2 = |\lambda_i(\tilde{A}) - \gamma(v)|^2. \qquad (3.10)$$

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

$$\Phi_{n,\rho}(v) \subseteq \left\{ \min_{i=1,\dots,n} \frac{|\lambda_i(\tilde{A}) - \gamma^{(n,\rho)}(v)|^2}{|v|} \le \hat{\Delta}_{\max}^{(n,\rho)} \right\} \\ \subseteq \left\{ \inf_{v \in D_{\varepsilon, \varepsilon'}^{(2)}} \min_{i=1,\dots,n} \frac{|\lambda_i(\tilde{A}) - \gamma^{(n,\rho)}(v)|^2}{|v|} \le \hat{\Delta}_{\max}^{(n,\rho)} \right\} = R^{(n,\rho)}(\varepsilon, \varepsilon'). \qquad (3.11)$$

Then

$$\Phi_{n,\rho}^{(2)}(\varepsilon, \varepsilon') = \cup_{v \in D_{\varepsilon, \varepsilon'}^{(2)}} \{\sigma_1(H(v)) = 0\} \subseteq R^{(n,\rho)}(\varepsilon, \varepsilon'), \qquad (3.12)$$
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 \le i \le n$. Lemma 3.1 is proved. $\square$

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], Exercise 22),

$$|\sigma_i(X + Y) - \sigma_i(X)| \le \|Y\|, \quad i = 1, \dots, n, \qquad (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)| \le \|v\hat{B}\| = |v| \max_{i=1,\dots,n} |\hat{\Delta}_i^{(n,\rho)}|, \quad i = 1, \dots, n, \qquad (3.6)$$

where

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

We denote

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

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

$$\{\sigma_1(H(v)) = 0\} \subseteq \{\sigma_1(\tilde{A} - \gamma^{(n,\rho)}(v)I) \le |v|\hat{\Delta}_{\max}^{(n,\rho)}\}. \qquad (3.8)$$

Elementary calculation shows that

$$\sigma_i(\tilde{A} - \gamma^{(n,\rho)}(v)I) = \lambda_i((\tilde{A} - \gamma^{(n,\rho)}(v)I)(\tilde{A} - \gamma^{(n,\rho)}(v)I)^*) \\ = \lambda_i((\tilde{A} - \alpha(v)I)^2) + \beta(v)^2, \qquad (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) = (\lambda_i(\tilde{A}) - \alpha(v))^2 + \beta(v)^2 = |\lambda_i(\tilde{A}) - \gamma(v)|^2. \qquad (3.10)$$

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

$$\Phi_{n,\rho}(v) \subseteq \left\{ \min_{i=1,\dots,n} \frac{|\lambda_i(\tilde{A}) - \gamma^{(n,\rho)}(v)|^2}{|v|} \le \hat{\Delta}_{\max}^{(n,\rho)} \right\} \\ \subseteq \left\{ \inf_{v \in D_{\varepsilon, \varepsilon'}^{(2)}} \min_{i=1,\dots,n} \frac{|\lambda_i(\tilde{A}) - \gamma^{(n,\rho)}(v)|^2}{|v|} \le \hat{\Delta}_{\max}^{(n,\rho)} \right\} = R^{(n,\rho)}(\varepsilon, \varepsilon'). \qquad (3.11)$$

Then

$$\Phi_{n,\rho}^{(2)}(\varepsilon, \varepsilon') = \cup_{v \in D_{\varepsilon, \varepsilon'}^{(2)}} \{\sigma_1(H(v)) = 0\} \subseteq R^{(n,\rho)}(\varepsilon, \varepsilon'), \qquad (3.12)$$
where we omitted $\varepsilon$ and $\varepsilon'$ in $\mathbb{R}$. Let us note that the minimums of (3.11) can be taken in arbitrary order, in particular such that

$$ \inf_{v \in D_{\varepsilon, \varepsilon'}^{(2)}} = \inf_{1+\varepsilon < r < 1/\varepsilon'} \inf_{0 \le \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) + \frac{1}{v}, \quad \tau = \frac{1}{n} + \frac{1}{\rho}. \qquad (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

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

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') \subseteq R_1^{(n,\rho)} \cup R_2^{(n,\rho)}, \qquad (3.14) $$

where

$$ R_1^{(n,\rho)} = \left\{ M_r^{(2)} M_\varphi \frac{|\lambda_1(\tilde{A}) - \gamma(re^{i\varphi})|^2}{r} \le \hat{\Delta}_{\max}^{(n,\rho)} \right\} $$

and

$$ R_2^{(n,\rho)} = \left\{ M_r^{(2)} M_\varphi \min_{i=2,\dots,n} \frac{|\lambda_i(\tilde{A}) - \gamma(re^{i\varphi})|^2}{r} \le \hat{\Delta}_{\max}^{(n,\rho)} \right\}. $$

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

$$ \check{A}^{(n,\rho)} = \frac{1 - \delta_{ij}}{\sqrt{\rho}} \left( a_{ij}^{(n,\rho)} - \frac{\rho}{n} \right). \qquad (3.15) $$

It is known [15] that

$$ \lambda_1(\check{A}) \ge \lambda_2(\check{A}) \ge \dots \ge \lambda_n(\check{A}) \ge \lambda_n(\check{A}). \qquad (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} \frac{|\lambda_i(\tilde{A}) - \gamma(re^{i\varphi})|^2}{r} \ge \min_{i=1,\dots,n} \frac{|\lambda_i(\check{A}) - \gamma(re^{i\varphi})|^2}{r}. $$
where we omitted $\varepsilon$ and $\varepsilon'$ in $\mathbb{R}$. Let us note that the minimums of (3.11) can be taken in arbitrary order, in particular such that

$$ \inf_{v \in D_{\varepsilon, \varepsilon'}^{(2)}} = \inf_{1+\varepsilon < r < 1/\varepsilon'} \inf_{0 \le \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) + \frac{1}{v}, \quad \tau = \frac{1}{n} + \frac{1}{\rho}. \qquad (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

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

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') \subseteq R_1^{(n,\rho)} \cup R_2^{(n,\rho)}, \qquad (3.14) $$

where

$$ R_1^{(n,\rho)} = \left\{ M_r^{(2)} M_\varphi \frac{|\lambda_1(\tilde{A}) - \gamma(re^{i\varphi})|^2}{r} \le \hat{\Delta}_{\max}^{(n,\rho)} \right\} $$

and

$$ R_2^{(n,\rho)} = \left\{ M_r^{(2)} M_\varphi \min_{i=2,...,n} \frac{|\lambda_i(\tilde{A}) - \gamma(re^{i\varphi})|^2}{r} \le \hat{\Delta}_{\max}^{(n,\rho)} \right\}. $$

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

$$ \check{A}^{(n,\rho)} = \frac{1 - \delta_{ij}}{\sqrt{\rho}} \left( a_{ij}^{(n,\rho)} - \frac{\rho}{n} \right). \qquad (3.15) $$

It is known [15] that

$$ \lambda_1(\check{A}) \ge \lambda_2(\check{A}) \ge \dots \ge \lambda_n(\check{A}) \ge \lambda_n(\check{A}). \qquad (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,...,n} \frac{|\lambda_i(\tilde{A}) - \gamma(re^{i\varphi})|^2}{r} \ge \min_{i=1,...,n} \frac{|\lambda_i(\check{A}) - \gamma(re^{i\varphi})|^2}{r}. $$
Let us introduce the set

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

Then we can write an obvious inclusion

$$ R_2^{(n,\rho)} \subseteq (R_2^{(n,\rho)} \cap \Upsilon_{\delta}) \cup \bar{\Upsilon}_{\delta}. \qquad (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(\check{A}) - \gamma(re^{i\varphi})|^2 I_{\Upsilon_{\delta}} \ge M_{\varphi}|\lambda_{\max}(\check{A}) - \gamma(re^{i\varphi})|^2 I_{\Upsilon_{\delta}}, $$

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

$$ M_{\varphi}|\lambda_{\max}(\check{A}) - \gamma(re^{i\varphi})|^2 I_{\Upsilon_{\delta}} = |\lambda_{\max}(\check{A}) - \gamma(r)|^2 I_{\Upsilon_{\delta}} \ge |(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')$ is given by the value

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

see Lemma 4.2. Taking into account obvious inclusion,

$$ R_2^{(n,\rho)} \cap \Upsilon_{\delta} \subseteq \left\{ M_r^{(2)} M_{\varphi} \frac{|\lambda_{\max}(\check{A}) - \gamma(re^{i\varphi})|^2}{r} I_{\Upsilon_{\delta}} \le \hat{\Delta}_{\max}^{(n,\rho)} \right\}, $$

we can write that

$$ P(R_2^{(n,\rho)} \cap \Upsilon_{\delta}) \le P(\hat{\Delta}_{\max}^{(n,\rho)} \ge F^{(1)}(2+\delta, \varepsilon, \varepsilon', \tau)). \qquad (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(\hat{\Delta}_{\max}^{(n,\rho_n)} > \nu) \le \frac{1}{n^{\log(\nu\sqrt{\chi_n(1+o(1))})}}, \quad n \to \infty. \qquad (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 \ge 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+$
Let us introduce the set

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

Then we can write an obvious inclusion

$$ R_2^{(n,\rho)} \subseteq (R_2^{(n,\rho)} \cap \Upsilon_{\delta}) \cup \bar{\Upsilon}_{\delta}. \qquad (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(\check{A}) - \gamma(re^{i\varphi})|^2 I_{\Upsilon_{\delta}} \ge M_{\varphi}|\lambda_{\max}(\check{A}) - \gamma(re^{i\varphi})|^2 I_{\Upsilon_{\delta}}, $$

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

$$ M_{\varphi}|\lambda_{\max}(\check{A}) - \gamma(re^{i\varphi})|^2 I_{\Upsilon_{\delta}} = |\lambda_{\max}(\check{A}) - \gamma(r)|^2 I_{\Upsilon_{\delta}} \ge |(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')$ is given by the value

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

see Lemma 4.2. Taking into account obvious inclusion,

$$ R_2^{(n,\rho)} \cap \Upsilon_{\delta} \subseteq \left\{ M_r^{(2)} M_{\varphi} \frac{|\lambda_{\max}(\check{A}) - \gamma(re^{i\varphi})|^2}{r} I_{\Upsilon_{\delta}} \le \hat{\Delta}_{\max}^{(n,\rho)} \right\}, $$

we can write that

$$ P(R_2^{(n,\rho)} \cap \Upsilon_{\delta}) \le P(\hat{\Delta}_{\max}^{(n,\rho)} \ge F^{(1)}(2+\delta, \varepsilon, \varepsilon', \tau)). \qquad (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(\hat{\Delta}_{\max}^{(n,\rho_n)} > \nu) \le \frac{1}{n^{\log(\nu\sqrt{\chi_n(1+o(1))})}}, \quad n \to \infty. \qquad (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 \ge 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', \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), \qquad (3.20) $$

where $\rho_n$ satisfies conditions (2.5).

Let us show that

$$ \sum_{n \ge 1} P(\bar{\Upsilon}_{\delta_n}) < \infty \quad \text{with} \quad \delta_n = \frac{1}{\chi_n^{3/8}}. \qquad (3.21) $$

It is easy to see that starting from some $n_0$, random matrix $\tilde{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} \| \tilde{A}^{(n, \rho)} \| < 2 + \frac{C}{\sqrt{\chi_n}}, \quad (\rho, \chi)_n \to \infty. \qquad (3.22) $$

Adding to this result the general concentration inequality

$$ P\left(\left|\|\tilde{A}^{(n, \rho)}\| - \mathbb{E}\|\tilde{A}^{(n, \rho)}\|\right| \ge t\right) \le \frac{2}{n^{c\chi_n t^2}}, \quad t > 0 \qquad (3.23) $$

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

$$ P\left(\|\tilde{A}\| \ge 2 + \delta\right) \le P\left(\left|\|\tilde{A}\| - \mathbb{E}\|\tilde{A}\|\right| \ge \delta - \frac{C}{\sqrt{\chi_n}}\right) \le \frac{2}{n^{c\chi_n(\delta/2)^2}}. \qquad (3.24) $$

It follows from (3.22) that

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

Then, using (3.23), we get

$$ P(\bar{\Upsilon}_{\delta}) \le \left( |\lambda_{\max}(\tilde{A}) - \mathbb{E}\lambda_{\max}(\tilde{A})| > \delta - C/\sqrt{\chi_n} \right) \le \frac{2n^{2\delta cC \sqrt{\chi_n}}}{n^{c\chi_n \delta^2} \cdot n^{cC^2}}. \qquad (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 \ge 1} P(R_2^{(n, \rho_n)}) < \infty. \qquad (3.26) $$

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

$$ \Psi_{\kappa} = \{ \lambda_1(\tilde{A}) \ge \sqrt{\rho}(1-\kappa) \} \qquad (3.27) $$

and observe that

$$ R_1^{(n, \rho)} \subseteq (R_1^{(n, \rho)} \cap \Psi_{\kappa}) \cup \bar{\Psi}_{\kappa}. \qquad (3.28) $$
$\delta, \varepsilon, \varepsilon', \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), \qquad (3.20) $$

where $\rho_n$ satisfies conditions (2.5).

Let us show that

$$ \sum_{n \ge 1} P(\bar{\Upsilon}_{\delta_n}) < \infty \quad \text{with} \quad \delta_n = \frac{1}{\chi_n^{3/8}}. \qquad (3.21) $$

It is easy to see that starting from some $n_0$, random matrix $\tilde{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} \| \tilde{A}^{(n, \rho)} \| < 2 + \frac{C}{\sqrt{\chi_n}}, \quad (\rho, \chi)_n \to \infty. \qquad (3.22) $$

Adding to this result the general concentration inequality

$$ P\left(\left\|\tilde{A}^{(n, \rho)}\right\| - \mathbb{E}\left\|\tilde{A}^{(n, \rho)}\right\| \ge t\right) \le \frac{2}{n^{c\chi_n t^2}}, \quad t > 0 \qquad (3.23) $$

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

$$ P\left(\|\tilde{A}\| \ge 2 + \delta\right) \le P\left(\left\|\tilde{A}\right\| - \mathbb{E}\left\|\tilde{A}\right\| \ge \delta - \frac{C}{\sqrt{\chi_n}}\right) \le \frac{2}{n^{c\chi_n(\delta/2)^2}}. \qquad (3.24) $$

It follows from (3.22) that

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

Then, using (3.23), we get

$$ P(\bar{\Upsilon}_{\delta}) \le \left( |\lambda_{\max}(\tilde{A}) - \mathbb{E}\lambda_{\max}(\tilde{A})| > \delta - C/\sqrt{\chi_n} \right) \le \frac{2n^{2\delta c C \sqrt{\chi_n}}}{n^{c\chi_n \delta^2} \cdot n^{cC^2}}. \qquad (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 \ge 1} P(R_2^{(n, \rho_n)}) < \infty. \qquad (3.26) $$

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

$$ \Psi_{\kappa} = \{ \lambda_1(\tilde{A}) \ge \sqrt{\rho}(1 - \kappa) \} \qquad (3.27) $$

and observe that

$$ R_1^{(n, \rho)} \subseteq (R_1^{(n, \rho)} \cap \Psi_{\kappa}) \cup \bar{\Psi}_{\kappa}. \qquad (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'} \frac{|\sqrt{\rho}(1-\kappa) - \gamma(r)|^2}{r} \le \hat{\Delta}_{\max}^{(n,\rho)} \right\}. \quad (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) \le P\left(\hat{\Delta}_{\max}^{(n,\rho)} \ge F^{(2)}(\sqrt{\rho}(1-\kappa), \varepsilon, \varepsilon', \tau)\right), \quad (3.30)$$

where

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

under condition

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

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

$$F^{(2)}(\sqrt{\rho}(1-\kappa), \varepsilon, \varepsilon', \tau) = \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) \le P\left(\hat{\Delta}_{\max}^{(n,\rho)} \ge \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) \le \frac{1}{n^{\log(\sqrt{\chi_n \rho_n}(h-\kappa)^2(1+o(1)))}}.$$

Therefore we can write that

$$\sum_{n \ge 1} P(R_1^{(n,\rho)} \cap \Psi_\kappa) < \infty. \quad (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(\sqrt{D_{\max}}, np_n)$, 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) \ge \max\left(\sqrt{\max_{i=1,...,n} b_{ii}^{(n,\rho_n)}}, \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)}) \ge (1+o(1))\sqrt{\rho_n}, \quad (\rho, \chi)_n \to \infty. \quad (3.33)$$
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'} \frac{|\sqrt{\rho}(1-\kappa) - \gamma(r)|^2}{r} \le \hat{\Delta}_{\max}^{(n,\rho)} \right\}. \quad (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) \le P\left(\hat{\Delta}_{\max}^{(n,\rho)} \ge F^{(2)}(\sqrt{\rho}(1-\kappa), \varepsilon, \varepsilon', \tau)\right), \quad (3.30)$$

where

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

under condition

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

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

$$F^{(2)}(\sqrt{\rho}(1-\kappa), \varepsilon, \varepsilon', \tau) = \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) \le P\left(\hat{\Delta}_{\max}^{(n,\rho)} \ge \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) \le \frac{1}{n^{\log(\sqrt{\chi_n \rho_n}(h-\kappa)^2(1+o(1)))}}.$$

Therefore we can write that

$$\sum_{n \ge 1} P(R_1^{(n,\rho)} \cap \Psi_\kappa) < \infty. \quad (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(\sqrt{D_{\max}}, np_n)$, 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) \ge \max\left(\sqrt{\max_{i=1,...,n} b_{ii}^{(n,\rho_n)}}, \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)}) \ge (1+o(1))\sqrt{\rho_n}, \quad (\rho, \chi)_n \to \infty. \quad (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| > \frac{t}{\sqrt{\rho_n}}\right) \le 4e^{-t^2/32} \quad (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) \le \frac{4}{n\chi_n s^2/32}. \quad (3.35)$$

It follows from (3.33) that

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

Then (3.35) implies the following upper bound,

$$P(\bar{\Psi}_{\kappa}) \le P\left(\left|\mathbb{E}\lambda_1(\tilde{A}) - \lambda_1(\tilde{A})\right| \ge \sqrt{\rho}\kappa(1+o(1))\right) \le \frac{4}{n\chi_n \rho_n \kappa^2(1+o(1))/32}.$$

Then clearly

$$\sum_{n \ge 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 \ge 1} P(R_1^{(n, \rho_n)}) < \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_{\varepsilon, \varepsilon'}^{(1)}} \min_{i=1, \dots, n} \frac{|\lambda_i(\tilde{A}) - \gamma^{(n, \rho)}(v)|^2}{|v|} \le \hat{\Delta}_{\max}^{(n, \rho)} \right\} = S^{(n, \rho)}(\varepsilon, \varepsilon'). \quad (3.36)$$

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

$$S_2^{(n, \rho)} \cap \Upsilon_{\delta} \subseteq \left\{ M_r^{(1)} M_{\varphi} \frac{|\lambda_{\max}(\tilde{A}) - \gamma(re^{i\varphi})|^2}{r} I_{\Upsilon_{\delta}} \le \hat{\Delta}_{\max}^{(n, \rho)} \right\},$$

and therefore

$$P(S_2^{(n, \rho)} \cap \Upsilon_{\delta}) \le P(\hat{\Delta}_{\max}^{(n, \rho)} \ge G^{(1)}(2 + \delta, \varepsilon, \varepsilon', \tau)). \quad (3.37)$$
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| > \frac{t}{\sqrt{\rho_n}}\right) \le 4e^{-t^2/32} \quad (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) \le \frac{4}{n\chi_n s^2/32}. \quad (3.35)$$

It follows from (3.33) that

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

Then (3.35) implies the following upper bound,

$$P(\bar{\Psi}_{\kappa}) \le P\left(\left|\mathbb{E}\lambda_1(\tilde{A}) - \lambda_1(\tilde{A})\right| \ge \sqrt{\rho}\kappa(1+o(1))\right) \le \frac{4}{n\chi_n \rho_n \kappa^2(1+o(1))/32}.$$

Then clearly

$$\sum_{n \ge 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 \ge 1} P(R_1^{(n, \rho_n)}) < \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_{\varepsilon, \varepsilon'}^{(1)}} \min_{i=1, \dots, n} \frac{|\lambda_i(\tilde{A}) - \gamma^{(n, \rho)}(v)|^2}{|v|} \le \hat{\Delta}_{\max}^{(n, \rho)} \right\} = S^{(n, \rho)}(\varepsilon, \varepsilon'). \quad (3.36)$$

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

$$S_2^{(n, \rho)} \cap \Upsilon_{\delta} \subseteq \left\{ M_r^{(1)} M_{\varphi} \frac{|\lambda_{\max}(\tilde{A}) - \gamma(re^{i\varphi})|^2}{r} I_{\Upsilon_{\delta}} \le \hat{\Delta}_{\max}^{(n, \rho)} \right\},$$

and therefore

$$P(S_2^{(n, \rho)} \cap \Upsilon_{\delta}) \le P(\hat{\Delta}_{\max}^{(n, \rho)} \ge G^{(1)}(2 + \delta, \varepsilon, \varepsilon', \tau)). \quad (3.37)$$
Relation (4.19) shows that $G^{(1)}(2 + \delta, \varepsilon, \varepsilon', \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 \qquad (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' < r < 1-\varepsilon} \frac{|\sqrt{\rho}(1-\kappa) - \gamma(r)|^2}{r} \le \hat{\Delta}_{\max}^{(n,\rho)} \right\} $$

and by Lemma 4.3, we have

$$ P(S_1^{(n,\rho)} \cap \Psi_{\kappa}) \le P\left(\hat{\Delta}_{\max}^{(n,\rho)} \ge G^{(2)}(\sqrt{\rho}(1-\kappa), \varepsilon, \varepsilon', \tau)\right), \quad (3.39) $$

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

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

Then (3.19) implies convergence

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

The upper bounds for the probabilities $P(\bar{Y}_{\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)| \le |v| \hat{\Delta}_{\max}^{(n,\rho)}, \quad i=1, \dots, n, \qquad (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

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

and

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

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

$$ \hat{\Phi}_{n,\rho}^{(2)}(\hat{\varepsilon}, \varepsilon') = \cup_{1+\hat{\varepsilon}<v<1/\varepsilon'} \{\omega : \det(H(v)) = 0\} \subseteq \hat{R}_1^{(n,\rho)} \cup \hat{R}_2^{(n,\rho)}, $$
Relation (4.19) shows that $G^{(1)}(2 + \delta, \varepsilon, \varepsilon', \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 \qquad (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' < r < 1 - \varepsilon} \frac{|\sqrt{\rho}(1 - \kappa) - \gamma(r)|^2}{r} \le \hat{\Delta}_{\max}^{(n,\rho)} \right\} $$

and by Lemma 4.3, we have

$$ P(S_1^{(n,\rho)} \cap \Psi_{\kappa}) \le P\left(\hat{\Delta}_{\max}^{(n,\rho)} \ge G^{(2)}(\sqrt{\rho}(1-\kappa), \varepsilon, \varepsilon', \tau)\right), \qquad (3.39) $$

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

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

Then (3.19) implies convergence

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

The upper bounds for the probabilities $P(\bar{Y}_{\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)| \le |v| \hat{\Delta}_{\max}^{(n,\rho)}, \quad i = 1, \dots, n, \qquad (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

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

and

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

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

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

$$ \hat{R}_1^{(n,\rho)} = \left\{ M_v^{(2)} \frac{|\lambda_1(\tilde{A}) - \gamma(v)|}{|v|} \le \hat{\Delta}_{\max}^{(n,\rho)} \right\} $$

and

$$ \hat{R}_2^{(n,\rho)} = \left\{ M_v^{(2)} \min_{i=2,\dots,n} \frac{|\lambda_i(\tilde{A}) - \gamma(v)|}{|v|} \le \hat{\Delta}_{\max}^{(n,\rho)} \right\} $$

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

$$ \hat{F}^{(1)}(2 + \delta, \hat{\varepsilon}, \varepsilon', \tau) = \frac{\varepsilon^2 - \delta(1 + \varepsilon) - \tau(1 + \varepsilon)^2}{(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}_2^{(n,\rho)} \cap \Upsilon_{\delta}) \le P(\hat{\Delta}_{\max}^{(n,\rho)} \ge \hat{\varepsilon}^2) \le \frac{1}{n^{\log(\hat{\varepsilon}^2 \sqrt{\chi_n(1+o(1))})}}, \quad n \to \infty. \quad (3.42) $$

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

$$ \sum_{n \ge 1} P \left( \hat{R}_2^{(n, \rho_n)} \cap \Upsilon_{\delta_n} \right) < \infty, \quad \delta_n = \frac{\hat{\varepsilon}_n^2}{h}. \quad (3.43) $$

It follows from the upper bound (3.25) that to have the series of $P(\tilde{\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

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

where $\lambda_1 \le \dots \le \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 \le j \le 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 $$
where

$$ \hat{R}_1^{(n,\rho)} = \left\{ M_v^{(2)} \frac{|\lambda_1(\tilde{A}) - \gamma(v)|}{|v|} \le \hat{\Delta}_{\max}^{(n,\rho)} \right\} $$

and

$$ \hat{R}_2^{(n,\rho)} = \left\{ M_v^{(2)} \min_{i=2,\dots,n} \frac{|\lambda_i(\tilde{A}) - \gamma(v)|}{|v|} \le \hat{\Delta}_{\max}^{(n,\rho)} \right\} $$

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

$$ \hat{F}^{(1)}(2 + \delta, \hat{\varepsilon}, \varepsilon', \tau) = \frac{\varepsilon^2 - \delta(1 + \varepsilon) - \tau(1 + \varepsilon)^2}{(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}_2^{(n,\rho)} \cap \Upsilon_{\delta}) \le P(\hat{\Delta}_{\max}^{(n,\rho)} \ge \hat{\varepsilon}^2) \le \frac{1}{n^{\log(\hat{\varepsilon}^2 \sqrt{\chi_n(1+o(1))})}}, \quad n \to \infty. \quad (3.42) $$

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

$$ \sum_{n \ge 1} P \left( \hat{R}_2^{(n, \rho_n)} \cap \Upsilon_{\delta_n} \right) < \infty, \quad \delta_n = \frac{\hat{\varepsilon}_n^2}{h}. \quad (3.43) $$

It follows from the upper bound (3.25) that to have the series of $P(\tilde{\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

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

where $\lambda_1 \le \dots \le \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 \le j \le 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 = \frac{\lambda_j + \sqrt{\lambda_j^2 - 4q}}{2}. \quad (4.2) $$

Thus the values $\alpha_j$ and $\beta_j$ are complex conjugate if and only if

$$ |\lambda_j| \le 2\sqrt{q}. \quad (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 \text{or} \quad q^s = \beta_j, \quad (4.4) $$

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

**4.2. Distance property of ellipsoid.** Let $\mathcal{E}(a, b)$ denote the family of points on $\mathbb{R}^2$

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

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

$$ \mathcal{D}(x)^2 = \min_{(s,t) \in \mathcal{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 - \frac{b^2 s^2}{a^2}. $$

**Lemma 4.1.** There exists a critical point $x_0 = a(1 - b^2/a^2)$ such that

$$ \mathcal{D}(x)^2 = \begin{cases} b^2 \left(1 - \frac{x^2}{a^2 - b^2}\right), & \text{if } 0 \le x \le x_0, \\ (a-x)^2, & \text{if } x_0 \le x \le a \end{cases} \quad (4.5) $$

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

$$ \frac{\partial}{\partial s} \phi(x, s) = 2(s - x) - \frac{2b^2s}{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

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

$$ \alpha_j, \beta_j = \frac{\lambda_j + \sqrt{\lambda_j^2 - 4q}}{2}. \qquad (4.2) $$

Thus the values $\alpha_j$ and $\beta_j$ are complex conjugate if and only if

$$ |\lambda_j| \le 2\sqrt{q}. \qquad (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 \text{or} \quad q^s = \beta_j, \qquad (4.4) $$

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

**4.2. Distance property of ellipsoid.** Let $\mathcal{E}(a, b)$ denote the family of points on $\mathbb{R}^2$

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

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

$$ \mathcal{D}(x)^2 = \min_{(s,t) \in \mathcal{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 - \frac{b^2 s^2}{a^2}. $$

**Lemma 4.1.** There exists a critical point $x_0 = a(1 - b^2/a^2)$ such that

$$ \mathcal{D}(x)^2 = \begin{cases} b^2 \left(1 - \frac{x^2}{a^2 - b^2}\right), & \text{if } 0 \le x \le x_0, \\ (a-x)^2, & \text{if } x_0 \le x \le a \end{cases} \qquad (4.5) $$

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

$$ \frac{\partial}{\partial s} \phi(x, s) = 2(s - x) - \frac{2b^2s}{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

$$ \mathcal{D}(x)^2 = \phi(x, \tilde{s}(x)). $$
If $x \in [x_0, a]$, then the derivative $\phi'_s(x, s)$ has no zero on the interval $s \in [0, a]$ and therefore

$$ \mathcal{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 \ge x_0$, then the point $\tilde{s}$ coincides with the right extremity of the ellipsoid, $\tilde{s} = a$ for all $x \ge x_0$. The derivative of $\mathcal{D}(x)^2$ is a discontinuous function and that the distance $\mathcal{D}(x)^2$ shows a kind of "phase transition" of the first order at $x = x_0$. $\square$

Let us point out that the distance $\mathcal{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]} \mathcal{D}(x) = \mathcal{D}(s). \qquad (4.6) $$

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

$$ \dot{\mathcal{E}} = \mathcal{E}(\dot{a}, \dot{b}) = \begin{cases} \gamma^{(n,\rho)}(re^{i\varphi}), & 0 \le \varphi < 2\pi \end{cases} $$

is given by an ellipsoid with the half-axes

$$ \dot{a} = r(1 - \tau) + \frac{1}{r}, \quad \dot{b} = r(1 - \tau) - \frac{1}{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 \ge \mathcal{D}(\lambda)^2 $$

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

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

one can easily see that if

$$ \varepsilon < 1 \quad \text{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) + \frac{1}{r} - 2 - \delta \right)^2. \qquad (4.7) $$

Elementary analysis of the function

$$ \gamma(x) = x(1 - \tau) + \frac{1}{x} $$
If $x \in [x_0, a]$, then the derivative $\phi'_s(x, s)$ has no zero on the interval $s \in [0, a]$ and therefore

$$ \mathcal{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 \ge x_0$, then the point $\tilde{s}$ coincides with the right extremity of the ellipsoid, $\tilde{s} = a$ for all $x \ge x_0$. The derivative of $\mathcal{D}(x)^2$ is a discontinuous function and that the distance $\mathcal{D}(x)^2$ shows a kind of "phase transition" of the first order at $x = x_0$. $\square$

Let us point out that the distance $\mathcal{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]} \mathcal{D}(x) = \mathcal{D}(s). \qquad (4.6) $$

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

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

is given by an ellipsoid with the half-axes

$$ \dot{a} = r(1 - \tau) + \frac{1}{r}, \quad \dot{b} = r(1 - \tau) - \frac{1}{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 \ge \mathcal{D}(\lambda)^2 $$

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

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

one can easily see that if

$$ \varepsilon < 1 \quad \text{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) + \frac{1}{r} - 2 - \delta \right)^2. \qquad (4.7) $$

Elementary analysis of the function

$$ \gamma(x) = x(1 - \tau) + \frac{1}{x} $$
shows that if

$$ \varepsilon > \frac{1}{\sqrt{1-\tau}} - 1 \quad \text{and} \quad \varepsilon > \varepsilon_0 = \frac{(2\tau + \delta) + \sqrt{4\delta + \delta^2 + 4\tau}}{2(1-\tau)}, \qquad (4.8) $$

then

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

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

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

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

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

such that $x_3 < 0 < x_1 < x_4 < 1$ and

$$ 1 < x_2 = \frac{q + \sqrt{q^2 - 4(1-\tau)}}{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'$ verify inequality $1 + \varepsilon < 1/\varepsilon'$. If $q$ is greater than $2 - \tau$ and such that $x_2 < 1 + \varepsilon$, then

$$ F^{(1)}(q, \varepsilon, \varepsilon', \tau) = \inf_{1+\varepsilon<x<1/\varepsilon'} f(x) = f(1+\varepsilon) = \frac{((1+\varepsilon)^2(1-\tau) - q(1+\varepsilon) + 1)^2}{(1+\varepsilon)^3}. \qquad (4.10) $$

If $q$ is greater than $2 + \tau$ and such that $1/\varepsilon' < x_2$, then

$$ F^{(2)}(q, \varepsilon, \varepsilon', \tau) = \inf_{1+\varepsilon<x<1/\varepsilon'} f(x) = f(1/\varepsilon') = \frac{1}{\varepsilon'} ((1-\tau) - q\varepsilon' + (\varepsilon')^2)^2. \qquad (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 \text{and} \quad \tau = o(\delta), \qquad (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', \tau) = \varepsilon^4(1 + o(1)), \quad \varepsilon \to 0 \qquad (4.13) $$
shows that if

$$ \varepsilon > \frac{1}{\sqrt{1-\tau}} - 1 \quad \text{and} \quad \varepsilon > \varepsilon_0 = \frac{(2\tau + \delta) + \sqrt{4\delta + \delta^2 + 4\tau}}{2(1-\tau)}, \qquad (4.8) $$

then

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

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

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

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

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

such that $x_3 < 0 < x_1 < x_4 < 1$ and

$$ 1 < x_2 = \frac{q + \sqrt{q^2 - 4(1-\tau)}}{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'$ verify inequality $1 + \varepsilon < 1/\varepsilon'$. If $q$ is greater than $2 - \tau$ and such that $x_2 < 1 + \varepsilon$, then

$$ F^{(1)}(q, \varepsilon, \varepsilon', \tau) = \inf_{1+\varepsilon<x<1/\varepsilon'} f(x) = f(1+\varepsilon) = \frac{((1+\varepsilon)^2(1-\tau) - q(1+\varepsilon) + 1)^2}{(1+\varepsilon)^3}. \qquad (4.10) $$

If $q$ is greater than $2 + \tau$ and such that $1/\varepsilon' < x_2$, then

$$ F^{(2)}(q, \varepsilon, \varepsilon', \tau) = \inf_{1+\varepsilon<x<1/\varepsilon'} f(x) = f(1/\varepsilon') = \frac{1}{\varepsilon'} ((1-\tau) - q\varepsilon' + (\varepsilon')^2)^2. \qquad (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. $\square$

Regarding our main asymptotic regime when

$$ \varepsilon, \delta, \tau \to 0, \quad \delta = o(\varepsilon^2), \quad \text{and} \quad \tau = o(\delta), \qquad (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', \tau) = \varepsilon^4(1 + o(1)), \quad \varepsilon \to 0 \qquad (4.13) $$
is true.

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

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

Let us study the minimum of $\gamma(x)$ over the interval $r \in (\epsilon', 1 - \epsilon)$. The first observation is that if

$$\epsilon > \frac{-(2\tau + \delta) + \sqrt{\delta^2 + 4\delta + 4\tau}}{2(1 - \tau)}, \quad (4.15)$$

then the following analogue of (4.9) is verified,

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

**Lemma 4.3.** Let positive $\epsilon$ and $\epsilon'$ verify inequality $\epsilon' < 1 - \epsilon$. If $q$ is greater than $2 + \tau$ and such that $1 - \epsilon < x_1$, then

$$G^{(1)}(q, \epsilon, \epsilon', \tau) = \inf_{\epsilon' < x < 1-\epsilon} f(x) = f(1-\epsilon) = \frac{(\epsilon^2 - \delta(1+\epsilon) - \tau(1+\epsilon)^2)^2}{(1-\epsilon)^3}. \quad (4.17)$$

If $q$ is such that $x_1 < \epsilon'$, then

$$G^{(2)}(q, \epsilon, \epsilon', \tau) = \inf_{\epsilon' < x < 1-\epsilon} f(x) = f(\epsilon') = \frac{((\epsilon')^2(1-\tau) - q\epsilon' + 1)^2}{(\epsilon')^3}. \quad (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, \epsilon, \epsilon', \tau) = \epsilon^4(1 + o(1)), \quad \epsilon \to 0. \quad (4.19)$$

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

$$G^{(2)}(\sqrt{\rho}(1 - \kappa), \epsilon, \epsilon', \tau) = \rho^{3/2}(1 - h)(h - \kappa)^2(1 + o(1)) \quad (4.20)$$

is true in the asymptotic regime (4.12).
is true.

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

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

Let us study the minimum of $\gamma(x)$ over the interval $r \in (\epsilon', 1 - \epsilon)$. The first observation is that if

$$\epsilon > \frac{-(2\tau + \delta) + \sqrt{\delta^2 + 4\delta + 4\tau}}{2(1 - \tau)}, \quad (4.15)$$

then the following analogue of (4.9) is verified,

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

**Lemma 4.3.** Let positive $\epsilon$ and $\epsilon'$ verify inequality $\epsilon' < 1 - \epsilon$. If $q$ is greater than $2 + \tau$ and such that $1 - \epsilon < x_1$, then

$$G^{(1)}(q, \epsilon, \epsilon', \tau) = \inf_{\epsilon' < x < 1-\epsilon} f(x) = f(1-\epsilon) = \frac{(\epsilon^2 - \delta(1+\epsilon) - \tau(1+\epsilon)^2)^2}{(1-\epsilon)^3}. \quad (4.17)$$

If $q$ is such that $x_1 < \epsilon'$, then

$$G^{(2)}(q, \epsilon, \epsilon', \tau) = \inf_{\epsilon' < x < 1-\epsilon} f(x) = f(\epsilon') = \frac{((\epsilon')^2(1-\tau) - q\epsilon' + 1)^2}{(\epsilon')^3}. \quad (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, \epsilon, \epsilon', \tau) = \epsilon^4(1 + o(1)), \quad \epsilon \to 0. \quad (4.19)$$

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

$$G^{(2)}(\sqrt{\rho}(1 - \kappa), \epsilon, \epsilon', \tau) = \rho^{3/2}(1 - h)(h - \kappa)^2(1 + o(1)) \quad (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 $\tilde{A} = \tilde{A} - tJ$ (where $J$ is the matrix with all 1 entries), then

$$ \lambda_2(\tilde{A}) \le \lambda_1(\tilde{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

$$ \begin{aligned} \lambda_2(\tilde{A}) &\le \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}(\tilde{A} + tJ)\mathbf{x} \\ &= \max_{(\mathbf{x},\mathbf{1})=0, \|\mathbf{x}\|=1} \mathbf{x}\tilde{A}\mathbf{x} \le \lambda_1(\tilde{A}), \end{aligned} $$

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

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

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

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

$$ \begin{aligned} \lambda_{-\infty}(\tilde{A}) &= \min_{\|\mathbf{x}\|=1} \mathbf{x}\tilde{A}\mathbf{x} \ge \min_{\|\mathbf{x}\|=1} \mathbf{x}\tilde{A}\mathbf{x} + \min_{\|\mathbf{x}\|=1} xtJ\mathbf{x} \\ &\ge \min_{\|\mathbf{x}\|=1} \mathbf{x}\tilde{A}\mathbf{x} = \lambda_{-\infty}(\tilde{A}). \end{aligned} $$

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.
**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 $\tilde{A} = \tilde{A} - tJ$ (where $J$ is the matrix with all 1 entries), then

$$ \lambda_2(\tilde{A}) \le \lambda_1(\tilde{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

$$ \begin{aligned} \lambda_2(\tilde{A}) &\le \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}(\tilde{A} + tJ)\mathbf{x} \\ &= \max_{(\mathbf{x},\mathbf{1})=0, \|\mathbf{x}\|=1} \mathbf{x}\tilde{A}\mathbf{x} \le \lambda_1(\tilde{A}), \end{aligned} $$

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

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

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

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

$$ \begin{aligned} \lambda_{-\infty}(\tilde{A}) &= \min_{\|\mathbf{x}\|=1} \mathbf{x}\tilde{A}\mathbf{x} \ge \min_{\|\mathbf{x}\|=1} \mathbf{x}\tilde{A}\mathbf{x} + \min_{\|\mathbf{x}\|=1} xtJ\mathbf{x} \\ &\ge \min_{\|\mathbf{x}\|=1} \mathbf{x}\tilde{A}\mathbf{x} = \lambda_{-\infty}(\tilde{A}). \end{aligned} $$

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 $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.
[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 $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
[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