# X-Ramanujan graphs: ex uno plures

 Computer Science/Discrete Mathematics Seminar Topic: X-Ramanujan graphs: ex uno plures Speaker: Ryan O'Donnell Affiliation: Carnegie Mellon University Date: Monday, October 29 Time/Room: 3:30pm - 4:30pm/Simonyi Hall 101 Video Link: https://video.ias.edu/csdm/2018/1029-RyanODonnell

Let X be the infinite graph partially pictured below, the "free product graph" C_4 * C_4 * C_4. Let FinQuo(X) be the set of all finite graphs G that covered by X (i.e., that 'locally resemble' X; i.e., that consist of C_4's joined 3-to-a-vertex). A known Alon-Boppana-type theorem implies that every G in FinQuo(X) has second eigenvalue at least sqrt(5sqrt(5)+11) - o(1), where that magic number is the spectral radius of X. We may then ask the "Ramanujan question": are there infinitely many G in FinQuo(X) with second eigenvalue at most sqrt(5sqrt(5)+11)? When X is the infinite d-regular tree, this is the well known Ramanujan graph problem resolved by Marcus, Spielman, and Srivastava [MSS].

We show a positive answer to the problem for a wide variety of infinite X (not necessarily trees). Techniques involve a new infinite graph product, a new graph polynomial (generalizing the matching polynomial), "freelike walks", Heaps of Pieces, and of course [MSS]'s Interlacing Polynomials Method.

Joint work with Sidhanth Mohanty (CMU/Berkeley).