YMSC Probability Seminar | Extreme eigenvalues of random regular graphs

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\sqrt{d-1}$. Our proof shows that the fluctuations of these extreme eigenvalues are bounded by $N^{−2/3+\varepsilon}$, where $\varepsilon>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.

Speaker

I am currently an Assistant Professor of Statistics and Data Science at University of Pennsylvania. Before that, I was a postdoc at Courant Institute of Mathematical Sciences of New York University, and a Junior Fellow at the Simons Society of Fellows from 2020 to 2022. And I was a member in the Institute for Advanced Study (IAS) for the 2019-2020 academic year. I got my Ph.D. degree in mathematics from Harvard University under the supervision of Professor Horng-Tzer Yau.

黄骄阳，2024斯隆研究奖（Sloan Research Fellowships）获奖者。2014年在麻省理工学院数学系获得学士学位，2019年在哈佛大学数学系获得博士学位，2019-2022年在普林斯顿高等研究院和纽约大学做博士后。现为宾夕法尼亚大学统计和数据科学系助理教授。研究方向为随机矩阵理论、随机图、交互粒子系统、深度神经网络优化、后验采样和大规模逆问题的不确定性量化。