Circular law for sparse random regular digraphs

Abstract

Fix a constant $C\ge 1$ and let $d=d(n)$ satisfy $d\le {\ln }^{C}n$ for every large integer $n$. Denote by $A_n$ the adjacency matrix of a uniform random directed $d$-regular graph on $n$ vertices. We show that if $d\to \infty$ as $n\to \infty$, the empirical spectral distribution of the appropriately rescaled matrix $A_n$ converges weakly in probability to the circular law. This result, together with an earlier work of Cook, completely settles the problem of weak convergence of the empirical distribution in a directed $d$-regular setting with the degree tending to infinity. As a crucial element of our proof, we develop a technique of bounding intermediate singular values of $A_n$ based on studying random normals to rowspaces and on constructing a product structure to deal with the lack of independence between matrix entries.