The circular law for random regular digraphs

Abstract

Let ${\log }^{C}n\le d\le n/2$ for a sufficiently large constant $C>0$ and let $A_n$ denote the adjacency matrix of a uniform random $d$-regular directed graph on $n$ vertices. We prove that as $n$ tends to infinity, the empirical spectral distribution of $A_n$, suitably rescaled, is governed by the Circular Law. A key step is to obtain quantitative lower tail bounds for the smallest singular value of additive perturbations of $A_n$.

arXiv comment63 pages, 3 figures. Added an appendix proving Lemma 9.2, which previously relied on an unpublished result. Also added some references in the introduction