Algebraic Graph Theory-Theo McKenzie

Monday, March 3, 2025 11:30 am - 12:30 pm EST (GMT -05:00)

Title: Precise Eigenvalue Location for Random Regular Graphs

Speaker: Theo McKenzie
Affiliation: Stanford University
Location: Please contact Sabrina Lato for Zoom link.

Abstract:The spectral theory of regular graphs has broad applications in theoretical computer science, statistical physics, and other areas of mathematics. Graphs with optimally large spectral gap are known as Ramanujan graphs. Previous constructions of Ramanujan graphs are based on number theory and have specific constraints on the degree and number of vertices. In this talk, we show that, in fact, most regular graphs are Ramanujan; specifically, a randomly selected regular graph has a probability of 69% of being Ramanujan. We establish this through a rigorous analysis of the Green’s function of the adjacency operator, focusing on its behavior under random edge switches.