The rank of random regular digraphs of constant degree

Let d be a (large) integer. Given n≥2d, let An be the adjacency matrix of a random directed d-regular graph on n vertices, with the uniform distribution. We show that the rank of An is at least n−1 with probability going to one as n grows to infinity. The proof combines the well known method of simp...

Full description

Saved in:
Bibliographic Details
Published in:Journal of Complexity 2018-10, Vol.48, p.103-110
Main Authors: Litvak, Alexander E., Lytova, Anna, Tikhomirov, Konstantin, Tomczak-Jaegermann, Nicole, Youssef, Pierre
Format: Article
Language:English
Subjects:
Mathematics
Probability
Random matrices
Random regular graphs
Rank
Singularity probability
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let d be a (large) integer. Given n≥2d, let An be the adjacency matrix of a random directed d-regular graph on n vertices, with the uniform distribution. We show that the rank of An is at least n−1 with probability going to one as n grows to infinity. The proof combines the well known method of simple switchings and a recent result of the authors on delocalization of eigenvectors of An.
ISSN:0885-064X
1090-2708
DOI:10.1016/j.jco.2018.05.004