Combinatorics Seminar 2019

Speaker: Zilin Jiang (姜子麟), Massachusetts Institute of Technology

Date: Fri, Jul 05, 2019

Time: 15:00 - 15:50

Venue: Room 703

Title: Spectral radius: local and global


Ramanujan graphs are defined in terms of the eigenvalues of their adjacency matrices. Following Lubotzky, Phillips and Sarnak, we say that a $d$-regular bipartite graph is Ramanujan if its second largest eigenvalue is less than $2\sqrt{d-1}$. One reason for taking $2\sqrt{d-1}$ in the definition of Ramanujan graphs is the well-known result of Alon and Boppana, which states that for every $d$-regular graph $G$ containing two edges at distance $\ge2\sqrt{d-1}$, the second largest eigenvalue of $G$ is at least $2(1-1/r)\sqrt{d-1}+1/r$. All the existing proofs of the Alon--Boppana bound primarily relied on estimating the largest eigenvalue of a ball around a vertex in a graph $G$ -- a ball of radius $r$ around $v$ is the induced subgraph of $G$ on the vertices within distance $r$ from $v$. In this talk, we shall give a lower bound on the largest eigenvalue of a ball of a given radius in terms of the average degree of the graph. As an application, we give a natural generalization of the Alon--Boppana bound to graphs that may not be regular, improving a result of Hoory.