The circular law for random regular digraphs

, 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}

.

Review text

The article extends some recent work on the circular law for the distribution of eigenvalues of random matrices. An archetypal result here is a substantial theorem of \textit{T. Tao} and \textit{V. H. Vu} [Ann. Math. (2) 169, No. 2, 595--632 (2009; Zbl 1250.60023)] which states the following: if \(\xi\) is a random variable with mean 0 and variance 1 and \(X_{n}\) is an \(n\times n\) matric whose entries are i.i.d copies of \(\xi\), and \(\lambda_{1},\lambda_{2},\ldots ,\lambda_{n}\) are the eigenvalues of \(X_{n}\) then, letting the empirical spectral distribution (ESD) be \[ \mu_{X_{n}}=\frac{1}{n}\sum_{i=1}^{n}\delta_{\lambda_{i}} \] we have that the rescaled ESDs \(\mu_{\frac{1}{\sqrt{N}}X_{n}}\) converge to normalized Lebesgue measure on the unit disk \(\mu_{\text{circ}}\). The contribution of the paper under review is to consider the case of \(d\)-regular digraph adjacency matrices (i.e., indegree \(d\) and outdegree \(d\) at every vertex, with loops allowed). Here of course there is less independence, thus making proofs still more challenging. The main result is that letting \[ \tilde{A}=\frac{1}{\sqrt{d(1-d/n)}}A \] then, provided \(d=d(n)\) satisfies the mild condition \(\min\{d,n-d\}\geq \log^{C_{0}}(n)\) for some large enough constant \(C_{0}\). for \(A_{n}\) a uniformly-at-random selected \(d\)-regular digraph adjacency matrix we have \[ \mu_{\tilde{A_{n}}}\to \mu_{\text{circ}} \] where the arrow denotes convergence in probability. Issues needing addressed in the proof include control of the smallest singular value and use of pseudo-randomness properties of \(d\)-regular digraphs, and many other substantial technical issues. The author conjectures that the \(\log^{C_{0}}(n)\) condition on \(\min\{d,n-d\}\) (it is noted that \(C_{0}\) can be taken to be \(96\) in the paper but this may well not be optimal) can be replaced by any function tending to infinity with \(n\).

Recommendations

Cites work

Cited in

(25)

This page was built for publication: The circular law for random regular digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2291966)