Conference abstracts

Session B5 - Random Matrices

July 15, 14:30 ~ 14:55 - Room B3

The smallest singular value of adjacency matrices of random regular digraphs

Konstantin Tikhomirov

Princeton University, USA   -   kt12@math.princeton.edu

Let $A_n$ be the adjacency matrix of a random $d$-regular directed graph on $n$ vertices, distributed uniformly on the set of all $d$-regular digraphs without multiple edges. By combining a specially developed chaining method with linear algebraic arguments and Littlewood-Offord-type anti-concentration inequalities, we derive a lower bound for the smallest singular value of matrices of the form $A_n - z {\rm Id}_n$. Our result gives a bound $s_{\rm min} \geq  n^{-C}$ with probability at least $1 - d^{-c}$, for any $d$ larger than an absolute constant and less than $n/ \log n$. This result can be viewed as a step towards proving the circular law for uniform random digraphs in the ``sparse'' regime, complementing a recent result of Cook who established the circular law for $d$ at least polylogarithmic in $n$.

Joint work with A. E. Litvak (Alberta), A. Lytova (Alberta), N. Tomczak-Jaegermann (Alberta) and P. Youssef (Paris-Diderot).

View abstract PDF



FoCM 2017, based on a nodethirtythree design.