Invertibility of adjacency matrices for random $d$-regular graphs

Jiaoyang Huang

Published 2018-07-16Version 1

Very recently, M\'esz\'ados [22], and Nguyen and Wood [24] proved that the adjacency matrices of random $d$-regular graphs obtained from the union of $d$ random perfect matchings are nonsingular with high probability. This answers an open problem by Frieze [12] and Vu [29,30] for random $d$-regular graphs with even number of vertices. In this paper, we study random $d$-regular graphs obtained from the configuration model, and prove that with high probability their adjacency matrices are nonsingular. The proof combines a local central limit theorem and a large deviation estimate, which generalizes the argument developed for studying random $d$-regular directed graphs in [13].