The rank of random regular digraphs of constant degree

Alexander E. Litvak; Anna Lytova; Konstantin Tikhomirov; Nicole Tomczak-Jaegermann; Pierre Youssef

doi:10.1016/j.jco.2018.05.004

The rank of random regular digraphs of constant degree

Alexander E. Litvak, Anna Lytova, Konstantin Tikhomirov, Nicole Tomczak-Jaegermann, Pierre Youssef

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

Abstract

Let d be a (large) integer. Given n≥2d, let A_n be the adjacency matrix of a random directed d-regular graph on n vertices, with the uniform distribution. We show that the rank of A_n 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 A_n.

Original language	English (US)
Pages (from-to)	103-110
Number of pages	8
Journal	Journal of Complexity
Volume	48
DOIs	https://doi.org/10.1016/j.jco.2018.05.004
State	Published - Oct 2018
Externally published	Yes

All Science Journal Classification (ASJC) codes

Algebra and Number Theory
Statistics and Probability
Numerical Analysis
General Mathematics
Control and Optimization
Applied Mathematics

Keywords

Random matrices
Random regular graphs
Rank
Singularity probability

Access to Document

10.1016/j.jco.2018.05.004

Cite this

@article{18cfebffa6a2439e9b16bd68043f2aa0,

title = "The rank of random regular digraphs of constant degree",

abstract = "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.",

keywords = "Random matrices, Random regular graphs, Rank, Singularity probability",

author = "Litvak, {Alexander E.} and Anna Lytova and Konstantin Tikhomirov and Nicole Tomczak-Jaegermann and Pierre Youssef",

note = "Publisher Copyright: {\textcopyright} 2018 Elsevier Inc.",

year = "2018",

month = oct,

doi = "10.1016/j.jco.2018.05.004",

language = "English (US)",

volume = "48",

pages = "103--110",

journal = "Journal of Complexity",

issn = "0885-064X",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - The rank of random regular digraphs of constant degree

AU - Litvak, Alexander E.

AU - Lytova, Anna

AU - Tikhomirov, Konstantin

AU - Tomczak-Jaegermann, Nicole

AU - Youssef, Pierre

PY - 2018/10

Y1 - 2018/10

N2 - 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.

AB - 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.

KW - Random matrices

KW - Random regular graphs

KW - Rank

KW - Singularity probability

UR - http://www.scopus.com/inward/record.url?scp=85047378427&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85047378427&partnerID=8YFLogxK

U2 - 10.1016/j.jco.2018.05.004

DO - 10.1016/j.jco.2018.05.004

M3 - Article

AN - SCOPUS:85047378427

SN - 0885-064X

VL - 48

SP - 103

EP - 110

JO - Journal of Complexity

JF - Journal of Complexity

ER -

The rank of random regular digraphs of constant degree

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this