Speaker: Jiaoyang Huang, University of Pennsylvania

Time: 16:00-17:00 p.m., Jun 11, 2024, GMT+8

Venue: Room 77201, Jingchunyuan 78, BICMR, PKU

Abstract: 

Extremal eigenvalues of graphs are of particular interest in theoretical computer science and combinatorics. Specifically, the spectral gap—the gap between the first and second largest eigenvalues—measures the expanding property of the graph. In this talk, I will focus on random d-regular graphs, for which the largest eigenvalue is d. 
I'll first explain some conjectures on the extremal eigenvalue distributions of adjacency matrices of random d-regular graphs. In the second part of the talk, I will discuss a new proof of Alon's second eigenvalue conjecture, which asserts that with high probability, the second eigenvalue of a random d-regular graph concentrates around 2(d-1). Our proof shows that the fluctuations of these extreme eigenvalues are bounded by N, where e>0 can be arbitrarily small. This gives the same order of fluctuation as the eigenvalues of matrices from the Gaussian Orthogonal Ensemble. This work is based on joint research with Theo McKenzie and Horng-Tzer Yau.

Source: Beijing International Center for Mathematical Research, PKU