The rank of random regular digraphs of constant degree

DOI10.1016/J.JCO.2018.05.004MaRDI QIDQ722766zbMATH OpenOpenAlexWikidataFDO

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

Publication date 27 July 2018

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1801.05577

zbMATH Keywords

random matricesrandom regular graphsranksingularity probability

Mathematics Subject Classification ID

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

Abstract: Let $d$ be a fixed large integer. For any $n$ larger than $d$, let $A_n$ be the adjacency matrix of the random directed $d$-regular graph on $n$ vertices, with the uniform distribution. We show that $A_n$ has rank at least $n-1$ with probability going to one as $n$ goes to infinity. The proof combines the method of simple switchings and a recent result of the authors on delocalization of eigenvectors of $A_n$.

Recommendations

• The rank of random graphs
• On the singularity of adjacency matrices for random regular digraphs
• The rank of diluted random graphs
• The circular law for random regular digraphs
• Structure of eigenvectors of random regular digraphs

Cites work

• Adjacency matrices of random digraphs: singularity and anti-concentration
• Anti-concentration property for random digraphs and invertibility of their adjacency matrices
• Around the circular law
• scientific article; zbMATH DE number 5296054 (Why is no real title available?)
• scientific article; zbMATH DE number 3773632 (Why is no real title available?)
• scientific article; zbMATH DE number 6803211 (Why is no real title available?)
• scientific article; zbMATH DE number 6797624 (Why is no real title available?)
• scientific article; zbMATH DE number 3245540 (Why is no real title available?)
• Inverse Littlewood-Offord problems and the singularity of random symmetric matrices
• Invertibility of sparse non-Hermitian matrices
• Invertibility of symmetric random matrices
• On the Probability That a Random ± 1-Matrix Is Singular
• On the singularity of adjacency matrices for random regular digraphs
• On the singularity of random combinatorial matrices
• On the singularity probability of discrete random matrices
• On the singularity probability of random Bernoulli matrices
• Random symmetric matrices are almost surely nonsingular.
• The circular law for random regular digraphs with random edge weights
• The rank of diluted random graphs
• The rank of random graphs
• The rank of random regular digraphs of constant degree

Cited in

(18)

• The smallest singular value of a shifted d-regular random square matrix
• Sharp transition of the invertibility of the adjacency matrices of sparse random graphs
• Recent progress in combinatorial random matrix theory
• Invertibility of adjacency matrices for random d-regular graphs
• Singularity of sparse Bernoulli matrices
• Edge rigidity and universality of random regular graphs of intermediate degree
• The circular law for sparse non-Hermitian matrices
• PageRank regular digraphs with prime out-degrees
• On asymptotic properties of the rank of a special random adjacency matrix
• Adjacency matrices of random digraphs: singularity and anti-concentration
• The rank of random graphs
• On the singularity of adjacency matrices for random regular digraphs
• Anti-concentration property for random digraphs and invertibility of their adjacency matrices
• The rank of diluted random graphs
• Structure of eigenvectors of random regular digraphs
• The rank of diluted random graphs
• Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs
• The rank of random regular digraphs of constant degree

This page was built for publication: The rank of random regular digraphs of constant degree

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