Theo McKenzie - Precise Eigenvalue Location for Random Regular Graphs - IPAM at UCLA
Presenter
February 27, 2025
Abstract
Recorded 27 February 2025. Theo McKenzie of Stanford University presents "Precise Eigenvalue Location for Random Regular Graphs" at IPAM's Free Entropy Theory and Random Matrices Workshop.
Abstract: Random regular graphs are ubiquitous models of sparse, well-connected networks, with applications in theoretical computer science and statistical physics. However, the spectral statistics of a randomly selected graph are often challenging to analyze because of the strong dependence between entries. In this talk, I will show that despite this, we can achieve precise information about the spectrum, in that all eigenvalues fluctuate within optimally small intervals, and the distribution of edge eigenvalues is that of the largest eigenvalue of a matrix from the Gaussian Orthogonal Ensemble. This implies that most regular graphs are Ramanujan, meaning they have an optimally large spectral gap. We achieve this through a tight analysis of the Green’s function of the adjacency operator, specifically by analyzing changes in the Green's function after a random edge switch.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/free-entropy-theory-and-random-matrices/