Structure of eigenvectors of random regular digraphs

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 ln² 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.