Ramanujan coverings of graphs

Chris Hall, Doron Puder, William F. Sawin

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


Let G be a finite connected graph, and let ρ be the spectral radius of its universal cover. For example, if G is k-regular then ρ=2k−1. We show that for every r, there is an r-covering (a.k.a. an r-lift) of G where all the new eigenvalues are bounded from above by ρ. It follows that a bipartite Ramanujan graph has a Ramanujan r-covering for every r. This generalizes the r=2 case due to Marcus, Spielman and Srivastava [26]. Every r-covering of G corresponds to a labeling of the edges of G by elements of the symmetric group Sr. We generalize this notion to labeling the edges by elements of various groups and present a broader scenario where Ramanujan coverings are guaranteed to exist. In particular, this shows the existence of richer families of bipartite Ramanujan graphs than was known before. Inspired by [26], a crucial component of our proof is the existence of interlacing families of polynomials for complex reflection groups. The core argument of this component is taken from [27]. Another important ingredient of our proof is a new generalization of the matching polynomial of a graph. We define the r-th matching polynomial of G to be the average matching polynomial of all r-coverings of G. We show this polynomial shares many properties with the original matching polynomial. For example, it is real rooted with all its roots inside [−ρ,ρ].

שפה מקוריתאנגלית
עמודים (מ-עד)367-410
מספר עמודים44
כתב עתAdvances in Mathematics
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 7 ינו׳ 2018
פורסם באופן חיצוניכן

ASJC Scopus subject areas

  • ???subjectarea.asjc.2600.2600???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Ramanujan coverings of graphs'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי