TY - JOUR

T1 - Structure of eigenvectors of random regular digraphs

AU - Litvak, Alexander E.

AU - Lytova, Anna

AU - Tikhomirov, Konstantin

AU - Tomczak-Jaegermann, Nicole

AU - Youssef, Pierre

N1 - Funding Information:
The first two authors visited the Mathematical Sciences Research Institute (MSRI) in Berkeley, California. A significant part of this work was completed while the last three authors were in residence at the MSRI, supported by NSF grant DMS-1440140. The hospitality of MSRI and of the organizers of the program Geometric Functional Analysis and Applications is gratefully acknowledged. The research of the last author was partially supported by grant ANR-16-CE40-0024-01
Funding Information:
Received by the editors May 8, 2018, and, in revised form, October 16, 2018. 2010 Mathematics Subject Classification. Primary 60B20, 15B52, 46B06, 05C80; Secondary 46B09, 60C05. Key words and phrases. Delocalization of eigenvectors, Littlewood–Offord theory, random graphs, random matrices, regular graphs, sparse matrices, structure of the kernel. The first two authors visited the Mathematical Sciences Research Institute (MSRI) in Berkeley, California. A significant part of this work was completed while the last three authors were in residence at the MSRI, supported by NSF grant DMS-1440140. The hospitality of MSRI and of the organizers of the program Geometric Functional Analysis and Applications is gratefully acknowledged. The research of the last author was partially supported by grant ANR-16-CE40-0024-01.
Publisher Copyright:
© 2019 American Mathematical Society.

PY - 2019

Y1 - 2019

N2 - Let d and n be integers satisfying C ≤ d ≤ exp(Formula Presented) for some universal constants c, C > 0, and let z ∈ C. 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 Id, formed by removing a subset of rows. We show that with large probability the kernel consists of two nonintersecting 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,..., 1), possesses a weak delocalization property: Its level sets have cardinality less than Cn ln2 d/ ln n. For a large constant d, this provides 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 Cn 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.

AB - Let d and n be integers satisfying C ≤ d ≤ exp(Formula Presented) for some universal constants c, C > 0, and let z ∈ C. 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 Id, formed by removing a subset of rows. We show that with large probability the kernel consists of two nonintersecting 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,..., 1), possesses a weak delocalization property: Its level sets have cardinality less than Cn ln2 d/ ln n. For a large constant d, this provides 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 Cn 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.

KW - Delocalization of eigenvectors

KW - Littlewood-Offord theory

KW - Random graphs

KW - Random matrices

KW - Regular graphs

KW - Sparse matrices

KW - Structure of the kernel

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

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

U2 - 10.1090/tran/7742

DO - 10.1090/tran/7742

M3 - Article

AN - SCOPUS:85069676532

VL - 371

SP - 8097

EP - 8172

JO - Transactions of the American Mathematical Society

JF - Transactions of the American Mathematical Society

SN - 0002-9947

IS - 11

ER -