paper

-Ramanujan Graphs

arXiv:1904.03500

Abstract

Let be an infinite graph of bounded degree; e.g., the Cayley graph of a free product of finite groups. If is a finite graph covered by , it is said to be -Ramanujan if its second-largest eigenvalue is at most the spectral radius of , and more generally -quasi--Ramanujan if is at most . In case 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 -quasi--Ramanujan graphs for a variety of infinite . In particular, need not be a tree; our analysis is applicable whenever is what we call an additive product graph. This additive product is a new construction of an infinite graph from finite 'atom' graphs over a common vertex set. It generalizes the notion of the free product graph when the atoms are vertex-transitive, and it generalizes the notion of the universal covering tree when the atoms are single-edge graphs. Key to our analysis is a new graph polynomial that we call the additive characteristic polynomial. It generalizes the well known matching polynomial in case the atoms are the single edges of , and it generalizes the -characteristic polynomial introduced in [Ravichandran'16, Leake-Ravichandran'18]. We show that is real-rooted, and all of its roots have magnitude at most . This last fact is proven by generalizing Godsil's notion of treelike walks on a graph to a notion of freelike walks on a collection of atoms .

arXiv comment36 pages

References in corpus (5)