Title: Invertibility of adjacency matrices for random d-regular graphs
Speaker: Jiaoyang Huang (Harvard University)
Abstract: The singularity problem of random matrices asks the probability that a given discrete random matrix is singular. The first such result was obtained by Komlós in 1967. He showed a Bernoulli random matrix is singular with probability $o(1)$. This question can be reformulated for the adjacency matrices of random graphs, either directed or undirected. The most challenging case is when the random graph is sparse. In this talk, I will prove that for random directed and undirected $d$-regular graphs, their adjacency matrices are invertible with high probability for all $d \geq 3$. The idea is to study the adjacency matrices over a finite field, and the proof combines a local central limit theorem and a large deviation estimate.
