The smallest singular value of dense random regular digraphs

DOI10.1093/IMRN/RNAB247MaRDI QIDQ6346875arXivFDO

Authors Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

Publication date 11 August 2020

Published in arXiv

Full work available at URL https://doi.org/10.1093/IMRN/RNAB247

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80)

arXiv classification

math.COmath.PR

Abstract: Let $A$ be the adjacency matrix of a uniformly random $d$-regular digraph on $n$ vertices, and suppose that $min(d,n-d)geqlambdan$. We show that for any $kappageq0$, [mathbb{P}[s_n(A)leqkappa]leq C_lambdakappasqrt{n}+2e^{-c_lambda n}.] Up to the constants $C_{l}ambda,c_{l}ambda>0$, our bound matches optimal bounds for $nimesn$ random matrices, each of whose entries is an i.i.d $extBer(d/n)$ random variable. The special case $kappa=0$ of our result confirms a conjecture of Cook regarding the probability of singularity of dense random regular digraphs.

This page was built for publication: The smallest singular value of dense random regular digraphs

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