Structure of eigenvectors of random regular digraphs

DOI10.1090/TRAN/7742MaRDI QIDQ5380492zbMATH OpenOpenAlexWikidataFDO

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

Publication date 5 June 2019

Published in Transactions of the American Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

delocalization of eigenvectorsLittlewood-Offord theoryrandom graphsrandom matricesregular graphssparse matricesstructure of kernel

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Random matrices (algebraic aspects) (15B52) Asymptotic theory of Banach spaces (46B06) Probabilistic methods in Banach space theory (46B09) Random matrices (probabilistic aspects) (60B20) Combinatorial probability (60C05)

Abstract: Let $d$ and $n$ be integers satisfying $Cleqdleqexp(csqrtlnn)$ for some universal constants $c,C>0$, and let $zinmathbbC$. Denote by $M$ the adjacency matrix of a random $d$-regular directed graph on $n$ vertices. In this paper, we study the structure of the kernel of submatrices of $M-z,mId$, formed by removing a subset of rows. We show that with large probability the kernel consists of two non-intersecting types of vectors, which we call very steep and gradual with many levels. As a corollary, we show, in particular, that every eigenvector of $M$, except for constant multiples of $(1,1,dots,1)$, possesses a weak delocalization property: its level sets have cardinality less than $Cnl{n}^{2}d/lnn$. For a large constant $d$ this provides a principally new structural information on eigenvectors, implying that the number of their level sets grows to infinity with $n$. As a key technical ingredient of our proofs we introduce a decomposition of $mathbb{C}^n$ into vectors of different degrees of `structuredness', which is an alternative to the decomposition based on the least common denominator in the regime when the underlying random matrix is very sparse.

Recommendations

• Sparse regular random graphs: spectral density and eigenvectors
• Sparse random graphs: eigenvalues and eigenvectors
• The rank of random regular digraphs of constant degree
• Many nodal domains in random regular graphs
• On the almost eigenvectors of random regular graphs

Cites work

• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• A proof of Alon’s second eigenvalue conjecture and related problems
• A Sharper Form of the Doeblin-Lévy-Kolmogorov-Rogozin Inequality for Concentration Functions.
• 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
• Asymptotic enumeration of sparse 0--1 matrices with irregular row and column sums
• Bounds for the Multidimensional Lévy Concentration Function
• Circular law for the sum of random permutation matrices
• Convergence of the density of states and delocalization of eigenvectors on random regular graphs
• Coverings of random ellipsoids, and invertibility of matrices with i.i.d. heavy-tailed entries
• Delocalization of eigenvectors of random matrices with independent entries
• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
• Discrepancy properties for random regular digraphs
• Eigenvector statistics of sparse random matrices
• Estimates for the concentration function of combinatorial number theory and probability
• Expander graphs and their applications
• Expansion of random graphs: new proofs, new results
• Functional limit theorems for random regular graphs
• scientific article; zbMATH DE number 3878944 (Why is no real title available?)
• scientific article; zbMATH DE number 3901742 (Why is no real title available?)
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• Invertibility of random matrices: norm of the inverse
• Invertibility of sparse non-Hermitian matrices
• Large deviations of empirical neighborhood distribution in sparse random graphs
• Local semicircle law for random regular graphs
• No-gaps delocalization for general random matrices
• Non-asymptotic theory of random matrices: extreme singular values
• On the concentration function of a sum of independent random variables
• On the distribution of additive arithmetic functions
• On the Kolmogorov-Rogozin inequality for the concentration function
• On the Probability That a Random ± 1-Matrix Is Singular
• On the singularity of adjacency matrices for random regular digraphs
• On the singularity probability of random Bernoulli matrices
• Optimal Construction of Edge-Disjoint Paths in Random Graphs
• Probability Inequalities for Sums of Bounded Random Variables
• Quantum ergodicity on large regular graphs
• RANDOM MATRICES: THE CIRCULAR LAW
• Size biased couplings and the spectral gap for random regular graphs
• Smallest singular value of a random rectangular matrix
• Smallest singular value of random matrices and geometry of random polytopes
• Smallest singular value of sparse random matrices
• Sparse random graphs: eigenvalues and eigenvectors
• Sparse regular random graphs: spectral density and eigenvectors
• Spectral analysis of large dimensional random matrices
• Symmetric Random Walks on Groups
• The circular law for random matrices
• The expected eigenvalue distribution of a large regular graph
• The Littlewood-Offord problem and invertibility of random matrices
• The rank of random regular digraphs of constant degree
• The smallest singular value of a shifted d-regular random square matrix

Cited in

(15)

• Spectral gap of sparse bistochastic matrices with exchangeable rows
• Eigenvectors and controllability of non-Hermitian random matrices and directed graphs
• Invertibility of adjacency matrices for random d-regular graphs
• Singularity of sparse Bernoulli matrices
• On delocalization of eigenvectors of random non-Hermitian matrices
• The sparse circular law under minimal assumptions
• Circular law for sparse random regular digraphs
• On non-localization of eigenvectors of high girth graphs
• Singularity of the \(k\)-core of a random graph
• Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs
• Past, current and future trends and challenges in non-deterministic fracture mechanics: a review
• Quantitative invertibility of non-Hermitian random matrices
• On the second eigenvalue of random bipartite biregular graphs
• A note on the singularity probability of random directed \(d\)-regular graphs
• The rank of random regular digraphs of constant degree

This page was built for publication: Structure of eigenvectors of random regular digraphs

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