Ï㽶ÊÓƵ

Title: Extreme eigenvalues of random d -regular graphs.

Abstract: Extremal eigenvalues of graphs are of particular interest in theoretical computer science and combinatorics. In particular, 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. I’ll first explain some conjectures on the extremal eigenvalue distributions of adjacency matrices of random d-regular graphs; some have been solved, some are still widely open. In the second part of the talk, I will give a new proof of Alon’s second eigenvalue conjecture that with high probability, the second eigenvalue of a random d-regular graph is bounded by 2√ d − 1+o(1), where we can show that the error term is polynomially small in the size of the graph. This is based on a joint work with Horng-Tzer Yau.