### Abstract

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^{2} 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.

Original language | English (US) |
---|---|

Pages (from-to) | 8097-8172 |

Number of pages | 76 |

Journal | Transactions of the American Mathematical Society |

Volume | 371 |

Issue number | 11 |

DOIs | |

State | Published - 2019 |

### Keywords

- Delocalization of eigenvectors
- Littlewood-Offord theory
- Random graphs
- Random matrices
- Regular graphs
- Sparse matrices
- Structure of the kernel

### ASJC Scopus subject areas

- Mathematics(all)
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Structure of eigenvectors of random regular digraphs'. Together they form a unique fingerprint.

## Cite this

*Transactions of the American Mathematical Society*,

*371*(11), 8097-8172. https://doi.org/10.1090/tran/7742