X-Ramanujan Graphs
share
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 second-largest eigenvalue λ_2(G) is at most the spectral radius ρ(X) of X, and more generally k-quasi-X-Ramanujan if λ_k(G) is at most ρ(X). 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 AddProd(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 [Ravichandran'16, Leake-Ravichandran'18]. We show that α(A_1, ..., A_c;x) is real-rooted, and all of its roots have magnitude at most ρ(AddProd(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.
READ FULL TEXT