# The characteristic polynomial of sums of random permutations
and regular digraphs

Simon Coste  Département d’informatique, ENS - PSL University
<EMAIL_ADDRESS>,  Gaultier Lambert  Institute of Mathematics, University
of Zurich<EMAIL_ADDRESS>and  Yizhe Zhu  Department of Mathematics,
University of California, Irvine<EMAIL_ADDRESS>
###### Abstract.

Let $A_{n}$ be the sum of $d$ permutations matrices of size $n\times n$, each
drawn uniformly at random and independently. We prove that the normalized
characteristic polynomial $\frac{1}{\sqrt{d}}\det(I_{n}-zA_{n}/\sqrt{d})$
converges when $n\to\infty$ towards a random analytic function on the unit
disk. As an application, we obtain an elementary proof of the spectral gap of
random regular digraphs. Our results are valid both in the regime where $d$ is
fixed and for $d$ slowly growing with $n$.

##  1\. Introduction

Spectral properties of non-Hermitian random matrices can have different
behaviors depending on their degree of sparsity. These properties are now well
understood for dense matrices with iid entries; a well-known example is the
Circular Law [10], for which the optimal sparsity threshold is known [53, 7,
50]. However, when the matrices in question are very sparse, with a fixed
number of non-zero entries on each row, including dependencies, the problem
becomes different and more challenging. One of our goals in this paper is to
understand these differences.

#### Sums-of-permutations

There are numerous ways to enforce sparsity in random matrices, and different
ensembles are expected to behave differently. In this paper, we focus on
_permutation matrices_ , that is, matrices with exactly one non-zero entry on
each row and each column; adding $d$ independent permutation matrices chosen
uniformly at random, we obtain a random matrix $A$ with integer entries, whose
row/column-sums are all exactly equal to $d$. Thus, $A$ can be viewed as a
typical matrix with fixed row sums and column sums. This model displays two
important properties:

  1. (i)

The structure of $A$ is very constrained (fixed row/column sums), hence the
entries of $A$ are not independent.

  2. (ii)

The rows and columns of $A$ can be swapped while keeping the distribution of
$A$ invariant (invariance by permutations).

#### Random regular directed graphs

Sums of random permutations are of particular interest to random graph theory
since they are a popular proxy for the (adjacency) matrix of _random regular
digraphs_. A digraph is regular when each node has the same number of in-
neighbors and out-neighbors; consequently, the matrix $A$ defined above is the
matrix of a $d$-regular digraph, possibly with multiple edges. It turns out
that for fixed $d$, conditioning on $A$ having no entry greater than $1$, the
graph represented by $A$ is nearly uniform among all the $d$-regular directed
graphs (the two models are _contiguous_ [34], and both are contiguous with the
configuration model). Our analysis thus provides results on the eigenvalues of
random regular digraphs, notably a new proof for the directed version of
Friedman’s second eigenvalue theorem [25, 9] which relates to important graph-
theoretical notions such as graph expansion and random walks on digraphs [47,
20].

#### Spectral properties

In general, studying the eigendecomposition of non-Hermitian matrices can be
challenging. For an $n\times n$ permutation matrix ($d=1$), the eigenvalues of
$A$ belong to the $n$-th roots of unity, and their multiplicity is given by
the cycle decomposition theorem; if $c_{k}$ denotes the number of cycles of
length $k$ (thus $c_{1}+2c_{2}+\dotsb+nc_{n}=n$ ), then the multiplicity of a
root of unity $\omega$ will be the sum of the $c_{k}$ for which
$\omega^{k}=1$. This basic structure allows to study even non-uniform
permutation matrices [32, 8]. However, already for $d=2$, this straightforward
analysis breaks down because generically, the permutation matrices that we sum
do not commute. In particular, a famous conjecture states that for fixed $d$
as $n\to\infty$, the empirical spectral measure of $A$ converges to the
oriented Kesten-McKay distribution [10]. In contrast, in the regime where
$d\to\infty$ as $n\to\infty$, one expects to recover the circular law and
there are already several results in this direction [5, 14, 40].

#### Our contributions

In this paper, we study asymptotics of the characteristic polynomial outside
of the spectral support. The results we obtain are analogous to [11, 44]; we
identify the distributional functional limit of the characteristic polynomial
of $A$, away from the spectrum. This problem has also been considered in the
Hermitian case for Gaussian $\beta$-ensembles [37]. In particular, the
relationships between our results and the theory of multiplicative chaos are
discussed in Section 2.2. Surprisingly, we obtain the same limiting functions
as in [19], which considers non-Hermitian matrices with independent
$\mathrm{Bernoulli}(d/n)$ entries — a proxy for sparse Erdős-Rényi digraphs.
This result is rather unexpected since in the Hermitian case, the spectral
properties of random regular graphs and sparse Erdős-Rényi graphs are
radically different for fixed $d$. In Appendix B, we also report on several
observations regarding the sum of Ewens-distributed random permutations, which
can be of independent interest.

As corollaries of our convergence results for characteristic polynomials
(Theorems 2.4 and 2.6 stated in Section 2), we obtain two spectral gap
theorems covering different regimes.

######  Theorem 1.1 (spectral gap for $d$-regular digraphs, $d$ fixed).

Let $A_{n}$ be one of the following random matrix models:

  1. (i)

the sum of $d$ independent uniform permutation matrices of size $n\times n$;

  2. (ii)

the sum of $d$ independent $n\times n$ uniform permutation matrices
conditioned on their graph being simple;

  3. (iii)

the adjacency matrix of a uniform random directed $d$-regular graph on $n$
vertices.

Then, for any $\varepsilon>0$ and $d\geq 1$,

$\lim_{n\to\infty}\mathbb{P}(|\lambda_{2}|>\sqrt{d}+\varepsilon)=0.$

where $\lambda_{i}$ are the complex eigenvalues of $A_{n}$, ordered by
decreasing modulus:
$d=\lambda_{1}\geqslant|\lambda_{2}|\geqslant\dotsb\geqslant|\lambda_{n}|$.

Theorem 1.1 gives an alternate proof of the spectral gap result obtained in
[20]; it notably implies that there are no outliers outside the support of the
oriented Kesten-McKay law, except the trivial eigenvalue $\lambda_{1}=d$. It
is not known for the moment how to prove the matching lower-bound on
$|\lambda_{2}|$; regarding this problem (directed analogs of the Alon-Boppana
inequality), we refer to the discussion in [19, Section 4].

When $d(n)\to\infty$, there is no contiguity result in the literature between
the uniform regular digraphs and sums of random permutations (it was
conjectured in [17] these two models are contiguous when $d(n)=O(\log n)$);
therefore, our next Theorem only applies to the sums-of-permutations model.

######  Theorem 1.2 (spectral gap for sums of permutations, $d(n)\to\infty$).

Let $A_{n}$ be the sum of $d(n)$ independent $n\times n$ uniform random
permutation matrices. Assume that $d(n)\to\infty$ in such a way that
$d(n)=n^{o(1)}$ as $n\to\infty$. Then, for any $\varepsilon>0$,

(1.1) $\displaystyle\mathbb{P}(|\lambda_{2}|>\sqrt{d(n)}(1+\varepsilon))\to 0$

where $\lambda_{i}$ are the complex eigenvalues of $A$, ordered by decreasing
modulus:
$d=\lambda_{1}\geqslant|\lambda_{2}|\geqslant\dotsb\geqslant|\lambda_{n}|$.

Combining the circular law proved in [5] for the random matrix
$A_{n}/\sqrt{d(n)}$, the bound (1.1) is sharp (at least in the regime
$d(n)\geq\log^{12}(n)/(\log\log n)^{4}$ and $d(n)=n^{o(1)}$). With high
probability, there is no outlier eigenvalues besides the trivial one
$\lambda_{1}=\sqrt{d(n)}$. In Theorem 1.2, the condition $d(n)=n^{o(1)}$ is
technical (due to our proof of Theorem 3.1 (2)) and it could be dispensed with
some extra work.

### Related work

The spectral properties of random permutations under Ewens distribution were
investigated in several works, including the characteristic polynomial and
linear statistics [32, 21, 8, 3, 2, 4]. For a uniform random permutation
matrix, the maximum of the characteristic polynomial on the unit circle has
been studied in [16]. It is also of interest to study this question for sums-
of-permutations for general $d$ and we intend to consider this problem in
subsequent work.

Spectral gap of random $d$-regular digraphs with fixed $d$ was studied in [20]
using the high trace method, which is limited to fixed $d$. For uniform random
regular digraphs, it was shown in [54] that $|\lambda_{2}|\leq C\sqrt{d(n)}$
for $d(n)=O(n^{2/3})$, and for $n^{\varepsilon}\leq d(n)\leq n/2$ in [52]. By
the size-biased coupling method introduced in [15], one can prove a similar
result to [15, Theorem 2.6] that $|\lambda_{2}|=O(\sqrt{d(n)})$ for the sum of
permutations for any $2\leq d(n)\leq n/2$. However, all of these results rely
on the $\varepsilon$-net and the Kahn-Szemrédi argument [26], which yields an
absolute constant far from optimal. Our approach gives a unified treatment for
fixed and growing $d$ in the random permutation model with a sharp constant,
while being elementary on a technical level.

Lower bounds on the least singular value of random $d$-regular digraphs for
fixed $d$ is a problem of considerable interests since it is a crucial step
towards proving the conjectured oriented Kesten-McKay law. The singularity
probability was estimated in [31, 41] for fixed $d$, and in [18, 38] for
growing $d(n)$. Quantitative estimates on the least singular values for
growing $d(n)$ were obtained in [5, 14, 39, 33].

In the Hermitian case, the sum of random permutations and their transpose
$\sum_{i=1}^{d}(P_{i}+P_{i}^{\top})$ can be seen as a model for random
$2d$-regular multi-graphs, and their spectral properties have been
investigated, including spectral gaps [25, 15] and linear eigenvalue
statistics [22, 35, 29]. There is also a direct connection between random
$d$-regular digraphs and random bipartite $d$-regular graphs. In particular,
the eigenvalue fluctuation results of random bipartite regular graphs shown in
[23] can be translated to singular value fluctuations of random regular
digraphs. However, it is a very challenging problem to study the eigenvalue
fluctuations of random regular digraphs.

### Acknowledgements

G.L. and Y.Z. acknowledge support from NSF DMS-1928930 during their
participation in the program “Universality and Integrability in Random Matrix
Theory and Interacting Particle Systems” hosted by the Mathematical Sciences
Research Institute in Berkeley, California during the Fall semester of 2021.
G.L. is supported by the SNSF Ambizione grant S-71114-05-01. Y.Z. is partially
supported by NSF-Simons Research Collaborations on the Mathematical and
Scientific Foundations of Deep Learning. S.C. is supported by ENS-PSL.

##  2\. Main Results

###  2.1. Sums of random permutations

For any $n\in\mathbb{N}$, let $d=d(n)\in\mathbb{N}$ and
$P^{(1)},\dotsc,P^{(d)}$ be a collection of i.i.d.random uniform $n\times n$
permutation matrices. We consider the random matrix

$A_{n}:=P^{(1)}+\dotsb+P^{(d)}.$

In the sequel, we will often drop the $n$ subscript and simply write $d,A$,
etc. We define the (rescaled) characteristic polynomial of $A$,

(2.1)
$\widehat{\chi}_{n}(z):=\frac{1}{\sqrt{d}}\det\left(I_{n}-z\frac{A}{\sqrt{d}}\right)\qquad(z\in\mathbb{C}).$

Note that $A$ has a trivial eigenvalue $d$ associated with the vector
$\mathbf{1}^{n}$, so that with our convention,
$\widehat{\chi}_{n}(1/\sqrt{d})=0$ almost surely. If fact, we will see that
for any $n\in\mathbb{N}$,

$\mathbb{E}[\widehat{\chi}_{n}(z)]=z-1/\sqrt{d}\qquad(z\in\mathbb{C}).$

The main results of this paper identify the weak $n\to\infty$ limit of the
sequence $(\widehat{\chi}_{n})$ in the unit disk either when the degree
$d(n)=d$ is fixed, or when $d(n)\to\infty$ slowly with $n$. Up to a rescaling,
the limit is the same as the function defined in [19]; but we adopt different
conventions allowing for a unified treatment of the cases $d=O(1)$ and
$d\to\infty$. We denote $D_{r}=\\{z\in\mathbb{C}:|z|<r\\}$ the disk of radius
$r>0$ in the complex plane.

We define the topology for the convergence of the random analytic functions,
and tightness for a sequence of random analytic functions.

######  Definition 2.1 (convergence of random analytic functions).

Let $H(D_{1})$ be the set of analytic functions on $D_{1}$, equipped with the
topology of uniform convergence on compact subsets on $D_{1}$. There is an
induced metric $\rho$ on $H(D_{1})$ such that $\rho(f_{n},f)\to 0$ if and only
if $f_{n}$ converges to $f$ locally uniformly on $D_{1}$, see [51] for more
details. A sequence of random analytic functions on $H(D_{1})$ converges in
law to some random analytic function $f\in H(D_{1})$ if for every bounded
real-valued continuous (with respect to $\rho$) function $g$ on $H(D_{1})$,
$\mathbb{E}[g(f_{n})]\to\mathbb{E}[g(f)]$.

######  Definition 2.2 (tightness).

A sequence of random analytic functions $\\{f_{n}\\}$ in $H(D_{1})$ is tight
if for every $\varepsilon>0$, there exists a compact subset $K$ of $H(D_{1})$
such that $\mathbb{P}(f_{n}\in K)>1-\varepsilon$ for sufficiently large $n$.

######  Definition 2.3.

Fix $d\in\mathbb{N}$ and let $\\{\Lambda_{\ell}\\}_{\ell\in\mathbb{N}}$ be a
family of independent random variables, with

$\Lambda_{\ell}\sim\mathrm{Poisson}\left(\frac{d^{\ell}}{\ell}\right).$

We also denote
$\overline{\Lambda_{\ell}}=\Lambda_{\ell}-\mathbb{E}[\Lambda_{\ell}]$ their
centered versions. For any integer $d$, we define the following formal series:

(2.2) $\displaystyle
Y_{d}(z):=\sum_{k\in\mathbb{N}}\frac{z^{k}}{kd^{k/2}}\sum_{\ell|k}\ell\overline{\Lambda_{\ell}},\qquad$
$\displaystyle
X_{d}(z):=\sum_{k\in\mathbb{N}}\frac{z^{k}}{d^{k/2}}\overline{\Lambda_{k}}.$

Proposition 2.7 implies that these functions are well-defined and analytic
functions in the unit disk $D_{1}$. Let us now state our main result for $d$
fixed.

######  Theorem 2.4.

Consider a fixed integer $d$ and let $d(n)=d$ for every $n$; let $Y_{d}$ be as
in (2.2). Then,

$\widehat{\chi}_{n}(z)\xrightarrow[n\to\infty]{\mathrm{law}}(z-1/\sqrt{d})\frac{e^{-Y_{d}(z)}}{\mathbb{E}[e^{-Y_{d}(z)}]}$

for the topology of uniform convergence on compact subsets of $D_{1}$.

In contrast, if the degree $d$ diverges, then we recover a Gaussian analytic
function in the limit, as for dense matrices non-Hermitian (real-valued)
Wigner matrices [11] — note that this function is real-analytic, the
coefficients being _real_ Gaussian variables, not complex ones. The proof of
Theorem 2.4 and the subsequent results is outlined in Section 3.

######  Definition 2.5.

Let $\\{N_{\ell}\\}_{\ell\in\mathbb{N}}$ be i.i.d. standard real Gaussian
random variables and define the random real-analytic function

(2.3)
$X_{\infty}(z)=\sum_{k\in\mathbb{N}}\frac{N_{k}}{\sqrt{k}}z^{k}\qquad(z\in
D_{1}).$

######  Theorem 2.6.

Consider a sequence $d(n)\in\mathbb{N}$ such that $d(n)\to\infty$ and
$d(n)=n^{o(1)}$ as $n\to\infty$. Let $X_{\infty}$ be as in (2.3). Then, it
holds for the topology of locally uniform convergence on $D_{1}$,

$\widehat{\chi}_{n}(z)\xrightarrow[n\to\infty]{\mathrm{law}}z\sqrt{1-z^{2}}e^{X_{\infty}(z)}.$

The technical condition $d(n)=n^{o(1)}$ means that $\log d(n)=o(\log n)$ as
$n\to\infty$.

###  2.2. Log-correlated structure of the limiting random fields

We gather here a few properties of the functions $X_{d},Y_{d}$. In particular,
we show that the boundary-values (on the unit circle $\partial D_{1}$) of the
functions $Y_{d}$ and $X_{\infty}$ are log-correlated fields and discuss some
expected consequences.

######  Proposition 2.7.

$Y_{d}$ and $X_{d}$ are random (centered) real-analytic functions on $D_{1}$.
Moreover,

  * •

For $z\in D_{1}$ and $d\geq 1$, we have

(2.4)
$\mathbb{E}\left[e^{-Y_{d}(z)}\right]=\bigg{(}\prod_{\ell\in\mathbb{N}}\mathrm{f}_{\ell}(z/\sqrt{d})^{\frac{d^{\ell}}{\ell}}\bigg{)}^{-1},$

where $\mathrm{f}_{\ell}(z):=(1-z^{\ell})e^{z^{\ell}}$. The infinite product
converges uniformly on compact sets of $D_{1}$.

  * •

For $d\geq 2$, $Y_{d}=X_{d}+\Upsilon_{d}$ where
$\mathbb{E}\left[\|\Upsilon_{d}\|_{L^{\infty}(D_{1})}^{2}\right]\leq
C/d^{1/4}$ for a numerical constant $C$. Moreover, $X_{d}$ has covariance
kernel

$\mathbb{E}[X_{d}(z)X_{d}(w)]=\log(1-zw)^{-1}$

and $Y_{d}$ has covariance kernel

$\mathbb{E}[Y_{d}(z)Y_{d}(w)]=\log(1-zw)^{-1}+O_{d}(1),\qquad z,w\in D_{1},$

where the error term is a bi-analytic function which converges to $0$
uniformly in $\overline{D_{1}\times D_{1}}$ as $d\to\infty$.

One can check that for $d\in\mathbb{R}_{+}\cup\\{\infty\\}$, the random series
$Y_{d}$ also converges in the Sobolev space of (Schwartz) distributions
$H^{-\epsilon}(\partial D_{1})$ of any $\epsilon>0$. In particular, for
$d\in\mathbb{N}$, $\big{(}Y_{d}(z):z\in\partial D_{1}\big{)}$ defines a non-
Gaussian log-correlated field. From this perspective, it is natural to ask for
the asymptotics of the modulus of the limits in Theorems 2.4-2.6. Since
$|\mathrm{e}^{z}|=\mathrm{e}^{\Re z}$, it is thus natural to study, for
instance111$\big{(}Y_{d}(z):z\in D_{1}\big{)}$ is the harmonic extension of
the log-correlated field inside the disk and this is a natural way to
regularize this random generalized function. An alternative approach consists
in truncating the Fourier series (2.2), considering the asymptotics of the
maximum of $\Re\big{(}\sum_{k\leq
N}\frac{z^{k}}{kd^{k/2}}\sum_{\ell|k}\ell\overline{\Lambda_{\ell}}\big{)}$ as
$N\to\infty$. Theorem 2.4 shows that yet another regularization is given by
the log characteristic polynomial $\log|\widehat{\chi}_{n}(z)|$ (after the
appropriate centering). These procedures are expected to be all equivalent.,
the behaviour of $\max_{|z|=r}\Re Y_{d}(z)$ as $r\to 1$.

If $d=1$, the leading order of the maximums of $Y_{d}$ and
$\log|\widehat{\chi}_{n}|$ have been studied in [16]; specifically, it was
shown that $\max_{z\in\partial D_{1}}\log|\widehat{\chi}_{n}|\sim x_{0}\log n$
as $n\to\infty$ where $x_{0}\simeq 0.652$. The significance of this result is
that the usual prediction for the value of $x_{0}$ coming from the theory of
log-correlated fields [27] does not apply to this problem and this is due to
the tails of the field $\log|\widehat{\chi}_{n}|$ which are not Gaussian. A
similar and more accessible question is the maximum of the characteristic
polynomial of the CUE (circular unitary ensemble or Haar-distributed random
matrices over the group U$(n)$). This problem has been thoroughly considered
and precise results about the asymptotics of the maximum are available [28, 1,
46, 13, 36]. We intend to consider the asymptotics for maximum of $Y_{d}$ and
the leading order of that of $\log|\widehat{\chi}_{n}|$ for general $d$ in
subsequent work. Another perspective is that
$|\widehat{\chi}_{n}(z)|^{\gamma}\mathrm{d}z$ appropriately renormalized
should converge to a multiplicative chaos222According to Theorem 2.6, the
limiting random measures should be Gaussian multiplicative chaos (GMC) only in
the regime as $d(n)\to\infty$. For fixed $d$, we still expect that the
limiting random measures have similar multi-fractal properties [24]. measure
as $n\to\infty$ for $\gamma>0$ sufficiently small (in the subcritical phase).
In contrast to the CUE characteristic polynomial [45], it is not clear whether
the critical value is the standard $\gamma=\sqrt{2}$ for this model or if it
depends on the degree $d$.

One can also investigate the regularity of the random (Schwartz) distributions
$\big{(}e^{\sqrt{\theta}Y_{d}(z)}:z\in\partial D_{1}\big{)}$ depending on
$\theta>0$. This question has just been considered in the CUE case333The
results of [13, 36, 44] are valid for general circular $\beta$-ensembles. in
[44] (for the so-called _holomorphic multiplicative chaos_) which exhibits a
phase transition related to the asymptotics for the maximum of the CUE field.
In summary, these are fascinating research questions which motivates the study
of characteristic polynomials of permutation matrices and the corresponding
limiting random fields.

Finally, we relate the Gaussian analytic function in (2.3) with the $Y_{d}$
and $X_{d}$ defined before. It is well known that $X_{\infty}$ is an analytic
function over $D_{1}$ with covariance kernel

$\mathbb{E}[X_{\infty}(z)X_{\infty}(w)]=\log(1-zw)^{-1},\qquad z,w\in D_{1}.$

Thanks to the second point in Proposition 2.7, we have the following
convergence result.

######  Proposition 2.8.

With the notation of Proposition 2.7, it holds for the topology of locally
uniform convergence on $D_{1}$,

$(X_{d},\Upsilon_{d})\xrightarrow[d\to\infty]{\mathrm{law}}(X_{\infty},0).$

In particular,

$Y_{d}\xrightarrow[d\to\infty]{\mathrm{law}}X_{\infty}.$

The proofs of Propositions 2.7 and 2.8 will be given in Section 7. We also
refer to [19, Section 2.3] for the computation of the generating function of
the exponential moments of $Y_{d}$.

###  2.3. On fluctuations outside the support of the oriented Kesten-McKay
density

The empirical spectral density of sums of $d$ random permutation matrices or
random $d$-regular digraphs is conjectured to converge towards the oriented
Kesten-McKay law, whose density with respect to the Lebesgue measure on
$\mathbb{C}$ is

$\varrho_{d}(z)=\frac{d^{2}(d-1)}{\pi}\frac{\mathbf{1}_{|z|<\sqrt{d}}}{(d^{2}-|z|^{2})^{2}}.$

The reader will find many insights regarding this problem in [14, 42]. The
measure $\varrho_{d}$ is the Brown measure for the free sum of $d$ Haar
unitary operators, and the oriented Kesten-McKay law was established in [6]
for sums of $d$ independent Haar unitary or orthogonal matrices. Our main
result gives some information on the fluctuations around this law, in the
spirit of [49, lambert2020maximum]. The log-potential fluctuations around the
oriented Kesten-McKay distribution are defined as the function

$\Psi_{n}(z)=\log|\det(zI_{n}-A_{n})|-nU_{d}(z),$

where $U_{d}$ is the Log-potential of $\varrho_{d}$, that is
$U_{d}(z)=\int\log|z-x|\varrho_{d}(x)\mathrm{d}x$. Indeed, it can be checked
by a direct computation that

(2.5) $U_{d}(z)=\begin{cases}\log|z|~{}~{}~{}~{}\text{ for }|z|>\sqrt{d},\\\
-(d-1)\log\sqrt{d^{2}-|z|^{2}}+\alpha_{d}\text{ for
}|z|\leqslant\sqrt{d}\end{cases}$

where $\alpha_{d}=(d-1)\log\sqrt{1-d^{-1}}+(d-1/2)\log(d)$.

As a consequence, for every $|z|>\sqrt{d}$, the fluctuations are given by
$\Psi_{n}(z)=\log|\det(I-z^{-1}A_{n})|$ since the $n\log|z|$ terms cancel in
$\Psi_{n}$. Our main result, Theorem 2.4, identifies the limit of the
fluctuations $\Psi_{n}$ outside the disk $D_{\sqrt{d}}$. In figure 1 depicting
$\Psi_{n}$, this corresponds to the smooth part of the picture. The rough part
corresponds to the fluctuations inside the bulk of the oriented Kesten-McKay
density; it is not clear what is going to be the correct definition of this
generalized function.

|
---|---
Figure 1. Picture of the values of $\log|\det(z-A_{n})|-nU_{d}(z)$ for $z$ in
$[-5,5]^{2}$, from two different angles; here, $A_{n}$ is a sum of $3$ uniform
permutation matrices, $n=2000$ and $U_{d}$ is the Log-potential (2.5). The
logarithmic singularity of $\Psi_{n}(z)$ at $z=d$ is visible in the smooth
(harmonic) part of the picture.

##  3\. Outline of the paper

###  3.1. Proof strategy

The proofs of Theorems 2.4 and 2.6 are given in Section 8. They are based on
the following three steps strategy;

  * (i)

If $(d(n))_{n\in\mathbb{N}}$ is a sequence of degree such that
$d(n)=o(\sqrt{n})$, then the family of random analytic function
$\\{\widehat{\chi}_{n}(z):z\in D_{1}\\}_{n\in\mathbb{N}}$ is tight for the
topology of locally uniform convergence on $D_{1}$; cf. Section 4.1 at page
4.1.

  * (ii)

By expanding (2.1), for the principal branch of $\log$, it holds for
$k\in\mathbb{N}$ that

(3.1)
$[z^{k}]\log\bigg{(}\frac{\widehat{\chi}_{n}(z)}{z-1/\sqrt{d}}\bigg{)}=\frac{(-1)^{k+1}}{k}\frac{\mathrm{tr}(A^{k})-d^{k}}{d^{k/2}},$

where $[z^{k}]f(z)$ means the $k$-th coefficient of the analytic function
$f(z)$. Note that it is natural to consider $\log$ of
$z\mapsto\frac{\widehat{\chi}_{n}(z)}{z-1/\sqrt{d}}$ to account for the
trivial root of $\widehat{\chi}_{n}$ at $1/\sqrt{d}\in D_{1}$ if $d\geq 2$. We
establish that

$\frac{\mathrm{tr}(A^{k})-d^{k}}{d^{k/2}}\xrightarrow[n\to\infty]{\mathrm{law}}L_{k}$

in the sense of finite dimensional distributions for a sequence of independent
random variables $(L_{k})_{k\in\mathbb{N}}$. This is the content of Theorem
3.1 thereafter, which is proved in Section 6 at page 6.

  * (iii)

Suppose that $\sum_{k\in\mathbb{N}}|L_{k}|r^{k}$ converges for any $r<1$
almost surely. From (i) tightness and (ii) we conclude that the random
analytic function

$\bigg{(}\frac{\widehat{\chi}_{n}(z)}{z-1/\sqrt{d}}\bigg{)}\xrightarrow[n\to\infty]{\mathrm{law}}\exp\bigg{(}\sum_{k\in\mathbb{N}}\frac{(-1)^{k+1}}{k}L_{k}z^{k}\bigg{)}$

in the topology of locally uniform convergence on $D_{1}$; cf. Section 8.

Step (ii) consists in a standard application of the trace method, without
resorting to high traces. The main result is the following one.

######  Theorem 3.1.

  1. (1)

Suppose that $d\in\mathbb{N}$ is fixed and
$\\{\Lambda_{\ell}\\}_{\ell\in\mathbb{N}}$ be as in Definition 2.3. Then for
every $k\in\mathbb{N}$,

(3.2)
$\big{(}\mathrm{tr}(A),\dotsc,\mathrm{tr}(A^{k})\big{)}\xrightarrow[n\to\infty]{\mathrm{law}}\bigg{(}\Lambda_{1},\dotsc,\sum_{\ell|k}\ell\Lambda_{\ell}\bigg{)}.$

  2. (2)

Consider a sequence $d(n)\in\mathbb{N}$ such that $d(n)\to\infty$ and
$d(n)=n^{o(1)}$ as $n\to\infty$. Then for every $k\in\mathbb{N}$,

(3.3)
$\displaystyle\left(\frac{\mathrm{tr}(A)-d}{\sqrt{d}},\dotsc,\frac{\mathrm{tr}(A^{k})-d^{k}}{\sqrt{d^{k}}}\right)\xrightarrow[n\to\infty]{\mathrm{law}}\left(N_{1},\sqrt{2}N_{2}+1,\dotsc,\sqrt{k}N_{k}+\mathbf{1}_{\\{k\text{
is even}\\}}\right).$

The proof of Theorem 3.1 relies on the relationship between the random
variables $\mathrm{tr}(A^{k})$ and $k$-cycles on the (adjacency) digraph
associated to the matrix $A$ – note that $A$ is generically non-Hermitan, and
$d$ is the degree of the regular digraph. The argument proceeds by the moment
method, estimating the probabilities to observe some given collection of
cycles for large $n$.

######  Remark 3.2.

Theorem 3.1 yields the fluctuations of linear statistics
$\sum_{i=1}^{n}[f(\lambda_{i})-\mathbb{E}f(\lambda_{i})]$ for any (analytic)
polynomial $f$, where $\lambda_{1},\dots,\lambda_{n}$ are eigenvalues of
$A/\sqrt{d}$. To study the fluctuations of linear statistics for general
smooth test function with the moment method, one needs to extend the results
to polynomials in $z$ and $\overline{z}$. This approach was developed in [49]
for the Ginibre ensemble.

###  3.2. Notational preliminaries

We never indicate that $d$ and the random variables defined in terms of $A$
depend on $n$=size($A$). We always consider limits as $n\to\infty$.

_Sets._ For any $k\in\mathbb{N}$, denote $[k]=\\{1,\dotsc,k\\}$. If
$I\subset\mathbb{N}$ is a finite set, we denote by $S_{I}$, the group of
permutations of elements in $I$. For $\sigma\in S_{I}$, we let
$\epsilon(\sigma)$ be the sign of this permutation. If $I$ is a finite set, we
denote by $|I|$ its cardinal (number of elements). Tuples are denoted by
boldface letters. If $I\subseteq\mathbb{N}$ is a set, then

$I^{k}=\\{\mathbf{i}=(i_{1},\dots,i_{k}):i_{1},\dots,i_{k}\in I\\}$

for $k\in\mathbb{N}$. For $k\in\mathbb{N}$, we denote

$\mathcal{E}_{k}=\\{\mathbf{i}\in[n]^{k}:i_{1},\dots,i_{s}\text{ are
distinct}\\}.$

_Matrices._ In the sequel $A=(A_{i,j})_{i,j\in[n]}$ is a random matrix and we
denote for any multi-index $\mathbf{i}\in[n]^{k}$,

$A_{\mathbf{i}}:=A_{i_{1},i_{2}}\dotsb A_{i_{k-1},i_{k}}A_{i_{k},i_{1}}.$

With this notation,

$\mathrm{tr}(A^{k})=\sum_{\mathbf{i}\in[n]^{k}}A_{\mathbf{i}}.$

For any subset $I\subset[n]$, we denote $A(I)=(A_{i,j})_{i,j\in I}$ the
corresponding submatrix.

_Directed graphs._ The matrix $A$ is an $n\times n$ matrix with integer
entries. It represents the adjacency matrix of a (weighted) digraph, on the
vertex set $V=[n]$. The edge set is $E=\\{(i,j)\in[n]\times[n]:A_{i,j}\geq
1\\}$ and the weights correspond to the entries of $A$. We insist on the fact
that $G_{A}=(V,E)$ is directed and possibly has simple loops. We can interpret
$\mathbf{i}\in[n]^{k}$ as _cyclic paths_ on the graph of $A$ and
$A_{\mathbf{i}}$ as the _weight_ of this path. In addition, the paths
$\mathbf{i}\in\mathcal{E}_{k}$ correspond to simple loops.

_Random permutation._ We define a random permutation matrix
$P=(\mathbf{1}_{\pi(i)=j})_{i,j\in[n]}$, where $\pi$ is a uniform random
element of $S_{[n]}$. We will use that under this law, for any $k\in[n]$, any
$\mathbf{i},\mathbf{j}\in\mathcal{E}_{k}$,

$\mathbb{P}[\pi(i_{1})=j_{1},\dotsc,\pi(i_{k})=j_{k}]=\mathbb{P}[P_{i_{1},j_{1}}=\cdots=P_{i_{k},j_{k}}=1]=\frac{(n-k)!}{n!}.$

We will also make several use of the following bounds; for any
$d\in\mathbb{N}$, if $\mathbf{k}\in\mathbb{N}^{d}$ with
$k_{1}+\cdots+k_{d}=k\leq n$, then

(3.4) $\prod_{\delta=1}^{d}\frac{(n-k_{\delta})!}{n!}\leq\frac{(n-k)!}{n!}.$

##  4\. Tools for proving the tightness of $\\{\chi_{n}\\}$

###  4.1. A simple tightness criterion

A family of analytic function $\\{f_{n}\\}$ on a domain $D\subset\mathbb{C}$
is pre-compact (or normal) for the topology of locally uniform convergence if
for any compact $K\subset D$,

$\sup_{n}\|f_{n}\|_{L^{\infty}(K)}<\infty.$

In particular, from Definition 2.2, $\\{f_{n}\\}$ is tight (in this topology)
if for any compact $K\subset D$,

$\big{\\{}\|f_{n}\|_{L^{\infty}(K)}\big{\\}}\text{ is tight.}$

In particular, it suffices to check that for $\alpha>0$

(4.1)
$\displaystyle\sup_{n}\mathbb{E}\|f_{n}\|_{L^{\infty}(K)}^{\alpha}<\infty.$

We will use this criterion to show that the characteristic polynomial of a
random $n\times n$ matrix $A$,

$\big{\\{}\chi_{n}=\det(I+\cdot A)\big{\\}}$

forms a tight sequence in a disk $D_{r}=\\{|z|<r\\}$. Note that the random
matrices $A$ need not be defined on the same probability spaces for different
$n\in\mathbb{N}$. Recall that for $z\in\mathbb{C}$,

$\chi_{n}(z)=\sum_{k\leq n}z^{k}\Delta_{k}^{(n)},$

where $\Delta_{k}$ are called secular coefficients and are given by
$\Delta_{0}=1$,

(4.2)
$\displaystyle\Delta_{k}^{(n)}=\sum_{I\subseteq[n],|I|=k}\det(A(I)),\qquad
k\in[n].$

For any $\theta<1$, $r>0$ and $\epsilon>0$, by Jensen’s inequality, it holds

$\mathbb{E}\|\chi_{n}\|_{L^{\infty}(D_{r\theta})}^{1+\epsilon}\leq\mathbb{E}\bigg{(}\sum_{k\leq
n}r^{k}\theta^{k}|\Delta_{k}^{(n)}|\bigg{)}^{1+\epsilon}\leq\frac{1}{(1-\theta)^{\epsilon}}\sum_{k\leq
n}r^{k(1+\epsilon)}\mathbb{E}|\Delta_{k}^{(n)}|^{1+\epsilon}.$

With the normalization (2.1), by scaling and choosing $\epsilon=1$, it holds
for $r>0$ and $\theta<1$,

(4.3)
$\displaystyle\mathbb{E}\|\widehat{\chi}_{n}\|_{L^{\infty}(D_{r\theta})}^{2}\leq\frac{1}{1-\theta}\sum_{k\leq
n}\frac{r^{2k}}{d^{k+1}}\mathbb{E}|\Delta_{k}^{(n)}|^{2}.$

For the model $A=\sum_{q=1}^{d}P^{(q)}$ where $P^{(q)}$ are $d\in\mathbb{N}$
independent random permutation matrices, we will prove the following bound in
the sequel. For any $n\geq 2$, it holds for all $0<r<1$ and $1\leq
d<\sqrt{\frac{n(1-r)}{r}}$,

(4.4) $\displaystyle\sum_{k\leq
n}\frac{r^{k}}{d^{k+1}}\mathbb{E}|\Delta_{k}^{(n)}|^{2}\leq\frac{\frac{2}{d}+r}{(1-r-\frac{rd^{2}}{n})^{2}}.$

(4.1), (4.3), and (4.4) immediately imply the following result.

######  Proposition 4.1.

For any sequence $d(n)\in\mathbb{N}$ with $d=o(\sqrt{n})$, the sequence of
random analytic function $(\widehat{\chi}_{n})_{n\in\mathbb{N}}$ admits a
subsequence which converges weakly locally uniformly on compact subset of
$D_{1}$.

###  4.2. Exchangeability

By (4.2), it holds for any $k\in[n]$

$\mathbb{E}\Delta_{k}^{2}=\sum_{|I|,|J|=k}\mathbb{E}\det(A(I))\det(A(J)).$

where the sum is over all subsets $I,J\subseteq[n]$. Lemma 4.3 below allows to
reduce this sum to subsets $(I,J)$ which share at least $k-1$ elements;

(4.5)
$\mathbb{\mathbb{E}}\Delta_{k}^{2}=\sum_{|I|=k}\mathbb{E}\det(A(I))^{2}+\sum_{|I|=|J|=k,|I\cap
J|=k-1}\mathbb{E}\det(A(I))\det(A(J)).$

The Lemmas of this section apply to any exchangeable random matrix model, that
is, if the following invariance property holds; for any given permutation
$\pi\in S_{[n]}$,

(4.6) $\big{(}A_{i,\pi(j)}\big{)}_{i,j\in[n]}\overset{\rm
law}{=}\big{(}A_{\pi(i),j}\big{)}_{i,j\in[n]}\overset{\rm
law}{=}\big{(}A_{i,j}\big{)}_{i,j\in[n]}.$

######  Lemma 4.2.

For any $k\in[n]$,

$\mathbb{E}\Delta_{k}^{(n)}=\mathbf{1}_{k=1}\mathbb{E}\mathrm{tr}A.$

In particular, for the random matrix $A=\sum_{q=1}^{d}P^{(q)}$, we have
$\mathbb{E}\Delta_{1}^{(n)}=d$.

###### Proof.

By (4.2), it holds for any $k\in[n]$

$\mathbb{E}\Delta_{k}=\sum_{|I|=k}\mathbb{E}\det(A(I)).$

If the random matrix $A$ satisfies (4.6), observe that by permuting two
columns of $A$, $\mathbb{E}\det(A(I))=-\mathbb{E}\det(A(I))$, hence
$\mathbb{E}\det(A(I))=0$ for any $I\subset[n]$ provided that $|I|\geq 2$. This
shows that $\mathbb{E}\Delta_{k}=0$ for all $k\geq 2$ and

$\mathbb{E}\Delta_{1}=\sum_{i\in[n]}\mathbb{E}A_{i,i}=\mathbb{E}\mathrm{tr}A.\qed$

######  Lemma 4.3.

Assume $|I|=|J|=k$. If $|I\cap J|\leq k-2$, then
$\mathbb{E}\det(A(I))\det(A(J))=0$.

###### Proof.

For ease of notation, we consider the case when $|I\cap J|=k-2$. Other cases
follow in the same way. Let us denote $\\{x,y\\}=I\setminus J$. Given
$\sigma\in S_{I},\tau\in S_{J}$, using the invariance in law (4.6) applied to
$\pi=(xy)$, we have

$\displaystyle\mathbb{E}\left[\prod_{i\in I,j\in
J}A_{i,\sigma(i)}A_{j,\tau(j)}\right]=\mathbb{E}\left[\prod_{i\in I,j\in
J}A_{i,\sigma^{\prime}(i)}A_{j,\tau(j)}\right]$

where $\sigma^{\prime}=\sigma\circ\pi$. Note that we used that
$\tau\circ\pi=\tau$ since $x,y\notin J$. Since the map
$\sigma\to\sigma^{\prime}=\sigma\circ\pi$ is a bijection on $S_{I}$ with the
property that $\epsilon(\sigma^{\prime})=-\epsilon(\sigma)$, by summing over
all $\sigma\in S_{I}$, this implies that for any fixed $\tau\in S_{J}$,

$\displaystyle\sum_{\sigma\in
S_{I}}\epsilon(\sigma)\epsilon(\tau)\mathbb{E}\left[\prod_{i\in I,j\in
J}A_{i,\sigma(i)}A_{j,\tau(j)}\right]=0.$

Summing over $\tau\in S_{J}$ gives the desired result. ∎

From Lemma 4.3, identity (4.5) holds.

##  5\. Analysis for the simple case of a single permutation

When $d=1$, the matrix $A$ is indeed the permutation matrix of a uniform
permutation of $[n]$ and the analysis is easier to perform. We include this
special case because it gives all the ideas for the general proof.

###  5.1. Tightness of the determinants

When $d=1$, this reduces to the study of random permutation matrix. In this
case we can calculate the second moment of secular coefficients exactly.

######  Lemma 5.1.

For all $1\leq k\leq n-1$,

(5.1) $\displaystyle\mathbb{E}|\Delta_{k}|^{2}=2,$

and

$\displaystyle\mathbb{E}|\Delta_{n}|^{2}=1.$

###### Proof.

Let $\pi\in S_{n}$ be a uniform random permutation and $A$ be the permutation
matrix of $\pi$. By Lemma 4.3, we only need to evaluate

$\displaystyle\sum_{|I|=k}\mathbb{E}\det(A(I)^{2})+\sum_{|I|=|J|=k,|I\cap
J|=k-1}\mathbb{E}\det A(I)A(J).$

The summation in the second term is non-empty if and only if $k<n$. For the
first term,

$\displaystyle\mathbb{E}\det(A(I)^{2})$ $\displaystyle=\sum_{\sigma,\tau\in
S(I)}\epsilon(\sigma)\epsilon(\tau)\mathbb{E}\prod_{i\in
I}A_{i,\sigma(i)}A_{i,\tau(i)}$
$\displaystyle=\sum_{\sigma,\tau}\epsilon(\sigma)\epsilon(\tau)\mathbb{P}\left(\pi(i)=\sigma(i)=\tau(i),\forall
i\in I\right)$
$\displaystyle=\sum_{\sigma}\mathbb{P}\left(\pi(i)=\sigma(i),\forall i\in
I\right)=\mathbb{P}(\pi:I\to I)=\frac{k!(n-k)!}{n!}=\frac{1}{\binom{n}{k}},$

where $\pi:I\to I$ is the event that $\pi$ restricted on $I$ is a permutation
on $I$. Hence

$\displaystyle\sum_{|I|=k}\mathbb{E}\det(A(I)^{2})=1.$

By taking $k=n$, it gives $\mathbb{E}[|\Delta_{n}|^{2}]=1$.

For the second term, with the assumption $|I|=|J|=k,|I\cap J|=k-1$,

$\displaystyle\mathbb{E}\det A(I)A(J)$ $\displaystyle=\sum_{\sigma\in
S(I),\tau\in S(J)}\epsilon(\sigma)\epsilon(\tau)\mathbb{E}\prod_{i\in
I}A_{i,\sigma(i)}\prod_{j\in J}A_{j,\tau(j)}$ $\displaystyle=\sum_{\sigma\in
S(I),\tau\in
S(J)}\epsilon(\sigma)\epsilon(\tau)\mathbb{P}(\pi(i)=\sigma(i),i\in
I,\pi(j)=\tau(j),j\in J)$

Without loss of generality, we assume $I=\\{1,\dots,k\\},J=\\{2,\dots,k+1\\}$.
To have a non-zero probability, we must have $\sigma(i)=\tau(i)$ for all $i\in
I\cap J$. This forces $\sigma,\tau$ to be two permutations on $I\cap J$, and
$\sigma(1)=1,\tau(k+1)=k+1$. Let

$\Omega=\\{(\sigma,\tau)\in S(I)\times
S(J):\sigma(1)=1,\tau(k+1)=k+1,\sigma(k)=\tau(k),\forall k\in I\cap J\\}.$

For any $(\sigma,\tau)\in\Omega$, both permutations have the same cycle types,
hence $\epsilon(\sigma)=\epsilon(\tau)$. Therefore

$\displaystyle\mathbb{E}\det A(I)A(J)$
$\displaystyle=\sum_{(\sigma,\tau)\in\Omega}\mathbb{P}(\pi(i)=\sigma(i),i\in
I,\pi(j)=\tau(j),j\in J)$
$\displaystyle=\mathbb{P}(\pi(1)=1,\pi(k+1)=k+1,\pi:\\{2,\dots,k\\}\to\\{2,\dots,k\\})$
$\displaystyle=\frac{(k-1)!(n-k-1)!}{n!}.$

Since $\\#\big{\\{}I,J\subset[n]:|I|=|J|=k,|I\cap
J|=k-1\big{\\}}=\binom{n}{k}k(n-k)$, we conclude that

$\sum_{|I|=|J|=k,|I\cap J|=k-1}\mathbb{E}\det
A(I)A(J)=\binom{n}{k}\frac{k!(n-k)!}{n!}=1.$

∎

###  5.2. Probability estimates for one random uniform permutation

Recall that in case $d=1$, $A=P=(\mathbf{1}_{\pi(i)=j})_{i,j\in[n]}$ where
$\pi$ is a uniform random element of $S_{[n]}$. We start by giving an estimate
on the probability of generic events. Recall that for $s\in\mathbb{N}$, we
denote

$\mathcal{E}_{s}=\\{\mathbf{i}\in[n]^{s}:i_{1},\dots,i_{s}\text{ are
distinct}\\}.$

######  Proposition 5.2.

Let $r,s\in\mathbb{N}_{0}$ with $r+s<n$ and fix
$\mathbf{i},\mathbf{j}\in\mathcal{E}_{s}$ such that
$(i_{1},j_{1}),\cdots,(i_{r},j_{r})$ are distinct, and
$\mathbf{k},\mathbf{q}\in[n]^{r}$. Assume

(5.2)
$\big{\\{}(k_{1},q_{1}),\cdots,(k_{r},q_{r})\big{\\}}\cap\big{\\{}(i_{1},j_{1}),\cdots,(i_{s},j_{s})\big{\\}}=\emptyset.$

Then there exists $0\leq\varepsilon\leqslant\frac{r}{n-s}$ such that

(5.3)
$\mathbb{P}\big{(}P_{i_{1},j_{1}}=\dotsc=P_{i_{s},j_{s}}=1,P_{k_{1},q_{1}}=\dotsc=P_{k_{r},q_{r}}=0\big{)}=(1-\varepsilon)\frac{(n-s)!}{n!}.$

Otherwise, if $\mathbf{i}\notin\mathcal{E}_{s}$, or
$\mathbf{j}\notin\mathcal{E}_{s}$, or the condition (5.2) fails, then the
probability on the LHS of (5.3) equals $0$.

###### Proof.

Under the hypothesis (5.2), we have the upper-bound

$\mathbb{P}\big{(}P_{i_{1},j_{1}}=\dotsc=P_{i_{s},j_{s}}=1,P_{k_{1},q_{1}}=\dotsc=P_{k_{r},q_{r}}=0\big{)}\leq\mathbb{P}\begin{pmatrix}\pi(i_{1})=j_{1},\dotsc,\pi(i_{s})=j_{s}\end{pmatrix}=\frac{(n-s)!}{n!}$

valid for any $\mathbf{i},\mathbf{j}\in\mathcal{E}_{s}$. For the lower-bound,
we may assume that $k_{1},\dots,k_{r}\notin\mathbf{i}$ and
$q_{1},\dots,q_{r}\notin\mathbf{j}$. Otherwise, there are less constraints and
the probability of the event in question is larger. In this case, using the
invariance (4.6) of the uniform measure on $S_{[n]}$, we can write

$\mathbb{P}\begin{pmatrix}P_{i_{1},j_{1}}=\dotsc=P_{i_{s},j_{s}}=1\\\
P_{k_{1},q_{1}}=\dotsc=P_{k_{r},q_{r}}=0\end{pmatrix}=\frac{(n-s)!}{n!}\mathbf{Q}\begin{pmatrix}\pi(1)\neq
1,\dotsc,\pi(r)\neq r\end{pmatrix}$

where $\mathbf{Q}$ is the uniform measure on $S_{[n-s]}$. In particular, we
have the simple lower-bound

$\mathbf{Q}\begin{pmatrix}\pi(1)\neq 1,\dotsc,\pi(r)\neq r\end{pmatrix}\geq
1-r\mathbf{Q}\big{(}\pi(1)=1\big{)}=1-\frac{r}{n-s}.$

This proves the claim. ∎

##  6\. The general case: tightness and trace asymptotics

###  6.1. Proving the tightness of the sequence $(\chi_{n})$ with the second
moment argument

In the case of a sum of $d>1$ permutations, proving the tightness of
$(\chi_{n})$ using the criteria given in Subsection 4.1 is more involved and
necessitates a detailed technical analysis of the determinant expansion of
$I-zA$. We recall that $A=\sum_{q=1}^{d}P^{(q)}$, where $P^{(q)},q\in[d]$ are
$n\times n$ independent random permutation matrices. The subsequent
computations crucially rely on the exchangeability of $A$ as in (4.6).

######  Lemma 6.1.

For any $n\geq 2$, it holds for all $0<r<1$ and $1\leq
d<\sqrt{\frac{n(1-r)}{r}}$,

$\sum_{k\geq
1}\frac{r^{k}}{d^{k}}\sum_{|I|=k}\mathbb{E}\det(A(I)^{2})\leq\frac{2}{1-r-\frac{rd^{2}}{n}}.$

###### Proof.

First observe that

$\sum_{|I|=k}\mathbb{E}\det(A(I)^{2})=\sum_{|I|=k}\sum_{\sigma,\tau\in
S(I)}\epsilon(\sigma)\epsilon(\tau)\mathbb{E}\prod_{i\in
I}A_{i,\sigma(i)}\prod_{j\in I}A_{j,\tau(j)}.$

Then, by symmetry of the permutation model,

(6.1) $\displaystyle\sum_{|I|=k}\mathbb{E}\det(A(I)^{2})$
$\displaystyle=\binom{n}{k}\sum_{\sigma,\tau\in
S_{k}}\epsilon(\sigma)\epsilon(\tau)\prod_{i\in[k]}\mathbb{E}A_{i,\sigma(i)}A_{i,\tau(i)}$
$\displaystyle=\binom{n}{k}\sum_{\sigma,\tau\in
S_{k}}\epsilon(\sigma^{-1}\tau)\mathbb{E}\prod_{i\in[k]}A_{i,i}A_{i,\sigma^{-1}\tau(i)}$
$\displaystyle=\binom{n}{k}k!\sum_{\tau\in
S_{k}}\epsilon(\tau)\mathbb{E}\prod_{i\in[k]}A_{i,i}A_{i,\tau(i)}$
$\displaystyle=\frac{n!}{(n-k)!}\sum_{q_{1},\dots,q_{k}\in[d]}\sum_{\ell_{1},\dots,\ell_{k}\in[d]}\sum_{\tau\in
S_{k}}\epsilon(\tau)\mathbb{E}\prod_{i\in[k]}P_{ii}^{(q_{i})}P_{i\tau(i)}^{(\ell_{i})}.$

where we used (4.6) to obtain (6.1). Observe that for any fixed
$q,\ell\in[d]^{k}$ and all $i\in[k]$, if $q_{i}=\ell_{i}$ then

$P_{i,i}^{(q_{i})}P_{i,\tau(i)}^{(\ell_{i})}=P_{i,i}^{(q_{i})}\mathbf{1}\\{\tau(i)=i\\},$

and using independence,

$\displaystyle\mathbb{E}\prod_{i\in[k]}P_{ii}^{(q_{i})}P_{i\tau(i)}^{(\ell_{i})}$
$\displaystyle=\prod_{r\in[d]}\mathbb{E}\bigg{[}\prod_{i:q_{i}=r}P_{ii}\prod_{i:\ell_{i}=r}P_{i\tau(i)}\bigg{]}$
$\displaystyle=\prod_{r\in[d]}\mathbf{1}\big{\\{}\tau(i)=i;\forall
i\in\\{q_{i}=\ell_{i}=r\\}\big{\\}}\mathbb{E}\bigg{[}\prod_{i:q_{i}=r}P_{ii}\prod_{i\in
K_{r}}P_{i\tau(i)}\bigg{]}$

where $K_{r}=K_{r}(\ell,q)=\\{i:\ell_{i}=r,\ q_{i}\neq r\\}$. Let
$K=K(\ell,q)=\\{i:q_{i}\neq\ell_{i}\\}=\bigcup_{r=1}^{d}K_{r}$ (disjoint) and
for $r\in[d]$,

$\Theta_{r}(\tau)=\mathbb{E}\bigg{[}\prod_{i:q_{i}=r}P_{ii}\prod_{i\in
K_{r}}P_{i\tau(i)}\bigg{]}\mathbf{1}\big{\\{}\tau(i)\notin\\{i:q_{i}=r\\};\forall
i\in K_{r}\big{\\}}.$

This implies that

(6.2) $\sum_{\tau\in
S_{k}}\epsilon(\tau)\mathbb{E}\prod_{i\in[k]}P_{ii}^{(q_{i})}P_{i\tau(i)}^{(\ell_{i})}=\sum_{\tau\in
S_{K}}\epsilon(\tau)\prod_{r\in[d]}\Theta_{r}(\tau).$

By (4.6), observe that for any permutation $\sigma\in S_{K}$ which fixes the
subsets $\\{K_{r}\\}_{r\in[d]}$,

$\prod_{r\in[d]}\Theta_{r}(\sigma\tau)=\prod_{r\in[d]}\Theta_{r}(\tau).$

Let

$\delta_{r}=\\#K_{r}=\\#\\{i:\ell_{i}=r,q_{i}\not=\ell_{i}\\}.$

If $\delta_{r}\geq 2$ for some $r\in[d]$, by a transposition, one has

$\sum_{\tau\in S_{K}}\epsilon(\tau)\prod_{r\in[d]}\Theta_{r}(\tau)=0.$

In particular, this shows that for any fixed $q,\ell\in[d]^{k}$,

$\bigg{|}\sum_{\tau\in
S_{K}}\epsilon(\tau)\prod_{r\in[d]}\Theta_{r}(\tau)\bigg{|}\leq\Delta!\prod_{r\in[d]}\mathbf{1}\big{\\{}\delta_{r}\in\\{0,1\\}\big{\\}}\frac{(n-\\#\\{i:q_{i}=r\\}-\delta_{r})!}{n!},\qquad\Delta=\sum_{r\in[d]}\delta_{r}=\\#K.$

Observe that for any integers $k_{1}\geq 1,k_{2}\geq 0$,
$\delta_{1},\delta_{2}\in\\{0,1\\}$,

(6.3)
$\displaystyle\frac{(n-k_{1}-\delta_{1})!}{(n-k_{1}-k_{2})!}\leq\begin{cases}\frac{n!}{(n-k_{2}-\delta_{2})!}\frac{1}{n^{\delta_{1}+\delta_{2}}},&\delta_{1}+\delta_{2}\leq
1,\\\
\frac{n!}{(n-k_{2}-\delta_{2})!}\frac{2}{n^{\delta_{1}+\delta_{2}}},&\delta_{1}=\delta_{2}=1.\end{cases}$

Let $k_{r}(q)=\\#\\{i:q_{i}=r\\}$. We have $k_{1}+\cdots+k_{r}=k$. By
symmetry, we can assume $k_{1}\geq 1$, and by induction, we obtain

$\displaystyle\prod_{r\in[d]}\frac{(n-k_{r}-\delta_{r})!}{n!}$
$\displaystyle\leq\frac{2}{n^{\delta_{1}+\delta_{2}}}\frac{(n-k_{1}-k_{2})!}{n!}\prod_{r\geq
3}\frac{(n-k_{r}-\delta_{r})!}{n!}$
$\displaystyle\leq\frac{(n-k)!}{n!}\frac{2}{n^{\Delta}}$

where $\Delta=\sum_{r\in[d]}\delta_{r}$. We conclude that

$\bigg{|}\sum_{\tau\in
S_{K}}\epsilon(\tau)\prod_{r\in[d]}\Theta_{r}(\tau)\bigg{|}\leq\frac{2\Delta!(n-k)!}{n!n^{\Delta}}\prod_{r\in[d]}\mathbf{1}\big{\\{}\delta_{r}\in\\{0,1\\}\big{\\}},\qquad\Delta=\sum_{r\in[d]}\delta_{r}=\\#K.$

Going back to (6.1), using formula (6.2), this argument shows that

$\displaystyle\sum_{|I|=k}\mathbb{E}\det(A(I)^{2})$ $\displaystyle\leq
2\sum_{q_{1},\dots,q_{k}\in[d]}\sum_{\ell_{1},\dots,\ell_{k}\in[d]}\frac{\Delta!}{n^{\Delta}}\prod_{r\in[d]}\mathbf{1}\big{\\{}\delta_{r}\in\\{0,1\\}\big{\\}}.$

For $\ell\in[d]^{k}$, let us denote $k_{r}=k_{r}(\ell)=\\#\\{i:\ell_{i}=r\\}$
for $r\in[d]$. Observe that given $k_{1},\dots,k_{r}$, there are
$\binom{k}{k_{1},\dots,k_{d}}$ many choices of $\ell\in[d]^{k}$, and for
$\delta\in\\{0,1\\}^{d}$, there are at most
$d^{\Delta}\prod_{r=1}^{d}k_{r}^{\delta_{r}}$ configurations $q\in[d]^{k}$
which contributes to the previous sum. Hence,

$\displaystyle\sum_{|I|=k}\mathbb{E}\det(A(I)^{2})$ $\displaystyle\leq
2\sum_{k_{1},\dots,k_{d}\geq
0}\binom{k}{k_{1},\cdots,k_{d}}\sum_{\delta_{1},\dots,\delta_{d}\in\\{0,1\\}}\prod_{r\in[d]}\bigg{(}\frac{k_{r}d^{2}}{n}\bigg{)}^{\delta_{r}}$
$\displaystyle=2\sum_{k_{1},\dots,k_{d}\geq
0}\binom{k}{k_{1},\cdots,k_{d}}\prod_{r\in[d]}\bigg{(}1+\frac{k_{r}d^{2}}{n}\bigg{)}$
(6.4)
$\displaystyle=2d^{k}\big{(}1+\tfrac{d}{n}\partial_{x}\big{)}^{d}x^{k}\big{|}_{x=1}.$

The last identity follows from the fact that the second display equals (up to
a factor 2)

$\displaystyle\sum_{k_{1},\dots,k_{d}\geq
0}\binom{k}{k_{1},\cdots,k_{d}}\prod_{r\in[d]}\big{(}1+\epsilon\partial_{x}\big{)}x^{k_{r}}\big{|}_{x=1}$
$\displaystyle=\prod_{r\in[d]}\big{(}1+\epsilon\partial_{x_{r}}\big{)}\bigg{(}\sum_{k_{1},\dots,k_{d}\geq
0}\binom{k}{k_{1},\cdots,k_{d}}\prod_{r\in[d]}x_{r}^{k_{r}}\bigg{)}\bigg{|}_{x_{r}=1}$
$\displaystyle=\prod_{r\in[d]}\big{(}1+\epsilon\partial_{x_{r}}\big{)}\big{(}x_{1}+\cdots+x_{r}\big{)}^{k}\big{|}_{x_{1}=\cdots=x_{r}=1}$
$\displaystyle=\big{(}1+\epsilon\partial_{x}\big{)}^{d}x^{k}\big{|}_{x=d}$
$\displaystyle=d^{k}\big{(}1+\tfrac{\epsilon}{d}\partial_{x}\big{)}^{d}x^{k}\big{|}_{x=1}$

by scaling, and taking $\epsilon=d^{2}/n$. By summing over all
$k\in\mathbb{N}_{0}$, we conclude that for any $0<r<1$,

$\displaystyle\sum_{k\in\mathbb{N}}\frac{r^{k}}{d^{k}}\sum_{|I|=k}\mathbb{E}\det(A(I)^{2})$
$\displaystyle\leq
2\big{(}1+\tfrac{d}{n}\partial_{x}\big{)}^{d}\frac{1}{1-xr}\bigg{|}_{x=1}$
$\displaystyle=2\sum_{\ell\geq
0}\binom{d}{\ell}\frac{d^{\ell}}{n^{\ell}}\partial_{x}^{\ell}\frac{1}{1-xr}\bigg{|}_{x=1}$
$\displaystyle\leq
2\sum_{\ell=0}^{d}\frac{d!}{(d-\ell)!}\frac{(dr)^{\ell}}{n^{\ell}}\frac{1}{(1-r)^{\ell+1}}$
$\displaystyle\leq\frac{2}{1-r}\sum_{\ell=0}^{\infty}\left(\frac{d^{2}r}{n(1-r)}\right)^{\ell}\leq\frac{2}{1-r}\cdot\frac{1}{1-\frac{d^{2}r}{n(1-r)}}=\frac{2}{1-r(1+\frac{d^{2}}{n})}.$

The previous sum converges if $\frac{d^{2}r}{n(1-r)}<1$. This completes the
proof. ∎

######  Lemma 6.2.

For any $n\geq 2,$ it holds for all $0<r<1$ and $1\leq
d<\sqrt{\frac{n(1-r)}{r}}$,

$\sum_{k\geq 1}\frac{r^{k}}{d^{k+1}}\bigg{|}\sum_{|I|=|J|=k,|I\cap
J|=k-1}\mathbb{E}\det
A(I)A(J)\bigg{|}\leq\frac{r}{(1-r-\frac{rd^{2}}{n})^{2}}.$

###### Proof.

Using the invariance (4.6) of the random matrix $A$, for $k\leq n-1$, we can
rewrite

(6.5) $\displaystyle\sum_{|I|=|J|=k,|I\cap J|=k-1}\mathbb{E}\det A(I)A(J)$
$\displaystyle=\binom{n}{k}k(n-k)\sum_{\begin{subarray}{c}\tau\in S_{k}\otimes
S_{1}\\\ \sigma\in S_{1}\otimes
S_{k}\end{subarray}}\epsilon(\sigma)\epsilon(\tau)\mathbb{E}\prod_{j=1}^{k}\prod_{i=2}^{k+1}A_{i,\sigma(i)}A_{j,\tau(j)}$

where $S_{k}\otimes S_{1}=\\{\tau\in S_{k+1}:\tau(k+1)=k+1\\}.$ and
$S_{1}\otimes S_{k}=\\{\sigma\in S_{k+1}:\sigma(1)=1\\}.$ Now (6.5) can be
written as

$\displaystyle=\binom{n}{k}k(n-k)\sum_{\begin{subarray}{c}\tau\in S_{k}\otimes
S_{1}\\\ \sigma\in S_{1}\otimes
S_{k}\end{subarray}}\epsilon(\sigma)\epsilon(\tau)\sum_{\ell_{1},\dots,\ell_{k}}\sum_{q_{2},\dots,q_{k+1}}\mathbb{E}\prod_{i=2}^{k+1}P_{i,\sigma(i)}^{(q_{i})}\prod_{j=1}^{k}P_{j,\tau(j)}^{(\ell_{j})}$
$\displaystyle=\binom{n}{k}k(n-k)\sum_{\ell_{1},\dots,\ell_{k}}\sum_{q_{2},\dots,q_{k+1}}\sum_{\begin{subarray}{c}\tau\in
S_{k}\otimes S_{1}\\\ \sigma\in S_{1}\otimes
S_{k}\end{subarray}}\epsilon(\sigma)\epsilon(\tau)\mathbf{1}_{\big{\\{}\tau(j)=\sigma(j),\forall
j\in[k]\setminus K\big{\\}}}\prod_{r\in[d]}\mathbb{E}\bigg{[}\prod_{i\geq
2:q_{i}=r}P_{i,\sigma(i)}\prod_{j\in K:\ell_{j}=r}P_{j\tau(j)}\bigg{]},$

where $K=K(\ell,q)=\\{j\in[k]:q_{j}\neq\ell_{j}\\}$. By convention $1\in K$
and by symmetry we may assume that $l_{1}=1$ and multiply the sum with an
extra factor $d$. Moreover, by the argument following (6.2), we must have for
all $r\in\\{2,\dots,d\\}$,

$\delta_{r}=\\#\\{j\in K:\ell_{j}=r\\}\in\\{0,1\\}$

for otherwise the sum over all permutation $\tau\in S_{k}$ yields 0 by a
transposition. Similarly, we must have

$\delta_{1}=\\#\\{j\in K:\ell_{j}=1\\}=1$

since $1\in K$. Then, for any configuration $q,\ell\in[d]^{k}$ with
$\ell_{1}=1$, following the argument in (6.3), it holds for any
$\sigma,\tau\in S_{k+1}$

$\displaystyle\prod_{r\in[d]}\mathbb{E}\bigg{[}\prod_{i\geq
2:q_{i}=r}P_{i,\sigma(i)}\prod_{j\in K:\ell_{j}=r}P_{j,\tau(j)}\bigg{]}$
$\displaystyle\leq\prod_{r\in[d]}\frac{(n-\\#\\{i\geq
2:q_{i}=r\\}-\delta_{r})!}{n!}$
$\displaystyle=\frac{(n-k_{1}-1)!}{n!}\prod_{r\geq
2}\frac{(n-k_{r}-\delta_{r})!}{n!}$
$\displaystyle\leq\frac{(n-k-1)!}{n!\,n^{\Delta}}$

where $\Delta=\sum_{r=2}^{d}\delta_{r}$ and $k_{r}=k_{r}(q)=\\#\\{i\geq
2:q_{i}=r\\}$ form a partition of $k$ for $r\in[d]$. Moreover, for any
$\Delta\leq d-1$ and any given $\sigma\in S_{1}\otimes S_{k}$,

$\\#\big{\\{}\tau\in S_{k}:\tau(j)=\sigma(j),\forall j\in[k]\setminus
K\big{\\}}\leq(\Delta+1)!\leq d^{\Delta},$

so that this argument shows that

$\displaystyle\binom{n}{k}k(n-k)\sum_{\ell_{1},\dots,\ell_{k}}\sum_{q_{2},\dots,q_{k+1}}\sum_{\begin{subarray}{c}\tau\in
S_{k}\otimes S_{1}\\\ \sigma\in S_{1}\otimes
S_{k}\end{subarray}}\epsilon(\sigma)\epsilon(\tau)\mathbf{1}_{\big{\\{}\tau(j)=\sigma(j),\forall
j\in[k]\setminus K\big{\\}}}\prod_{r\in[d]}\mathbb{E}\bigg{[}\prod_{i\geq
2:q_{i}=r}P_{i,\sigma(i)}\prod_{j\in K:\ell_{j}=r}P_{j\tau(j)}\bigg{]}$
$\displaystyle\leq
dk\sum_{q_{2},\dots,q_{k+1}\in[d]}\sum_{l_{2},\dots,l_{k}\in[d]}\frac{d^{\Delta}}{n^{\Delta}}\mathbf{1}\big{\\{}\delta_{1}=1\big{\\}}\prod_{r=2}^{d}\mathbf{1}\big{\\{}\delta_{r}\in\\{0,1\\}\big{\\}}.$

Let $k_{r}=\\#\\{i\geq 2:\ell_{i}=r\\}$ for $r\in[d]$. There are
$\binom{k-1}{k_{1},\dots,k_{d}}$ many choices of $\ell\in[d]^{k}$ with
$\ell_{1}=1$. As in the proof of Lemma 6.1, for a given $l\in[d]^{k}$ with
$\ell_{1}=1$, there are at most

$d^{\Delta+1}\prod_{r=2}^{d}k_{r}^{\delta_{r}}$

configurations $(q_{2},\cdots,q_{k+1})\in[d]^{k}$ which contribute to the
previous sum; this is because there are
$d^{\Delta}\prod_{r=2}^{d}k_{r}^{\delta_{r}}$ many choices for
$(q_{2},\dots,q_{k})$ and at most $d$ choices for $q_{k+1}$. Hence,

$\displaystyle
dk\sum_{q_{2},\dots,q_{k+1}\in[d]}\sum_{\ell_{2},\dots,\ell_{k}\in[d]}\frac{d^{\Delta}}{n^{\Delta}}\mathbf{1}\big{\\{}\delta_{1}=1\big{\\}}\prod_{r=2}^{d}\mathbf{1}\big{\\{}\delta_{r}\in\\{0,1\\}\big{\\}}$
$\displaystyle\leq d^{2}k\sum_{k_{1},\dots,k_{d}\geq
0}\binom{k-1}{k_{1},\dots,k_{d}}\sum_{\delta_{2},\dots,\delta_{d}\in\\{0,1\\}}\prod_{r=2}^{d}\left(\frac{k_{r}d^{2}}{n}\right)^{\delta_{r}}$
$\displaystyle\leq
kd^{k+1}\big{(}1+\tfrac{d}{n}\partial_{x}\big{)}^{d}x^{k-1}\big{|}_{x=1}.$

The last inequality follows as in the proof of Lemma 6.1 (replacing $k$ by
$k-1$). Summing over all $k\in\mathbb{N}$, we conclude that for any $0<r<1$,

$\displaystyle\sum_{k\geq
1}\frac{r^{k}}{d^{k+1}}\bigg{|}\sum_{|I|=|J|=k,|I\cap J|=k-1}\mathbb{E}\det
A(I)A(J)\bigg{|}$ $\displaystyle\leq\sum_{k\geq
1}kr^{k}\big{(}1+\tfrac{d}{n}\partial_{x}\big{)}^{d}x^{k-1}\bigg{|}_{x=1}=\big{(}1+\tfrac{d}{n}\partial_{x}\big{)}^{d}\frac{r}{(1-rx)^{2}}\bigg{|}_{x=1}$
$\displaystyle=\sum_{\ell=0}^{d}\binom{d}{\ell}\frac{d^{\ell}}{n^{\ell}}\partial_{x}^{\ell}\frac{r}{(1-xr)^{2}}\bigg{|}_{x=1}$
$\displaystyle=r\sum_{\ell=0}^{d}\frac{d!}{(d-\ell)!\ell!}\frac{(rd)^{\ell}}{n^{\ell}}\frac{(\ell+1)!}{(1-r)^{\ell+2}}$
(6.6)
$\displaystyle\leq\frac{r}{(1-r)^{2}}\sum_{\ell=0}^{\infty}(\ell+1)\bigg{(}\frac{d^{2}r}{n(1-r)}\bigg{)}^{\ell}=\frac{r}{(1-r-\frac{rd^{2}}{n})^{2}}.$

This completes the proof. ∎

###### Proof of Proposition 4.1.

From Lemma 6.1 and Lemma 6.2, together with (4.5), we obtain when $1\leq
d\leq\sqrt{\frac{n(1-r)}{r}}$,

(6.7) $\displaystyle\sum_{k\leq
n}\frac{r^{k}}{d^{k+1}}\mathbb{E}|\Delta_{k}^{(n)}|^{2}\leq\frac{\frac{2}{d}+r}{(1-r-\frac{rd^{2}}{n})^{2}}.$

Then from (4.1), (4.3), the conclusion holds. ∎

###  6.2. Asymptotics of traces of sums of $d$ independent uniform
permutations

We now turn to the identification of the limits of $\mathrm{trace}(A^{k})$
stated in Theorem 3.1.

####  6.2.1. Subgraph probability estimation

Given integers $0\leqslant k_{1},\dotsc,k_{r}\leqslant d$ with
$k=k_{1}+\dotsb+k_{r}$, define

$\mathscr{T}_{\mathbf{k}}=\big{\\{}T\in\\{0,1\\}^{d\times
r}:{\textstyle\sum_{i=1}^{d}}T_{ij}=k_{j}\text{ for all }j\in[r]\big{\\}}.$

Observe that

(6.8)
$|\mathscr{T}_{\mathbf{k}}|=\binom{d}{k_{1}}\cdots\binom{d}{k_{r}}\leq\frac{d^{k}}{k_{1}!\cdots
k_{r}!}.$

######  Proposition 6.3.

Fix $\mathbf{i},\mathbf{j}\in[n]^{r}$ for $r\in\mathbb{N}$ such that
$(i_{1},j_{1}),\cdots,(i_{r},j_{r})$ are distinct. Let $\mathbf{k}\in[d]^{r}$
and set $k=k_{1}+\dotsb+k_{r}$. Then,

$\mathbb{P}(A_{i_{1},j_{1}}=k_{1},\dotsc,A_{i_{r},j_{r}}=k_{r})\leqslant|\mathscr{T}_{\mathbf{k}}|\frac{(n-k)!}{n!}.$

###### Proof.

Decomposing the event
$\\{A_{i_{1},j_{1}}=k_{1},\dotsc,A_{i_{r},j_{r}}=k_{r}\\}$ in terms of the
permutations $P^{1},\dotsc,P^{d}$ leads to

$\mathbb{P}(A_{i_{1},j_{1}}=k_{1},\dotsc,A_{i_{r},j_{r}}=k_{r})=\sum_{T\in\mathscr{T}}\mathbb{P}\left(\begin{bmatrix}P^{1}_{i_{1},j_{1}}&\dots&P^{1}_{i_{r},j_{r}}\\\
\vdots&&\vdots\\\
P^{d}_{i_{1},j_{1}}&\dots&P^{d}_{i_{r},j_{r}}\end{bmatrix}=T\right).$

Since $P^{1},\dotsc,P^{d}$ are independent, we obtain

$\mathbb{P}(A_{i_{1},j_{1}}=k_{1},\dotsc,A_{i_{r},j_{r}}=k_{r})=\sum_{T\in\mathscr{T}}\prod_{\delta=1}^{d}\mathbb{P}(P_{i_{1},j_{1}}=T_{\delta,1},\dotsc,P_{i_{r},j_{r}}=T_{\delta,r}).$

Each term in this product falls under Proposition 5.2 – either it equals $0$
or (5.3) holds. Let $s_{\delta}=T_{\delta,1}+\dotsb+T_{\delta,r}$ for
$\delta\in[d]$, this implies that there exists
$0\leq\varepsilon_{\delta}\leqslant\frac{r}{n-r}$ for $\delta\in[d]$ so that

(6.9)
$\mathbb{P}(A_{i_{1},j_{1}}=k_{1},\dotsc,A_{i_{r},j_{r}}=k_{r})\leq\sum_{T\in\mathscr{T}}\prod_{\delta=1}^{d}(1-\varepsilon_{\delta})\frac{(n-s_{\delta})!}{n!},\quad\text{
with equality if $\mathbf{i},\mathbf{j}\in\mathcal{E}_{r}$.}$

Note that by definition of $\mathscr{T}$,
$\sum_{\delta=1}^{d}s_{\delta}=\sum_{j=1}^{r}k_{j}=k$, this yields the upper-
bound,

$\mathbb{P}(A_{i_{1},j_{1}}=k_{1},\dotsc,A_{i_{r},j_{r}}=k_{r})\leq\sum_{T\in\mathscr{T}}\prod_{\delta=1}^{d}\frac{(n-s_{\delta})!}{n!}\leq|\mathscr{T}|\frac{(n-k)!}{n!}$

where we used (3.4). ∎

######  Proposition 6.4.

Fix $\mathbf{i},\mathbf{j}\in\mathcal{E}_{r}$ for $r\leq n/2$. Let
$\theta=d/n$. There exists
$|\varepsilon|\leq\max\left\\{\frac{dr}{n-r},\frac{2r^{2}}{n}\right\\}$ such
that

(6.10)
$\mathbb{P}\big{(}A_{i_{1},j_{1}}=\cdots=A_{i_{r},j_{r}}=1\big{)}=(1+\varepsilon)\theta^{r}.$

###### Proof.

Note that for $r\leq n/2$,

$\displaystyle\frac{n^{r}(n-r)!}{n!}=\left(1+\frac{r-1}{n-r+1}\right)\cdots\left(1+\frac{1}{n-1}\right)\leq\left(1+\frac{r-1}{n-r+1}\right)^{r-1}\leq
1+\frac{2r^{2}}{n}.$

We have the inequality for $r\leq n/2$,

(6.11) $\displaystyle\frac{(n-r)!}{n!}\leq\frac{1+2r^{2}/n}{n^{r}}.$

By Proposition 6.3 and using the fact that $|\mathscr{T}_{\mathbf{k}}|=d^{r}$
for $\mathbf{k}=(1,\dots,1)$, and (6.11), we get

$\mathbb{P}\big{(}A_{i_{1},j_{1}}=\cdots=A_{i_{r},j_{r}}=1\big{)}\leq\left(1+\frac{2r^{2}}{n}\right)\theta^{r}.$

For the lower bound, by formula (6.9) in case
$\mathbf{i},\mathbf{j}\in\mathcal{E}_{r}$,

$\mathbb{P}(A_{i_{1},j_{1}}=k_{1},\dotsc,A_{i_{r},j_{r}}=k_{r})\geq(1-\varepsilon)^{d}\sum_{T\in\mathscr{T}}\prod_{\delta=1}^{d}\frac{(n-s_{\delta})!}{n!}$

with $\varepsilon=\frac{r}{n-r}$. By convexity, when $r<n/2$,
$(1-\varepsilon)^{d}\geq 1-d\epsilon$. Then, using that in this case
$\sum_{\delta=1}^{d}s_{\delta}=\sum_{j=1}^{r}k_{j}=r$, this implies that

$\mathbb{P}(A_{i_{1},j_{1}}=k_{1},\dotsc,A_{i_{r},j_{r}}=k_{r})\geq(1-d\varepsilon)|\mathscr{T}|n^{-r}.$

This concludes the proof. ∎

As a direct consequence of Proposition 6.4, we have the asymptotics of the
probability of a simple cycle on the digraph of the random matrix $A$. We now
turn to bounding joint moments of the entries of the random matrix $A$.

######  Proposition 6.5.

For a fixed constant $r\in\mathbb{N}$, fix
$\bm{\alpha},\bm{\beta}\in\mathbb{N}^{r}$ and let
$\beta=\beta_{1}+\cdots+\beta_{r}$. Let $\theta=d/n$ and assume that
$d\leq\sqrt{n}$. Then, for any $\mathbf{i},\mathbf{j}\in[n]^{r}$,

$\mathbb{E}\big{[}A_{i_{1},j_{1}}^{\alpha_{1}}\dotsb
A_{i_{r},j_{r}}^{\alpha_{r}}\mathbf{1}_{\\{A_{i_{\ell},j_{\ell}}\geq\beta_{\ell},\ell\in[r]\\}}\big{]}=O_{\bm{\alpha},\bm{\beta}}(\theta^{\beta}).$

###### Proof.

Without loss of generality, we may assume that
$(i_{1},j_{1}),\cdots,(i_{r},j_{r})$ are distinct. By Proposition 6.3 and
(6.8), we have

$\displaystyle\mathbb{E}\big{[}A_{i_{1},j_{1}}^{\alpha_{1}}\dotsb
A_{i_{r},j_{r}}^{\alpha_{r}}\mathbf{1}_{\\{A_{i_{\ell},j_{\ell}}\geq\beta_{\ell},\ell\in[r]\\}}\big{]}$
$\displaystyle=\sum_{\mathbf{k}\in[d]^{r},\mathbf{k}\geq\bm{\beta}}k_{1}^{\alpha_{1}}\cdots
k_{r}^{\alpha_{r}}\mathbb{P}(A_{i_{1},j_{1}}=k_{1},\dotsc,A_{i_{r},j_{r}}=k_{r})$
$\displaystyle\leq\sum_{\mathbf{k}\in[d]^{r},\mathbf{k}\geq\bm{\beta}}\frac{k_{1}^{\alpha_{1}}\cdots
k_{r}^{\alpha_{r}}}{k_{1}!\cdots k_{r}!}d^{k}\frac{(n-k)!}{n!};\qquad
k=k_{1}+\cdots+k_{r}.$

Again with (6.11), we can bound
$\frac{(n-k)!}{n!}\leq\frac{1+2k^{2}/n}{n^{k}}$ for $k\leq n/2$. Since $r$ is
fixed, this yields the estimate valid for $k\leq rd\leq n/2$, and
$d\leq\sqrt{n}$,

$\displaystyle\mathbb{E}\big{[}A_{i_{1},j_{1}}^{\alpha_{1}}\dotsb
A_{i_{r},j_{r}}^{\alpha_{r}}\mathbf{1}_{\\{A_{i_{\ell},j_{\ell}}\geq\beta_{\ell},\ell\in[r]\\}}\big{]}$
$\displaystyle\leq(1+2r^{2}d^{2}/n)\sum_{\mathbf{k}\geq\bm{\beta}}\prod_{j=1}^{r}\frac{k_{j}^{\alpha_{j}}}{k_{j}!}\theta^{k_{j}}\leq(1+2r^{2})\sum_{\mathbf{k}\geq\bm{\beta}}\prod_{j=1}^{r}\frac{k_{j}^{\alpha_{j}}}{k_{j}!}\theta^{k_{j}}.$

Now, we can use the bound for $\theta\leq 1$,

$\sum_{k\geq b}\frac{k^{a}}{k!}\theta^{k}\leq C_{a,b}\theta^{b},$

to conclude the proof. ∎

####  6.2.2. Reducing traces to cycle counts in the digraph of $A$

Recall that

$\mathrm{tr}(A^{k})=\sum_{\mathbf{i}\in[n]^{k}}A_{\mathbf{i}}.$

In particular, by Proposition 6.5 applied with
$\alpha_{1}+\cdots+\alpha_{r}=k$, $\beta_{1}=\cdots=\beta_{r}=1$,

$\mathbb{E}\mathrm{tr}(A^{k})\leq C_{k}n^{k}\theta^{k}=C_{k}d^{k}.$

In particular, in the regime where $d$ is fixed, for any $k\in\mathbb{N}$, the
non-negative random variables
$\big{(}\mathrm{tr}(A^{k})\big{)}_{n\in\mathbb{N}}$ are tight.

For every $\mathbf{i}=(i_{1},\dotsc,i_{k})\in[n]^{k}$, we can associate a
digraph

$\displaystyle V(\mathbf{i})=\\{i_{1},\dotsc,i_{k}\\}$ $\displaystyle
v(\mathbf{i})=\\#V(\mathbf{i})$ $\displaystyle
E(\mathbf{i})=\\{(i_{1},i_{2}),(i_{2},i_{3}),\dotsc,(i_{k-1},i_{k}),(i_{k},i_{1})\\}$
$\displaystyle e(\mathbf{i})=\\#E(\mathbf{i}).$

One can interpret $v(\mathbf{i})$ as the number of ‘vertices’ of $[n]$ that
are visited by $\mathbf{i}$, and $e(\mathbf{i})$ as the number of distinct
‘edges’ of $\mathbf{i}$. The digraph $(V(\mathbf{i}),E(\mathbf{i}))$ contains
at least a loop, so necessarily $v(\mathbf{i})\leqslant e(\mathbf{i})\leq k$.
For integers $v\leqslant e\leqslant k$, we define

(6.12)
$\mathscr{E}_{k}(v,e)=\\{\mathbf{i}\in[n]^{k}:v(\mathbf{i})=v,e(\mathbf{i})=e\\}.$

Let us decompose

(6.13)
$\mathrm{tr}(A^{k})=\sum_{\begin{subarray}{c}\mathbf{i}\in\mathscr{E}_{k}(v,e)\\\
v=e\end{subarray}}\mathbf{1}_{A_{\mathbf{i}}=1}+\sum_{\begin{subarray}{c}\mathbf{i}\in\mathscr{E}_{k}(v,e)\\\
v=e\end{subarray}}A_{\mathbf{i}}\mathbf{1}_{A_{\mathbf{i}}>1}+\sum_{\begin{subarray}{c}\mathbf{i}\in\mathscr{E}_{k}(v,e)\\\
v<e\end{subarray}}A_{\mathbf{i}}=:T_{k}+R_{k}+S_{k}.$

First, let us show that both $R_{k}$ and $S_{k}$ can be treated as negligible
errors.

######  Lemma 6.6.

Suppose that $d=n^{o(1)}$ as $n\to\infty$. For any fixed $k\in\mathbb{N}$,
$(R_{k}+S_{k})\to 0$ in probability as $n\to\infty$.

###### Proof.

For any $\mathbf{i}\in[n]^{k}$, by Proposition 6.5 with $k$ fixed,

$\mathbb{E}A_{\mathbf{i}}\leq C_{k}\theta^{e(\mathbf{i})},\qquad\theta=d/n,$

since there are $e$ different entries and we can take
$\bm{\beta}=\underbrace{(1,\dots,1)}_{\times e}$. Since
$|\mathscr{E}_{k}(v,e)|\leq k!n^{v}$, this shows that

$\mathbb{E}S_{k}\leq\sum_{v<e\leq k}C_{k}n^{v}\theta^{e}\leq
C_{k}\frac{d^{k}}{n}.$

We conclude that if $d=n^{o(1)}$, then $\mathbb{E}S_{k}\to 0$ as $n\to\infty$.
Similarly, by Proposition 6.5,

$\mathbb{E}A_{\mathbf{i}}\mathbf{1}_{A_{\mathbf{i}}>1}\leq
C_{k}\theta^{e(\mathbf{i})+1},$

so that

$\mathbb{E}R_{k}\leq\sum_{v\leq k}C_{k}n^{v}\theta^{v+1}\leq
C_{k}\frac{d^{k+1}}{n}.$

Hence, also $\mathbb{E}R_{k}\to 0$ as $n\to\infty$. ∎

######  Lemma 6.7 (Lemma 9.3 in [19]).

$\mathscr{E}_{k}(v,v)$ is empty if $v$ is not a divisor of $k$. Otherwise, if
$k=vq$, then the elements of $\mathscr{E}_{k}(v,v)$ are exactly the sequences

(6.14)
$(i_{1},i_{2},\dotsc,i_{v},i_{1},\dotsc,i_{v},\dotsc,i_{1},\dotsc,i_{v})$

where the subsequence
$\mathbf{i}^{\prime}=(i_{1},\dotsc,i_{v})\in\mathcal{E}_{v}$ is repeated $q$
times. Moreover, the events
$\\{A_{\mathbf{i}}=1\\}=\\{A_{\mathbf{i}^{\prime}}=1\\}$.

Lemma 6.7 implies that according to (6.13),

$T_{k}=\sum_{v|k}\sum_{\mathbf{i}^{\prime}\in\mathscr{E}_{v}}\mathbf{1}_{A_{\mathbf{i}^{\prime}}=1}.$

Let us denote for $\ell\in[n]$,

(6.15) $\mathcal{C}_{\ell}:=\big{\\{}\mathbf{i}=(i_{1},\dotsc,i_{\ell})\text{
modulo cyclic permutation}:i_{k}\in[n],\text{ distincts}\big{\\}}$

and the random variables

(6.16)
$Q_{\ell}:=\sum_{\mathbf{i}\in\mathcal{C}_{\ell}}\mathbf{1}_{A_{\mathbf{i}}=1}.$

With this new notation,

(6.17) $T_{k}=\sum_{\ell|k}\ell Q_{\ell}.$

The interpretation is that $Q_{\ell}$ is the number of (oriented)
$\ell$-cycles on the digraph defined by the random matrix $A$ and $T_{k}$ is a
good approximation for $\mathrm{tr}(A^{k})$.

####  6.2.3. Asymptotics of joint moments of cycle counts

If $Q\in\mathbb{N}$, we denote its falling factorials by

$(Q)_{r}=Q(Q-1)\cdots(Q-r+1),\qquad r\in\mathbb{N}.$

Our interest in these quantities stems from the fact that if $Q=|\mathcal{C}|$
for a finite set $\mathcal{C}$, then

(6.18) $(Q)_{r}=\big{|}\\{(j_{1},\dotsc,j_{r}):j_{k}\in\mathcal{C}\text{
distincts}\\}\big{|}.$

The following basic probabilistic result holds.

######  Lemma 6.8.

For $\lambda>0$, $\Lambda\sim{\rm Poisson}(\lambda)$ if and only if for all
$r\in\mathbb{N}$,

$\mathbb{E}(\Lambda)_{r}=\lambda^{r}.$

######  Proposition 6.9.

Recall the notation (6.16) and fix $k\in\mathbb{N}$ and
$\bm{\alpha}\in\mathbb{N}_{0}^{k}$. Then, as $n\to\infty$

$\mathbb{E}\left[(Q_{1})_{\alpha_{1}}\cdots(Q_{k})_{\alpha_{k}}\right]={\left(\frac{d^{1}}{1}\right)^{\alpha_{1}}\dotsb\left(\frac{d^{m}}{m}\right)^{\alpha_{m}}}\big{(}1+O_{\bm{\alpha}}(d/n)\big{)}.$

The proof of Proposition 6.9 will be given in Section 6.3.2. It relies on
Proposition 6.4 and basic combinatorial arguments counting certain collections
of (distinct) cycles on the digraph of the random matrix $A$. To illustrate
the argument, we compute the first and second moment of the random variable
$Q_{\ell}$ in Section 6.3.1.

According to Lemma 6.8, Proposition 6.9 directly implies that for a fixed
$d\in\mathbb{N}$, for any fixed $\bm{\ell},\bm{\alpha}\in\mathbb{N}^{k}$,

(6.19)
$\lim_{n\to\infty}\mathbb{E}\left[(Q_{\ell_{1}})_{\alpha_{1}}\cdots(Q_{\ell_{k}})_{\alpha_{k}}\right]=\mathbb{E}\left[(\Lambda_{\ell_{1}})_{\alpha_{1}}\cdots(\Lambda_{\ell_{k}})_{\alpha_{k}}\right]$

where the Poisson random variables $\\{\Lambda_{\ell}\\}_{\ell\in\mathbb{N}}$
are given by Definition 2.3. Now we are ready to prove Theorem 3.1.

#### Proof of (3.2)

The joint convergence of the factorial moments described in (6.19) implies
that for every $k\in\mathbb{N}$,

$(Q_{1},\dotsc,Q_{k})\xrightarrow[n\to\infty]{\mathrm{law}}\
(\Lambda_{1},\dotsc,\Lambda_{k})$

and in the sense of moments. Then, by the Cramér-Wold theorem, for every
$k\in\mathbb{N}$,

$\bigg{(}T_{1}=Q_{1},\cdots,T_{k}=\sum_{\ell|k}\ell
Q_{\ell}\bigg{)}\xrightarrow[n\to\infty]{\mathrm{law}}\bigg{(}\Lambda_{1},\dotsc,\sum_{\ell|k}\ell\Lambda_{\ell}\bigg{)}.$

By Lemma 6.6, for every $k\in\mathbb{N}$ and any $\epsilon>0$,

(6.20)
$\mathbb{P}\big{(}|\mathrm{tr}(A)-T_{1}|+\cdots+|\mathrm{tr}(A^{k})-T_{k}|\geq\epsilon\big{)}\xrightarrow[n\to\infty]{}0$

This establishes that for any fixed $d\in\mathbb{N}$ and $k\in\mathbb{N}$,

$\big{(}\mathrm{tr}(A),\cdots,\mathrm{tr}(A^{k})\big{)}\xrightarrow[n\to\infty]{\mathrm{law}}\bigg{(}\Lambda_{1},\dotsc,\sum_{\ell|k}\ell\Lambda_{\ell}\bigg{)}.$

#### Proof of (3.3)

In the regime where the degree $d=d(n)\to\infty$ so that $d=n^{o(1)}$ as
$n\to\infty$, the error term in Proposition 6.9 is so good that we can
directly show that the random variables $(Q_{\ell})_{\ell\in\mathbb{N}}$, if
suitably normalized, converge to independent Gaussians in the sense of finite
dimensional distributions. Namely, the asymptotics from Proposition 6.9 yields
the conditions (A.5)–(A.6) in Lemma A.1 with

$\lambda_{i,n}=d(n)^{i}/i\qquad\text{and}\qquad\epsilon_{\mathbf{k},n}=O_{\mathbf{k}}(d(n)/n).$

In particular since for every $k\in\mathbb{N}$, $d(n)^{k}/n\to 0$ as
$n\to\infty$, by Lemma A.1, we conclude that for any $\ell\in\mathbb{N}$

(6.21)
$\left(\frac{Q_{1}-d}{\sqrt{d/1}},\dots,\frac{Q_{\ell}-d^{\ell}/\ell}{\sqrt{d^{\ell}/\ell}}\right)\xrightarrow[n\to\infty]{\mathrm{law}}\big{(}N_{1},\dots,N_{\ell}\big{)},$

as well as in the sense of moments, where $\\{N_{\ell}\\}_{\ell\in\mathbb{N}}$
are as in Definition 2.5. Observe that according to (6.17), we can write for
$k\in\mathbb{N}$,

(6.22)
$\frac{T_{k}-d^{k}}{d^{k/2}}=\sum_{\ell|k}\sqrt{\ell}d^{-(k-\ell)/2}\bigg{(}\frac{Q_{\ell}-d^{\ell}/\ell}{\sqrt{d^{\ell}/\ell}}\bigg{)}+\sum_{\ell|k,\ell<k}d^{\ell-k/2}$

Hence, by (6.21) and the Cramér-Wold theorem, for every $k\in\mathbb{N}$,

$\left(\frac{T_{1}-d}{\sqrt{d}},\dots,\frac{T_{2k}-d^{2k}}{\sqrt{d^{2k}}}\right)\xrightarrow[n\to\infty]{\mathrm{law}}\big{(}N_{1},\sqrt{2}N_{2}+1,\sqrt{3}N_{3},\dots,\sqrt{2k}N_{2k}+1\big{)}.$

Note that in (6.22), as $d(n)\to\infty$, only the term $\ell=k$ contributes to
the random and the term $\ell=k/2$ contributes to the mean if $k\in
2\mathbb{N}$. In particular, once normalized, the weak limit of $T_{k}$ are
still independent Gaussians.

To finish the proof of (3.3), by (6.13) and Lemma 6.6 which still holds in the
regime where $d=n^{o(1)}$, for a fixed $k\in\mathbb{N}$,

$\left(\frac{\mathrm{tr}(A^{1})-d}{\sqrt{d}},\dots,\frac{\mathrm{tr}(A^{2k})-d^{2k}}{\sqrt{d^{2k}}}\right)=\left(\frac{T_{1}-d}{\sqrt{d}},\dots,\frac{T_{2k}-d^{2k}}{\sqrt{d^{2k}}}\right)+\underset{n\to\infty}{o(1)}$

where the error is controlled as in (6.20). This completes the proof of
Theorem 3.1.

###  6.3. Proof of Proposition 6.9

We now prove Proposition 6.9. We first prove the proposition only for first
and second moments, to give a flavour of the proof. The complete proof is in
Subsection 6.3.2.

####  6.3.1. First and second moment

Let us first prove that

$\mathbb{E}[Q_{i}]=\frac{d^{i}}{i}(1+O_{i}(d/n)),$

and that

$\mathbb{E}[(Q_{i})_{2}]=\left(\frac{d^{i}}{i}\right)^{2}(1+O_{i}(d/n)).$

By (6.16) and since $|\mathcal{C}_{\ell}|=(n)_{\ell}/\ell$, according to
Proposition 6.4, there exists $\varepsilon=O_{\ell}(d/n)$ so that

$\mathbb{E}Q_{\ell}=|\mathcal{C}_{\ell}|(1+\varepsilon)(d/n)^{\ell}.$

For fixed $\ell\in\mathbb{N}$, this shows that as $n\to\infty$,

$\mathbb{E}Q_{\ell}=d^{\ell}/\ell\big{(}1+O_{\ell}(d/n)\big{)}.$

For the second (factorial) moment, by (6.18),

$\mathbb{E}(Q_{\ell})_{2}=\sum_{\mathbf{i},\mathbf{j}\in\mathcal{C}_{\ell},\mathbf{i}\neq\mathbf{j}}\mathbb{P}\big{(}A_{\mathbf{i}}=1,A_{\mathbf{j}}=1\big{)}.$

If we identify $\mathbf{i},\mathbf{j}$ with $\ell$-cycles, observe that the
condition $\mathbf{i}\neq\mathbf{j}$ implies that the digraph
$\\{\mathbf{i},\mathbf{j}\\}$ obtained by concatenating $\mathbf{i}$,
$\mathbf{j}$,

(6.23) $\displaystyle
V(\\{\mathbf{i},\mathbf{j}\\})=\\{i_{1},\dotsc,i_{\ell},j_{1},\dotsc,j_{\ell}\\}$
$\displaystyle
E(\\{\mathbf{i},\mathbf{j}\\})=\\{(i_{1},i_{2}),(i_{2},i_{3}),\dotsc,(i_{k-1},i_{\ell}),(i_{\ell},i_{1}),(j_{1},j_{2}),(j_{2},j_{3}),\dotsc,(j_{k-1},j_{\ell}),(j_{\ell},j_{1})\\}$

satisfies

(6.24) $\mathbf{i}\cap\mathbf{j}=\emptyset\quad\text{if and only
if}\quad|V(\\{\mathbf{i},\mathbf{j}\\})|=|E(\\{\mathbf{i},\mathbf{j}\\})|.$

In particular, we can split

$\mathbb{E}(Q_{\ell})_{2}=\sum_{\mathbf{i},\mathbf{j}\in\mathcal{C}_{\ell},\mathbf{i}\cap\mathbf{j}=\emptyset}\mathbb{P}\big{(}A_{\mathbf{i}}=1,A_{\mathbf{j}}=1\big{)}+\sum_{\mathbf{i},\mathbf{j}\in\mathcal{C}_{\ell},|V|<|E|}\mathbb{P}\big{(}A_{\mathbf{i}}=1,A_{\mathbf{j}}=1\big{)}$

where the second term is due to (6.24). By Proposition 6.3, we have for
$\mathbf{i},\mathbf{j}\in\mathcal{C}_{\ell}$,

$\mathbb{P}\big{(}A_{\mathbf{i}}=1,A_{\mathbf{j}}=1\big{)}\leq
C_{\ell}(d/n)^{|E|}$

and $\big{|}\\{\mathbf{i},\mathbf{j}\in\mathcal{C}_{\ell},|V|=v\\}\big{|}\leq
C_{\ell}n^{v}$ for $v\in\\{\ell,\cdots,2\ell\\}$, so that

$\sum_{\mathbf{i},\mathbf{j}\in\mathcal{C}_{\ell},|V|<|E|}\mathbb{P}\big{(}A_{\mathbf{i}}=1,A_{\mathbf{j}}=1\big{)}\leq
C_{\ell}\frac{d^{2\ell}}{n}.$

On the other hand, also by Proposition 6.4, for
$\mathbf{i},\mathbf{j}\in\mathcal{C}_{\ell}$ disjoint, there exists
$\varepsilon=O_{\ell}(d/n)$ so that

$\mathbb{P}\big{(}A_{\mathbf{i}}=1,A_{\mathbf{j}}=1\big{)}=(1+\varepsilon)(d/n)^{2\ell}.$

Moreover, for a fixed $\ell\in\mathbb{N}$, we have
$\big{|}\\{\mathbf{i},\mathbf{j}\in\mathcal{C}_{\ell},\mathbf{i}\cap\mathbf{j}=\emptyset\\}\big{|}=\tfrac{n^{2\ell}}{\ell^{2}}\big{(}1-O_{\ell}(1/n)\big{)}$
as $n\to\infty$. This shows that as $n\to\infty$

(6.25)
$\mathbb{E}(Q_{\ell})_{2}=\frac{d^{2\ell}}{\ell^{2}}\big{(}1+O_{\ell}(d/n)\big{)}.$

####  6.3.2. Proof of Proposition 6.9

Fix $k\in\mathbb{N}$ and $\bm{\alpha}\in\mathbb{N}_{0}^{k}$. Recall (6.15) and
let us denote

$\Gamma_{\bm{\alpha}}=\big{\\{}\vec{\mathbf{i}}=\\{\mathbf{i}_{r,\ell}\\}_{r\in[\alpha_{\ell}],\ell\in[k]}:\,\mathbf{i}_{1,\ell},\dots,\mathbf{i}_{\alpha_{\ell},\ell}\in\mathcal{C}_{\ell},\text{
distincts, for all }\ell\in[k]\big{\\}}.$

An element $\vec{\mathbf{i}}\in\Gamma_{\bm{\alpha}}$ is a collection of
distinct cycles of length
$(\underbrace{1,\cdots,1}_{\times\alpha_{1}},\cdots,\underbrace{k,\cdots,k}_{\times\alpha_{k}})$.
Then, by (6.18), we have

$\mathbb{E}\left[(Q_{\ell_{1}})_{\alpha_{1}}\cdots(Q_{\ell_{k}})_{\alpha_{k}}\right]=\sum_{\vec{\mathbf{i}}\in\Gamma_{\bm{\alpha}}}\mathbb{P}\big{(}A_{\mathbf{i}_{r,\ell}}=1,\forall
r\in[\alpha_{\ell}],\forall\ell\in[k]\big{)}.$

Generalizing the notation (6.23), the digraph $\vec{\mathbf{i}}$ satisfies

$|V(\vec{\mathbf{i}})|=|E(\vec{\mathbf{i}})|\quad\text{if and only
if}\quad\text{the cycles $\mathbf{i}_{r,\ell}$ are all disjoint.}$

This follows e.g. by induction on (6.24). Hence, we split

(6.26)
$\displaystyle\mathbb{E}\left[(Q_{\ell_{1}})_{\alpha_{1}}\cdots(Q_{\ell_{k}})_{\alpha_{k}}\right]$
$\displaystyle=\sum_{\vec{\mathbf{i}}\in\Gamma_{\bm{\alpha}},\,\mathbf{i}_{r,\ell}\text{
disjoint}}\mathbb{P}\big{(}A_{\mathbf{i}_{r,\ell}}=1,\forall
r\in[\alpha_{\ell}],\forall s\in[k]\big{)}$ (6.27)
$\displaystyle+\sum_{\vec{\mathbf{i}}\in\Gamma_{\bm{\alpha}},\,|V(\vec{\mathbf{i}})|<|E(\vec{\mathbf{i}})|}\mathbb{P}\big{(}A_{\mathbf{i}_{r,\ell}}=1,\forall
r\in[\alpha_{\ell}],\forall s\in[k]\big{)}.$

By Proposition 6.4, for any $\vec{\mathbf{i}}\in\Gamma_{\bm{\alpha}}$, there
exists $\varepsilon(\vec{\mathbf{i}})=O(d/n)$ so that

$\mathbb{P}\big{(}A_{\mathbf{i}_{r,\ell}}=1,\forall
r\in[\alpha_{\ell}],\forall\ell\in[k]\big{)}=(1+\varepsilon(\vec{\mathbf{i}}))(d/n)^{E(\vec{\mathbf{i}})}.$

Since
$\big{|}\\{\vec{\mathbf{i}}\in\Gamma_{\bm{\alpha}},|V|=v\\}\big{|}=O(n^{v})$
for $v\in\\{1,\cdots,|\bm{\alpha}|\\}$ where
$|\bm{\alpha}|=1\cdot\alpha_{1}+\cdots+k\cdot\alpha_{k}$, we obtain

$\eqref{jm2}=O\big{(}d^{|\bm{\alpha}|}/n\big{)}.$

Now, if $\mathbf{i}_{r,\ell}$ are all disjoint,
$|V(\vec{\mathbf{i}})|=|E(\vec{\mathbf{i}})|=|\bm{\alpha}|$ and

$\big{|}\\{\vec{\mathbf{i}}\in\Gamma_{\bm{\alpha}},\,\mathbf{i}_{r,\ell}\text{
disjoint}\\}\big{|}=\frac{n^{|\bm{\alpha}|}}{1^{\alpha_{1}}\cdots
k^{\alpha_{k}}}\big{(}1-O(1/n)\big{)}$

This implies that

$\eqref{jm1}=\frac{d^{|\bm{\alpha}|}}{1^{\alpha_{1}}\cdots
k^{\alpha_{k}}}\big{(}1+O(d/n)\big{)}.$

Note that the implied constants above depend only on $\bm{\alpha}$. This
completes the proof of Proposition 6.9.

##  7\. Poisson analytic functions

###### Proof of Proposition 2.7.

The function $Y_{d}$ is centred and it is almost surely analytic in $D_{1}$
since $\|Y_{d}\|^{2}_{L^{\infty}(D_{r})}<\infty$ almost surely for any $r<1$.
Indeed, by Jensen’s inequality, it holds for $r<1$,

$\mathbb{E}\|Y_{d}\|_{L^{\infty}(D_{r})}^{2}\leq\mathbb{E}\bigg{(}\sum_{k\in\mathbb{N}}\frac{r^{k}}{kd^{k/2}}\bigg{|}\sum_{\ell|k}\ell\overline{\Lambda_{\ell}}\bigg{|}\bigg{)}^{2}\leq\frac{r}{1-r}\sum_{k\in\mathbb{N}}\frac{r^{k}}{k^{2}d^{k}}\mathbb{E}\bigg{|}\sum_{\ell|k}\ell\overline{\Lambda_{\ell}}\bigg{|}^{2}.$

By independence of $\\{\Lambda_{\ell}\\}_{\ell\in\mathbb{N}}$, it holds for
$k\in\mathbb{N}$,

$\frac{1}{k^{2}d^{k}}\mathbb{E}\bigg{|}\sum_{\ell|k}\ell\overline{\Lambda_{\ell}}\bigg{|}^{2}=\frac{1}{k^{2}d^{k}}\sum_{\ell|k}\ell^{2}\mathbb{E}\big{|}\overline{\Lambda_{\ell}}\big{|}^{2}=\frac{1}{k^{2}d^{k}}\sum_{\ell|k}\ell
d^{\ell}\leq 1,$

where we used that $\operatorname{Var}(\Lambda_{\ell})=d^{\ell}/\ell$ for
$\ell\in\mathbb{N}$. This shows that for any $r<1$,

(7.1)
$\mathbb{E}\|Y_{d}\|_{L^{\infty}(D_{r})}^{2}\leq\frac{r^{2}}{(1-r)^{2}}.$

Repeating this argument clearly leads to the same estimate for the random
analytic function $X_{d}$. This proves that $Y_{d}$ is well-defined. Then by
rearranging the series, we can write

(7.2)
$Y_{d}(z)=\sum_{\ell\in\mathbb{N}}\overline{\Lambda_{\ell}}\sum_{k\in\mathbb{N}}\frac{z^{k\ell}}{kd^{k\ell/2}}=-\sum_{\ell\in\mathbb{N}}\overline{\Lambda_{\ell}}\log\big{(}1-(z/\sqrt{d})^{\ell}\big{)}$

for the principle branch of $\log(1+z)$ which is analytic for $z\in D_{1}$.
Recall that the Laplace transform of a random variable
$\Lambda\sim\mathrm{Poisson}(\lambda)$ satisfies

(7.3)
$\mathbb{E}\exp(z(\Lambda-\mathbb{E}\Lambda))=\exp\big{(}\lambda(e^{z}-1-z)\big{)},\qquad
z\in\mathbb{C}.$

In particular, this can be used to give an alternative proof that the series
(7.2) is (almost surely) absolutely convergent and to justify rearranging this
sum. Namely, it holds for all $0\leq t\leq\sqrt{\lambda}$,

$\mathbb{E}\exp\big{(}t|\Lambda-\mathbb{E}\Lambda|/\sqrt{\lambda}\big{)}\leq
2\exp\big{(}t^{2}\big{)}.$

For $d\geq 2$, by Markov’s inequality, we obtain the large deviation estimate,

$\mathbb{P}\big{[}|\overline{\Lambda_{\ell}}|\geq\sqrt{d^{\ell}}\big{]}\leq\exp\big{(}-\ell/4\big{)}.$

Hence, almost surely, $|\overline{\Lambda_{\ell}}|\leq\sqrt{d^{\ell}}$ for all
$\ell\in\mathbb{N}$ sufficiently large and (7.2) is absolutely convergent.

######  Remark 7.1.

In the special case $d=1$, observe that

$\mathbb{P}\big{[}\Lambda_{\ell}\geq 2\text{ infinitely
often}\big{]}\leq\lim_{n\to\infty}\sum_{\ell\geq
n}\bigg{(}\mathbb{P}\big{[}\Lambda_{\ell}\geq
2\big{]}\bigg{)}\leq\bigg{(}\lim_{n\to\infty}\sum_{\ell\geq
n}\frac{1/2}{\ell^{2}}\bigg{)}=0.$

In particular, the random analytic function
$\sum_{k\in\mathbb{N}}\frac{z^{k}}{k}\sum_{\ell|k}\ell\Lambda_{\ell}$
converges almost surely for $z\in D_{1}$. In contrast, for $d\geq 2$, it is
necessary to re-center the Poisson random coefficients to define a random
analytic function in $D_{1}$.

Let us denote by $\mathrm{f}_{\ell}(z):=(1-z^{\ell})e^{z^{\ell}}$ for
$\ell\in\mathbb{N}$ so that $\log\mathrm{f}_{\ell}$ is analytic in $D_{1}$
(using the principal branch). By independence of
$\\{\Lambda_{\ell}\\}_{\ell\in\mathbb{N}}$ and (7.3), it follows from the
expansion (7.2) that

$\mathbb{E}e^{-Y_{d}(z)}=\bigg{(}\prod_{\ell\in\mathbb{N}}\mathrm{f}_{\ell}(z/\sqrt{d})^{\frac{d^{\ell}}{\ell}}\bigg{)}^{-1}.$

This infinite product converges since
$\big{|}\log\mathrm{f}_{\ell}(z)\big{|}\leq\frac{r^{2\ell}}{1-r}$ for $z\in
D_{r}$ and we used that

$e^{\log(1-z^{\ell})}-1-\log(1-z^{\ell})=-\log\mathrm{f}_{\ell}(z).$

This proves (2.4). Now, if we repeat the computation leading to (7.1), then
for any $r<d^{1/4}$,

$\displaystyle\mathbb{E}\|\Upsilon_{d}\|_{L^{\infty}(D_{r})}^{2}=\mathbb{E}\bigg{\|}\sum_{k\in\mathbb{N}}\frac{z^{k}}{kd^{k/2}}\sum_{\ell|k,\ell<k}\ell\overline{\Lambda_{\ell}}\bigg{\|}_{L^{\infty}(D_{r})}^{2}$
$\displaystyle\leq\frac{r}{d^{1/4}-r}\sum_{k\in\mathbb{N}}\frac{r^{k}}{k^{2}d^{3k/4}}\mathbb{E}\bigg{|}\sum_{\ell|k,\ell<k}\ell\overline{\Lambda_{\ell}}\bigg{|}^{2}$
(7.4)
$\displaystyle\leq\frac{r/2}{d^{1/4}-r}\sum_{k\in\mathbb{N}}\frac{r^{k}}{d^{k/4}}=\frac{r^{2}/2}{(d^{1/4}-r)^{2}},$

where we used that $\sum_{\ell|k,\ell<k}\ell
d^{\ell}\leq\frac{k^{2}}{2}d^{k/2}.$ This shows that the random analytic
function $\Upsilon_{d}$ converges almost surely in the disk $D_{d^{1/4}}$,
which is strictly larger than $D_{1}$ if the degree $d\geq 2$. On the other-
hand, by independence of $\\{\Lambda_{\ell}\\}_{\ell\in\mathbb{N}}$, the
covariance kernel of $X_{d}$ is

(7.5)
$\displaystyle\mathbb{E}X_{d}(z)X_{d}(w)=\sum_{k\in\mathbb{N}}\frac{z^{k}w^{k}}{d^{k}}\mathbb{E}\overline{\Lambda_{k}}^{2}=\sum_{k\in\mathbb{N}}\frac{z^{k}w^{k}}{k}=\log(1-zw)^{-1},\qquad
z,w\in D_{1}.$

Remarkably, this kernel is independent of $d\in\mathbb{N}$ and $z\in\partial
D_{1}\mapsto X_{d}(z)$ is a non-Gaussian log-correlated field. If $d\geq 2$,
so is the field $z\in\partial D_{1}\mapsto Y_{d}(z)$. The estimate of
$\mathbb{E}[Y_{d}(z)Y_{d}(w)]$ now follows from (7.5) and the bound (7.4).
This finishes the proof of Proposition 2.7. ∎

###### Proof of Proposition 2.8.

We have the following multi-dimensional CLT, for any $k\in\mathbb{N}$,

(7.6)
$\big{(}\overline{\Lambda_{1}}/\sqrt{d},\sqrt{2}\overline{\Lambda_{2}}/d,\cdots,\sqrt{k}\overline{\Lambda_{k}}/\sqrt{d^{k}}\big{)}\xrightarrow[d\to\infty]{\mathrm{law}}(N_{1},\cdots,N_{k});$

cf. Section A. In particular, we can choose a coupling, where almost surely,
$\sqrt{\ell}\overline{\Lambda_{\ell}}/\sqrt{d^{\ell}}\to(-1)^{\ell+1}N_{\ell}$
for all $\ell\in\mathbb{N}$ as $d\to\infty$. Within this coupling, and the
tightness proved in (7.1) and (7.4), we verify that almost surely,
$d\to\infty$

$\displaystyle X_{d}\to X_{\infty}\qquad\text{and}\qquad\Upsilon_{d}\to 0$

uniformly on compact subsets of $D_{1}$. ∎

##  8\.  Proofs of Theorem 2.4 and Theorem 2.6

We use the following lemma from [11], which is inspired from [51].

######  Lemma 8.1 (Lemma 3.2 in [11]).

Let $\\{f_{n}:D_{1}\to\mathbb{C}\\}$ be a sequence of random analytic
functions, $f_{n}(z)=\sum_{k=0}^{\infty}a_{k}^{(n)}z^{k}$ for
$n\in\mathbb{N}$. Assume that $\\{f_{n}\\}$ is tight and the process
$(a_{k}^{(n)})_{k\in\mathbb{N}_{0}}\to(a_{k})_{k\in\mathbb{N}_{0}}$ converges
in finite-dimensional distributions; for every $k\geq 0$,

(8.1)
$\big{(}a_{0}^{(n)},\dotsc,a_{k}^{(n)}\big{)}\xrightarrow[n\to\infty]{\mathrm{law}}\big{(}a_{0},\dotsc,a_{k}\big{)},$

then $f=\sum_{k=0}^{\infty}a_{k}z^{k}$ is convergent almost surely in $D_{1}$
and

$f_{n}\xrightarrow[n\to\infty]{\mathrm{law}}f.$

We also need the following non-trivial observation.

######  Lemma 8.2.

According to Definition 2.3,

$\mathbb{E}e^{-Y_{d}(z)}=\exp\bigg{(}\sum_{k\in\mathbb{N}}\frac{z^{k}}{kd^{k/2}}\sum_{\ell|k,\ell<k}\ell\,\mathbb{E}\Lambda_{\ell}\bigg{)}$

where the sum converges absolutely in $D_{1}$.

###### Proof.

Recall that $\mathrm{f}_{\ell}(z):=(1-z^{\ell})e^{z^{\ell}}$ for
$\ell\in\mathbb{N}$. These functions does not vanishes in $D_{1}$ so
$\log\mathrm{f}_{\ell}$ is well-defined for the principal branch of $\log$ and

$-\log\mathrm{f}_{\ell}(z)=\sum_{j\geq 2}\frac{z^{j\ell}}{j};\qquad z\in
D_{1}.$

Then, since $\mathbb{E}\Lambda_{\ell}=d^{\ell}/\ell$ for $\ell\in\mathbb{N}$,
we compute

$\displaystyle\sum_{k\in\mathbb{N}}\frac{z^{k}}{kd^{k/2}}\sum_{\ell|k,\ell<k}\ell\,\mathbb{E}\Lambda_{\ell}$
$\displaystyle=\sum_{\ell\in\mathbb{N}}\frac{d^{\ell}}{\ell}\sum_{j\geq
2}\frac{z^{j\ell}}{jd^{j\ell/2}}$
$\displaystyle=-\sum_{\ell\in\mathbb{N}}\frac{d^{\ell}}{\ell}\log\mathrm{f}_{\ell}(z/\sqrt{d})$

where all sums converge absolutely in $D_{1}$; e.g. using the bound
$\big{|}\log\mathrm{f}_{\ell}(z)\big{|}\leq\frac{r^{2\ell}}{1-r^{\ell}}$ valid
for $z\in D_{r}$. Taking $\exp$ and using formula (2.4), this proves the
claim. ∎

The characteristic polynomial of a $n\times n$ random matrix $A$ satisfies for
$z\in\mathbb{C}$,

$\chi_{n}(z)=\det(1-zA)=\sum_{k\leq n}z^{k}\Delta_{k}^{(n)}$

where $\Delta_{0}=1$ and for $k\geq 1$,

(8.2)
$\Delta_{k}=p_{k}\big{(}-\mathrm{tr}(A),\cdots,-\mathrm{tr}(A^{k})\big{)}$

where $p_{k}$ is a (multivariate) polynomial of degree $k$. These polynomials
arise by (formally) identifying the power series

(8.3)
$\exp\bigg{(}\sum_{k\in\mathbb{N}}\frac{z^{k}}{k}x_{k}\bigg{)}=1+\sum_{k\in\mathbb{N}}p_{k}(x_{1},\cdots,x_{k})z^{k},\qquad(x_{1},x_{2},\cdots)\in\mathbb{C}^{\infty}.$

In particular, they have the following property for every $k\in\mathbb{N}$;

$p_{k}\big{(}zx_{1},\cdots,z^{k}x_{k}\big{)}=z^{k}p_{k}\big{(}x_{1},\cdots,x_{k}\big{)}\qquad\text{for
$z\in\mathbb{C}$}$

and

$\big{|}p_{k}(x_{1},\cdots,x_{k})\big{|}\leq p_{k}(|x_{1}|,\cdots,|x_{k}|).$

Hence, if $\sum_{k\in\mathbb{N}}\frac{|x_{k}|}{k}r^{k}<\infty$ for $r>0$, then
both sums in (8.3) are absolutely convergent for $z\in\overline{D_{r}}$.

The underlying idea is that for $d\in\mathbb{N}$ fixed, by formula (8.2),
Theorem 3.1 (1) and the continuous mapping theorem, for every $k\in\mathbb{N}$

$\big{(}\Delta_{1}^{(n)},\dotsc,\Delta_{k}^{(n)}\big{)}\xrightarrow[n\to\infty]{\mathrm{law}}\big{(}P_{1},\dotsc,P_{k}\big{)}$

where

$P_{k}=p_{k}\bigg{(}-\Lambda_{1},\dotsc,-\sum_{\ell|k}\ell\Lambda_{\ell}\bigg{)}.$

Moreover, by Proposition 4.1 below, the characteristic polynomial
$\\{\chi_{n}\\}$ is tight in $D_{1/\sqrt{d}}$. Thus, by Lemma 8.1,

$\chi_{n}(z)\xrightarrow[n\to\infty]{\mathrm{law}}1+\sum_{k\in\mathbb{N}}P_{k}z^{k}$

locally uniformly for $z\in D_{1/\sqrt{d}}$. However, we cannot directly
identify the limit from this arguments since the series
$\sum_{k\in\mathbb{N}}\frac{z^{k}}{k}\sum_{\ell|k}\ell\Lambda_{\ell}$ does not
converge for $z\in D_{1/\sqrt{d}}$ (cf. Remark 7.1). Hence, we give a modified
version of this argument which also applies in the regime where
$d(n)\to\infty$.

###### Proof of Theorem 2.4.

Instead of the characteristic polynomial, we consider the function

$f_{n}(z)=\frac{\widehat{\chi}_{n}(z)}{z-1/\sqrt{d}}\mathbb{E}e^{-Y_{d}(z)},\qquad
z\in D_{1},n\in\mathbb{N}.$

By Lemma 8.2 and since the rescaled characteristic polynomial has a trivial
root at $z=1/\sqrt{d}$, these are still well-defined random analytic
functions. Moreover, by Proposition 4.1,
$\mathbb{E}\|\widehat{\chi}_{n}\|_{L^{\infty}(D_{e^{-t}})}\leq C_{t}$ for
$t>0$ so that by Cauchy’s formula,

$\mathbb{E}\|f_{n}\|_{L^{\infty}(D_{e^{-2t}})}\leq\int_{0}^{2\pi}\frac{\mathbb{E}\big{|}\widehat{\chi}_{n}(e^{-t+i\theta})\mathbb{E}e^{-Y_{d}(e^{-t+i\theta})}\big{|}}{|e^{-t}-1/\sqrt{d}||e^{-t}-e^{-2t}|}\frac{d\theta}{2\pi}$

which is bounded uniformly for $n\in\mathbb{N}$. This shows that $\\{f_{n}\\}$
is tight. We can expand

$f_{n}(z)=1+\sum_{k\in\mathbb{N}}a_{k}^{(n)}z^{k};\qquad
a_{k}^{(n)}=p_{k}\bigg{(}-\frac{\mathrm{tr}(A)-\mathbb{E}\Lambda_{1}}{\sqrt{d}},\dots,-\frac{\mathrm{tr}(A^{k})-\sum_{\ell|k}\ell\mathbb{E}\Lambda_{\ell}}{\sqrt{d^{k}}}\bigg{)}.$

This follows from (8.3) and the facts that

$\widehat{\chi}_{n}(z)=\exp\bigg{(}-\sum_{k\geq
1}\frac{z^{k}}{kd^{k/2}}\mathrm{tr}(A^{k})\bigg{)}/\sqrt{d}$

(the sum converges at least for $z$ in a small neighborhood of $0$ since we
have the crude bound $|\mathrm{tr}(A^{k})|\leq(nd)^{k}$ because the entries of
$A$ are bounded by $d$) and according to Lemma 8.2,

$\frac{\mathbb{E}e^{-Y_{d}(z)}}{1-z\sqrt{d}}=\exp\bigg{(}\sum_{k\in\mathbb{N}}\frac{z^{k}}{kd^{k/2}}\sum_{\ell|k}\ell\,\mathbb{E}\Lambda_{\ell}\bigg{)},\qquad
z\in D_{1/\sqrt{d}}.$

Hence, for a fixed $d\in\mathbb{N}$, by Theorem 3.1 (1) and the continuous
mapping theorem, it holds for every $k\in\mathbb{N}$

$\big{(}a_{1}^{(n)},\dotsc,a_{k}^{(n)}\big{)}\xrightarrow[n\to\infty]{\mathrm{law}}\big{(}a_{1},\dotsc,a_{k}\big{)},$

where

$a_{k}=d^{-k/2}p_{k}\bigg{(}-\overline{\Lambda_{1}},\dots,-\sum_{\ell|k}\ell\overline{\Lambda_{\ell}}\bigg{)}.$

By Lemma 8.1, we conclude that

$f_{n}(z)=\frac{\widehat{\chi}_{n}(z)}{z-1/\sqrt{d}}\mathbb{E}e^{-Y_{d}(z)}\xrightarrow[n\to\infty]{\mathrm{law}}f(z)=1+\sum_{k\in\mathbb{N}}a_{k}z^{k}.$

Moreover, from the proof of Proposition 2.7, it holds almost surely
$\sum_{k\in\mathbb{N}}\frac{r^{k}}{kd^{k/2}}\big{|}\sum_{\ell|k}\ell\overline{\Lambda_{\ell}}\big{|}<\infty$
for any $r<1$. By (8.3) and the subsequent observation, it follows that

$e^{-Y_{d}(z)}=1+\sum_{k\in\mathbb{N}}a_{k}z^{k}$

is the weak-limit of the sequence $\\{f_{n}\\}$. This completes the proof. ∎

###### Proof of Theorem 2.6.

This is a variant of the previous argument. We consider the function

$f_{n}(z)=\frac{\widehat{\chi}_{n}(z)}{z-1/\sqrt{d}},\qquad z\in
D_{1},n\in\mathbb{N}.$

By Proposition 4.1 and Cauchy’s formula, $\\{f_{n}\\}$ is tight (the fact that
$1/\sqrt{d}\to 0$ is not relevant). In this case, we have the expansion

$f_{n}(z)=1+\sum_{k\in\mathbb{N}}a_{k}^{(n)}z^{k};\qquad
a_{k}^{(n)}=p_{k}\bigg{(}-\frac{\mathrm{tr}(A)-d}{\sqrt{d}},\dots,-\frac{\mathrm{tr}(A^{k})-d^{k}}{\sqrt{d^{k}}}\bigg{)}.$

Hence, by Theorem 3.1 (2) and the continuous mapping theorem, in the regime
where $d=d(n)\to\infty$ and $d(n)=n^{o(1)}$, it holds for every
$k\in\mathbb{N}$

$\big{(}a_{1}^{(n)},\dotsc,a_{k}^{(n)}\big{)}\xrightarrow[n\to\infty]{\mathrm{law}}\big{(}a_{1},\dotsc,a_{k}\big{)},$

where

$a_{k}=p_{k}\left(N_{1},\sqrt{2}N_{2}-1,\dotsc,\sqrt{k}N_{k}-\mathbf{1}_{\\{k\text{
is even}\\}}\right).$

using the symmetry of $N_{k}$. Now, we verify that for $z\in D_{1}$,

$\sqrt{1-z^{2}}e^{X_{\infty}(z)}=\exp\bigg{(}\sum_{k\in\mathbb{N}}\frac{z^{k}}{k}\big{(}\sqrt{k}N_{k}-\mathbf{1}_{\\{k\text{
is even}\\}}\big{)}\bigg{)},$

where the sum converges absolutely for $z\in\overline{D_{r}}$ for any $r<1$.
Hence, we conclude that if $d(n)\to\infty$ and $d(n)=n^{o(1)}$, then

$f_{n}(z)=\frac{\widehat{\chi}_{n}(z)}{z-1/\sqrt{d}}\xrightarrow[n\to\infty]{\mathrm{law}}\sqrt{1-z^{2}}e^{X_{\infty}(z)}.$

This proves the claim. ∎

##  9\. Proof of spectral gaps

There are two popular models to generate simple random regular digraphs:

  1. (1)

Permutation model: Let $A=\sum_{i=1}^{d}P^{(i)}$ be a sum of $d$ independent
uniformly random permutations. Sample $A$ conditioned on $A$ being an
adjacency matrix of a simple digraph.

  2. (2)

Uniform model: Sample a $d$-regular digraph uniformly from all $d$-regular
digraphs with $n$ vertices.

It was proved in [34] and [43] that the two models are contiguous, which means
if a sequence of events happens asymptotically almost surely in model, it
holds for the other model as well. For fixed $d$, our Theorem 2.4 can be
applied to show a spectral gap result for the two models.

The proof follows the same way as in [11, Theorem 1.1] and [19, Theorem 2.6].
We will use the following proposition from [51]. We identify multisets with
integer-valued Radon measures and endow the space of multisets with the
topology of vague convergence, and the space of random multisets with the
topology of weak convergence with respect to the topology of vague convergene.

######  Proposition 9.1 (Proposition 2.3 in [51]).

Let $f_{n}$ be a sequence of random functions in $D_{r}$ converging in law to
a non-zero function $f$. Let $\Phi_{n}$ and $\Phi$ be the random multisets of
the zeros of $f_{n},f$ in $D_{r}$, respectively. Then $\Phi_{n}$ converges in
law towards $\Phi$.

###### Proof of Theorem 1.1 .

We first prove the statement for case (i): the sum of random permutations. Let
$f(z)$ be the limiting function of $\widehat{\chi}_{n}$. Then from Theorem
2.4, for any $0<r<1$, $f(z)$ has only one zero in $D_{r}$ at $-1/\sqrt{d}$. By
Proposition 9.1, with high probability $\widehat{\chi}_{n}(z)$ has only one
zero at $-1/\sqrt{d}$, which implies $A/\sqrt{d}$ has no eigenvalue outside
$D_{1/r}$ except $\sqrt{d}$. For any $\varepsilon>0$, take
$\frac{1}{1+\varepsilon/\sqrt{d}}<r<1$, then as $n\to\infty$,

$\displaystyle\mathbf{P}(|\lambda_{2}|>\sqrt{d}+\varepsilon)\leq\mathbf{P}\left(\frac{|\lambda_{2}|}{\sqrt{d}}>\frac{1}{r}\right)\to
0.$

It was shown in [43] that the probability that $A$ is simple is bounded from
below when $d$ is fixed. Therefore $|\lambda_{2}|>\sqrt{d}$ holds
asymptotically almost surely for case (ii). By contiguity between model (ii)
and model (iii), it holds for uniform random $d$ regular digraphs as well. ∎

When $d(n)\to\infty$, there is no contiguity result in the literature between
the two models (1) and (2), and we are not aware of any result to provide a
constant lower bound on the probability that $A=\sum_{i=1}^{d(n)}P^{(i)}$
being simple. So our Theorem 2.6 only gives a result for sums of random
permutations.

###### Proof of Theorem 1.2.

In Theorem 2.6, $\frac{\widehat{\chi}_{n}(z)}{z-1/\sqrt{d}}$ converges in law
to the limiting function $\sqrt{1-z^{2}}e^{X_{\infty}(z)}$, which has no root
inside $D_{r}$ for any $r\in(0,1)$. From Proposition 9.1, with high
probability $\frac{\widehat{\chi}_{n}(z)}{z-1/\sqrt{d}}$ has no roots in
$D_{r}$ for any $0<r<1$. Then $A/\sqrt{d(n)}$ has no eigenvalue outside
$D_{1/r}$ except for $\sqrt{d(n)}$. Therefore (1.1) holds. ∎

##  Appendix A Appendix: a Poisson CLT

Let $\Lambda\sim\mathrm{Poisson}(\lambda)$. Recall that the Laplace transform
of $\Lambda$ is

$\mathbb{E}\exp(z(\Lambda-\lambda))=\exp\big{(}\lambda(e^{z}-1-z)\big{)},\qquad
z\in\mathbb{C}.$

Let $\mu_{k}(\lambda)=\mathbb{E}(\Lambda-\lambda)^{k}$ be the central moments
of $\Lambda$ for $k\in\mathbb{N}$. We have for $k\in\mathbb{N}$

$\mu_{k}(\lambda)/k!=[z^{k}]\exp\big{(}\lambda(e^{z}-1-z)\big{)}.$

In particular, $\mu_{1}=0$ and for $k\in\mathbb{N}$,

(A.1)
$\displaystyle\begin{cases}\mu_{2k}(\lambda)=m_{k}\lambda^{k}+p_{k}(\lambda),&p_{k}\in\mathcal{P}_{k-1}\\\
\mu_{2k+1}\in\mathcal{P}_{k}\end{cases}$

where $m_{k}=\tfrac{(2k)!}{2^{k}k!}$, and
$\mathcal{P}_{k}=\\{\text{polynomials of degree }\leq k\\}$. From this fact,
we deduce that for every $k\in\mathbb{N}$,

(A.2)
$\frac{\mu_{k}(\lambda)}{\lambda^{k/2}}=\mathbb{E}\bigg{(}\frac{\Lambda-\lambda}{\sqrt{\lambda}}\bigg{)}^{k}\xrightarrow[\lambda\to\infty]{}\mathbb{E}N^{k}=\begin{cases}m_{k/2}&k\text{
even}\\\ 0&k\text{ odd}\end{cases},$

where $N$ is a standard Gaussian. This is a CLT in the sense of moments for a
Poisson random variable.

The goal of this appendix is to extend this results to a collection of
asymptotically Poisson random variables with large parameters. First recall
that we can expand for $k\in\mathbb{N}$,

(A.3)
$(x-\lambda)^{k}=\textstyle{\sum_{j=0}^{k}}(x)_{k-j}q_{k,j}(\lambda);\qquad
q_{k,j}\in\mathcal{P}_{j}.$

Then, according to Lemma 6.8, we have

(A.4) $\mu_{k}(\lambda)=\sum_{j\leq
k}q_{k,j}(\lambda)\mathbb{E}(\Lambda)_{k-j}=\sum_{j\leq
k}q_{k,j}(\lambda)\lambda^{k-j}.$

Remarkably, from (A.1), the RHS is a polynomial in $\lambda$ of degree $\leq
k/2$.

######  Lemma A.1.

Fix $\ell\in\mathbb{N}$ and for $j\in[\ell]$, let
$(\lambda_{j,n})_{n\in\mathbb{N}}$ be a sequence in $\mathbb{R}_{+}$ such that
$\lambda_{j,n}\to\infty$ as $n\to\infty$. Let
$(Q_{j,n})_{j\in[\ell],n\in\mathbb{N}}$ be a sequence of random vectors such
that its joint factorial moments satisfy for any
$\mathbf{k}\in\mathbb{N}^{\ell}$,

(A.5)
$\mathbb{E}\big{[}(Q_{1,n})_{k_{1}}\cdots(Q_{\ell,n})_{k_{\ell}}\big{]}=\lambda_{1,n}^{k_{1}}\cdots\lambda_{\ell,n}^{k_{\ell}}(1+\epsilon_{\mathbf{k},n})$

where $\epsilon_{\mathbf{k},n}\in\mathbb{R}$ and for
$\mathbf{k}\in\mathbb{N}^{\ell}$,

(A.6)
$\lambda_{1,n}^{k_{1}/2}\cdots\lambda_{\ell,n}^{k_{\ell}/2}\cdot\max_{\mathbf{j}\leq\mathbf{k}}|\epsilon_{\mathbf{j},n}|\to
0.$

Then

$\left(\frac{Q_{1,n}-\lambda_{1,n}}{\sqrt{\lambda_{1,n}}},\dots,\frac{Q_{\ell,n}-\lambda_{\ell,n}}{\sqrt{\lambda_{\ell,n}}}\right)\xrightarrow[n\to\infty]{\mathrm{law}}\big{(}N_{1},\dots,N_{\ell}\big{)}$

and in the sense of moments, where $(N_{i})_{i\in[\ell]}$ are i.i.d. standard
Gaussians.

###### Proof.

Let us denote
$\mu_{\mathbf{k},n}=\mathbb{E}\big{[}(Q_{1,n}-\lambda_{1,n})^{k_{1}}\cdots(Q_{\ell,n}-\lambda_{\ell,n})^{k_{\ell}}\big{]}$
for $\mathbf{k}\in\mathbb{N}^{\ell}$. Using (A.3) and (A.5), we can write

$\displaystyle\mu_{\mathbf{k},n}$
$\displaystyle=\sum_{\mathbf{j}\leq\mathbf{k}}\prod_{i\leq\ell}q_{k_{i},j_{i}}(\lambda_{i,n})\mathbb{E}\big{[}(Q_{1,n})_{k_{1}-j_{1}}\cdots(Q_{\ell,n})_{k_{\ell}-j_{\ell}}\big{]}$
$\displaystyle=\sum_{\mathbf{j}\leq\mathbf{k}}\prod_{i\leq\ell}q_{k_{i},j_{i}}(\lambda_{i,n})\lambda_{i,n}^{k_{i}-j_{i}}(1+\epsilon_{\mathbf{k-j},n}).$

Then, the conditions (A.6) imply that for any fixed
$\mathbf{k}\in\mathbb{N}^{\ell}$,

$\mu_{\mathbf{k},n}=\prod_{i\leq\ell}\bigg{(}\sum_{j\leq
k_{i}}q_{k_{i},j}(\lambda_{i,n})\lambda_{i,n}^{k_{i}-j}\bigg{)}+\underset{n\to\infty}{o_{\mathbf{k}}}\big{(}\lambda_{1,n}^{k_{1}/2}\cdots\lambda_{\ell,n}^{k_{\ell}/2}\big{)}.$

Here we used that $q_{k,j}\in\mathcal{P}_{j}$. Hence using the combinatorial
identity (A.4),

$\mu_{k,n}=\mu_{k_{1}}(\lambda_{1,n})\cdots\mu_{k_{\ell}}(\lambda_{\ell,n})+\underset{n\to\infty}{o_{\mathbf{k}}}\big{(}\lambda_{1,n}^{k_{1}/2}\cdots\lambda_{\ell,n}^{k_{\ell}/2}\big{)}.$

From (A.2), we conclude that for every $\mathbf{k}\in\mathbb{N}^{\ell}$,

$\frac{\mathbb{E}\big{[}(Q_{1,n}-\lambda_{1,n})^{k_{1}}\cdots(Q_{\ell,n}-\lambda_{\ell,n})^{k_{\ell}}\big{]}}{\lambda_{1,n}^{k_{1}/2}\cdots\lambda_{\ell,n}^{k_{\ell}/2}}\xrightarrow[n\to\infty]{}\mathbb{E}\big{[}N_{1}^{k_{1}}\cdots
N_{\ell}^{k_{\ell}}\big{]}.$

This completes the proof, since the law of $(N_{i})_{i\in[\ell]}$ is
characterized by its joint moments. ∎

##  Appendix B Appendix: sums of non-uniform random permutations

In this paper, we studied random digraphs arising as sums of $n\times n$
uniform permutations. A crucial technical argument in our analysis was that
the rows of the matrix $A=P^{(1)}+\dotsb+P^{(d)}$ are exchangeable; but this
property is in fact very strong. It would not hold if the permutation matrices
$P^{(i)}$ were not uniformly distributed on $S_{n}$. This is typically what
happens when they are skewed towards having more or fewer short cycles. For
example, the Ewens distribution with parameter $\theta$ is defined as follows;
we say that a random permutation $\pi$ is $\mathrm{Ewens}(\theta)$-distributed
if

$\forall\sigma\in
S_{n},\qquad\mathbb{P}(\pi=\sigma)=\frac{\theta^{\mathrm{cyc}(\sigma)}}{\theta(\theta+1)\dotsb(\theta+n-1)},$

where $\mathrm{cyc}(\sigma)$ is the number of cycles in the cycle
decomposition of $\sigma$. When $\theta=1$, the random permutation $\pi$ is
uniform; when $\theta>1$ (respectively, $<1$), it is skewed towards having
more cycles (respectively, less), resulting in a directed graph with a
different local structure. Crucially, Ewens-distributed random permutations
with $\theta\neq 1$ are invariant by _conjugation_ by any permutation matrix,
but not invariant by multiplication by a permutation matrix.

We were able to identify the asymptotics of the traces of
$A=P^{(1)}+\dotsb+P^{(d)}$ is this model, with $\theta$ fixed and not
depending on $n$; indeed, Theorem 3.1 still holds, with the limiting random
variables $\Lambda_{\ell}$ being replaced with the following ones:

$\Theta_{\ell}\sim\mathrm{Poisson}\left(\frac{d^{\ell}+d(\theta-1)}{\ell}\right).$

A proof is available on demand; however, the proof of the tightness of the
sequence $\det(I-zA_{n})$ is still under exploration. We mention this fact,
since the asymptotic behaviour of the spectrum of $A$ in the Ewens case
displays some unusual features; when $\theta$ is sufficiently large (this
might depend on $n$), the whole limiting shape of the eigenvalues seems not
rotation-invariant, with a previously unseen pattern of eigenvector
localization — see Figure 2. For comparison, Figure 3 displays the eigenvalues
of our model of sums-of-permutation matrices, together with an example of a
real Ginibre spectrum.

We note that the continuous counterpart of the Ewens measure on permutations,
is a generalization of the Haar measure on the unitary group, which is called
the Hua-Pickrell measure [30, 48], also known as the circular Jacobi ensembles
[12]. It is also an interesting question to study the limiting spectral
distribution for sums of independent unitary matrices sampled from the Hua-
Pickrell distribution beyond the Haar case [6].

|  |
---|---|---
$\theta=0.0001$ | $\theta=100$ | $\theta=500$
Figure 2. These figures display the $n=2000$ complex eigenvalues of sums of $d=3$ permutations matrices, the underlying permutations being $\mathrm{Ewens}(\theta)$-distributed on $\mathfrak{S}_{2000}$ for various $\theta$. Each eigenvalue is coloured according to the degree of localization of its corresponding right-eigenvector; here, we measure the localisation of a vector $\varphi\in\mathbb{C}^{n}$ using the Inverse Participation Ratio $\mathrm{IPR}(\varphi)=|\varphi|_{2}^{4}/n|\varphi|_{4}^{4}\leqslant 1$. An IPR equal to 1 means that $\varphi$ is constant up to phases (pure delocalization); an IPR equal to $1/n$ means that $\varphi$ is a multiple of a Dirac (pure localization). Here, we see that the eigenvectors with eigenvalues close to the real axis are more localized, a phenomenon already visible for classical matrix ensembles such as Ginibre (see Figure 3).  |  |
---|---|---
$d=2$ | $d=3$ | Ginibre ensemble
Figure 3. These figures display the $n=2000$ complex eigenvalues of sums of
$d$ uniform permutations matrices, with eigenvector localization depicted as
the Figure 2. We plotted in the third panel the eigenvalues of a Real Ginibre
matrix (the entries are iid $N_{\mathbb{R}}(0,1/n)$) for comparison.

## References

  * [1] Louis-Pierre Arguin, David Belius, and Paul Bourgade.  Maximum of the characteristic polynomial of random unitary matrices.  Communications in Mathematical Physics, 349(2):703–751, 2017.
  * [2] Valentin Bahier.  Characteristic polynomials of modified permutation matrices at microscopic scale.  Stochastic Processes and their Applications, 129(11):4335–4365, 2019.
  * [3] Valentin Bahier.  On the number of eigenvalues of modified permutation matrices in mesoscopic intervals.  Journal of Theoretical Probability, 32(2):974–1022, 2019.
  * [4] Valentin Bahier and Joseph Najnudel.  On smooth mesoscopic linear statistics of the eigenvalues of random permutation matrices.  Journal of Theoretical Probability, pages 1–22, 2021.
  * [5] Anirban Basak, Nicholas Cook, and Ofer Zeitouni.  Circular law for the sum of random permutation matrices.  Electronic Journal of Probability, 23:1–51, 2018.
  * [6] Anirban Basak and Amir Dembo.  Limiting spectral distribution of sum of unitary and orthogonal matrices.  Electronic Communications in Probability, 18:1–19, 2013.
  * [7] Anirban Basak and Mark Rudelson.  The circular law for sparse non-Hermitian matrices.  The Annals of Probability, 47(4):2359–2416, 2019.
  * [8] Gérard Ben Arous and Kim Dang.  On fluctuations of eigenvalues of random permutation matrices.  Annales de l’IHP Probabilités et statistiques, 51(2):620–647, 2015.
  * [9] Charles Bordenave.  A new proof of Friedman’s second eigenvalue theorem and its extension to random lifts.  Annales Scientifiques de l’École Normale Supérieure, 4(6):1393–1439, 2020.
  * [10] Charles Bordenave and Djalil Chafaï.  Around the circular law.  Probability surveys, 9:1–89, 2012.
  * [11] Charles Bordenave, Djalil Chafaï, and David García-Zelada.  Convergence of the spectral radius of a random matrix through its characteristic polynomial.  Probability Theory and Related Fields, pages 1–19, 2021.
  * [12] Paul Bourgade, Ashkan Nikeghbali, and Alain Rouault.  Ewens measures on compact groups and hypergeometric kernels.  In Séminaire de probabilités XLIII, pages 351–377. Springer, 2011.
  * [13] Reda Chhaibi, Thomas Madaule, and Joseph Najnudel.  On the maximum of the C$\beta$E field.  Duke Mathematical Journal, 167(12):2243–2345, 2018.
  * [14] Nicholas Cook.  The circular law for random regular digraphs.  Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 55(4):2111–2167, 2019.
  * [15] Nicholas Cook, Larry Goldstein, and Tobias Johnson.  Size biased couplings and the spectral gap for random regular graphs.  The Annals of Probability, 46(1):72–125, 2018.
  * [16] Nicholas Cook and Ofer Zeitouni.  Maximum of the characteristic polynomial for a random permutation matrix.  Communications on Pure and Applied Mathematics, 73(8):1660–1731, 2020.
  * [17] Nicholas A Cook.  Discrepancy properties for random regular digraphs.  Random Structures & Algorithms, 50(1):23–58, 2017.
  * [18] Nicholas A Cook.  On the singularity of adjacency matrices for random regular digraphs.  Probability Theory and Related Fields, 167(1):143–200, 2017.
  * [19] Simon Coste.  Sparse matrices: convergence of the characteristic polynomial seen from infinity.  arXiv preprint arXiv:2106.00593, 2021.
  * [20] Simon Coste.  The spectral gap of sparse random digraphs.  Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 57(2):644–684, 2021.
  * [21] Kim Dang and Dirk Zeindler.  The characteristic polynomial of a random permutation matrix at different points.  Stochastic Processes and their Applications, 124(1):411–439, 2014\.
  * [22] Ioana Dumitriu, Tobias Johnson, Soumik Pal, and Elliot Paquette.  Functional limit theorems for random regular graphs.  Probability Theory and Related Fields, 156(3):921–975, 2013.
  * [23] Ioana Dumitriu and Yizhe Zhu.  Global eigenvalue fluctuations of random biregular bipartite graphs.  arXiv preprint arXiv:2008.11760, 2020.
  * [24] Bertrand Duplantier, Rémi Rhodes, Scott Sheffield, and Vincent Vargas.  Log-correlated Gaussian fields: an overview.  Geometry, analysis and probability, pages 191–216, 2017.
  * [25] Joel Friedman.  A Proof of Alon’s Second Eigenvalue Conjecture and Related Problems.  Memoirs of the American Mathematical Society. American Mathematical Society, 2008.
  * [26] Joel Friedman, Jeff Kahn, and Endre Szemeredi.  On the second eigenvalue of random regular graphs.  In Proceedings of the twenty-first annual ACM symposium on Theory of computing, pages 587–598, 1989.
  * [27] Yan V Fyodorov and Olivier Giraud.  High values of disorder-generated multifractals and logarithmically correlated processes.  Chaos, Solitons & Fractals, 74:15–26, 2015.
  * [28] Yan V Fyodorov, Ghaith A Hiary, and Jonathan P Keating.  Freezing transition, characteristic polynomials of random matrices, and the Riemann zeta function.  Physical Review Letters, 108(17):170601, 2012.
  * [29] Shirshendu Ganguly and Soumik Pal.  The random transposition dynamics on random regular graphs and the Gaussian free field.  Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 56(4):2935–2970, 2020.
  * [30] Luogeng Hua.  Harmonic analysis of functions of several complex variables in the classical domains.  Number 6. American Mathematical Soc., 1963.
  * [31] Jiaoyang Huang.  Invertibility of adjacency matrices for random $d$-regular graphs.  Duke Mathematical Journal, 170(18):3977–4032, 2021.
  * [32] Christopher Hughes, Joseph Najnudel, Ashkan Nikeghbali, and Dirk Zeindler.  Random permutation matrices under the generalized ewens measure.  The Annals of Applied Probability, 23(3):987–1024, 2013.
  * [33] Vishesh Jain, Ashwin Sah, and Mehtaab Sawhney.  The smallest singular value of dense random regular digraphs.  International Mathematics Research Notices, 09 2021.  rnab247.
  * [34] Svante Janson.  Random regular graphs: asymptotic distributions and contiguity.  Combinatorics, Probability and Computing, 4(4):369–405, 1995.
  * [35] Tobias Johnson and Soumik Pal.  Cycles and eigenvalues of sequentially growing random regular graphs.  The Annals of Probability, 42(4):1396–1437, 2014.
  * [36] Gaultier Lambert.  Mesoscopic central limit theorem for the circular $\beta$-ensembles and applications.  Electronic Journal of Probability, 26:1–33, 2021.
  * [37] Gaultier Lambert and Elliot Paquette.  Strong approximation of Gaussian beta-ensemble characteristic polynomials: the hyperbolic regime.  arXiv preprint arXiv:2001.09042, 2020.
  * [38] Alexander E Litvak, Anna Lytova, Konstantin Tikhomirov, Nicole Tomczak-Jaegermann, and Pierre Youssef.  Adjacency matrices of random digraphs: singularity and anti-concentration.  Journal of Mathematical Analysis and Applications, 445(2):1447–1491, 2017.
  * [39] Alexander E Litvak, Anna Lytova, Konstantin Tikhomirov, Nicole Tomczak-Jaegermann, and Pierre Youssef.  The smallest singular value of a shifted d-regular random square matrix.  Probability Theory and Related Fields, 173(3):1301–1347, 2019.
  * [40] Alexander E Litvak, Anna Lytova, Konstantin Tikhomirov, Nicole Tomczak-Jaegermann, and Pierre Youssef.  Circular law for sparse random regular digraphs.  Journal of the European Mathematical Society, 23(2):467–501, 2020\.
  * [41] András Mészáros.  The distribution of sandpile groups of random regular graphs.  Transactions of the American Mathematical Society, 373(9):6529–6594, 2020.
  * [42] Fernando Lucas Metz, Izaak Neri, and Tim Rogers.  Spectral theory of sparse non-Hermitian random matrices.  Journal of Physics A: Mathematical and Theoretical, 52(43):434003, 2019.
  * [43] Michael S. O. Molloy, Hanna Robalewska, Robert W. Robinson, and Nicholas C. Wormald.  1-factorizations of random regular graphs.  Random Structures & Algorithms, 10(3):305–321, 1997.
  * [44] Joseph Najnudel, Elliot Paquette, and Nick Simm.  Secular coefficients and the holomorphic multiplicative chaos.  arXiv preprint arXiv:2011.01823, 2020.
  * [45] Miika Nikula, Eero Saksman, and Christian Webb.  Multiplicative chaos and the characteristic polynomial of the CUE: The ${L}_{1}$ phase.  Transactions of the American Mathematical Society, 373(6):3905–3965, 2020.
  * [46] Elliot Paquette and Ofer Zeitouni.  The maximum of the CUE field.  International Mathematics Research Notices, 2018(16):5028–5119, 2018.
  * [47] Ori Parzanchevski.  Ramanujan graphs and digraphs.  Analysis and Geometry on Graphs and Manifolds, 461:344, 2020.
  * [48] Doug Pickrell.  Measures on infinite dimensional grassmann manifolds.  Journal of Functional Analysis, 70(2):323–356, 1987.
  * [49] Brian Rider and Bálint Virág.  The noise in the circular law and the Gaussian free field.  International Mathematics Research Notices, 2007(9):rnm006, 2007\.
  * [50] Mark Rudelson and Konstantin Tikhomirov.  The sparse circular law under minimal assumptions.  Geometric and Functional Analysis, 29(2):561–637, 2019.
  * [51] Tomoyuki Shirai.  Limit theorems for random analytic functions and their zeros: Dedicated to the late Professor Yasunori Okabe (functions in number theory and their probabilistic aspects).  RIMS Kokyuroku Bessatsu, 34:335–359, 2012.
  * [52] Konstantin Tikhomirov and Pierre Youssef.  The spectral gap of dense random regular graphs.  The Annals of Probability, 47(1):362–419, 2019.
  * [53] Philip Matchett Wood.  Universality and the circular law for sparse random matrices.  The Annals of Applied Probability, 22(3):1266–1300, 2012.
  * [54] Yizhe Zhu.  On the second eigenvalue of random bipartite biregular graphs.  arXiv preprint arXiv:2005.08103, 2020.