X-Ramanujan graphs

Let X be an infinite graph of bounded degree; e.g., the Cayley graph of a free product of finite groups. If G is a finite graph covered by X, it is said to be X-Ramanujan if its secondlargest eigenvalue λ 2 (G) is at most the spectral radius ρ(X) of X, and more generally

In case X is the infinite ∆-regular tree, this reduces to the well known notion of a finite ∆-regular graph being Ramanujan. Inspired by the Interlacing Polynomials method of Marcus, Spielman, and Srivastava, we show the existence of infinitely many k-quasi-X-Ramanujan graphs for a variety of infinite X. In particular, X need not be a tree; our analysis is applicable whenever X is what we call an additive product graph. This additive product is a new construction of an infinite graph A 1 + • • • + A c from finite "atom" graphs A 1 , . . . , A c over a common vertex set. It generalizes the notion of the free product graph A 1 * • • • * A c when the atoms A j are vertex-transitive, and it generalizes the notion of the universal covering tree when the atoms A j are single-edge graphs. Key to our analysis is a new graph polynomial α(A 1 , . . . , A c ; x) that we call the additive characteristic polynomial. It generalizes the well known matching polynomial µ(G; x) in case the atoms A j are the single edges of G, and it generalizes the r-characteristic polynomial introduced in [Rav16,LR18]. We show that α(A 1 , . . . , A c ; x) is real-rooted, and all of its roots have magnitude at most ρ(A 1 + • • • + A c ). This last fact is proven by generalizing Godsil's notion of treelike walks on a graph G to a notion of freelike walks on a collection of atoms A 1 , . . . , A c .

A talk about this work may be viewed on YouTube.