Circular law for sparse random regular digraphs

  • Alexander E. Litvak

    University of Alberta, Edmonton, Canada
  • Anna Lytova

    University of Opole, Poland
  • Konstantin Tikhomirov

    Princeton University, USA
  • Nicole Tomczak-Jaegermann

    University of Alberta, Edmonton, Canada
  • Pierre Youssef

    Université Paris-Diderot, France
Circular law for sparse random regular digraphs cover
Download PDF

This article is published open access under our Subscribe to Open model.


Fix a constant C1C\geq 1 and let d=d(n)d=d(n) satisfy dlnCnd\leq \mathrm {ln}^{C} n for every large integer nn. Denote by AnA_n the adjacency matrix of a uniform random directed dd-regular graph on nn vertices. We show that if dd\to\infty as nn \to \infty, the empirical spectral distribution of the appropriately rescaled matrix AnA_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 dd-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 AnA_n based on studying random normals to rowspaces and on constructing a product structure to deal with the lack of independence between matrix entries.

Cite this article

Alexander E. Litvak, Anna Lytova, Konstantin Tikhomirov, Nicole Tomczak-Jaegermann, Pierre Youssef, Circular law for sparse random regular digraphs. J. Eur. Math. Soc. 23 (2021), no. 2, pp. 467–501

DOI 10.4171/JEMS/1015