On the local geometry of graphs in terms of their spectra

Huang, Brice; Rahman, Mustazee

Abstract

In this paper we consider the relation between the spectrum and the number of short cycles in large graphs. Suppose G1,G2,G3,... is a sequence of finite and connected graphs that share a common universal cover T and such that the proportion of eigenvalues of Gn that lie within the support of the spectrum of T tends to 1 in the large limit. This is a weak notion of being Ramanujan. We prove such a sequence of graphs is asymptotically locally tree-like. This is deduced by way of an analogous theorem proved for certain infinite sofic graphs and unimodular networks, which extends results for regular graphs and certain infinite Cayley graphs.

Citation

Huang, B., & Rahman, M. (2019). On the local geometry of graphs in terms of their spectra. European Journal of Combinatorics, 81, 378-393. https://doi.org/10.1016/j.ejc.2019.07.001

• Journal Article Type: Article
• Acceptance Date: Jul 3, 2019
• Online Publication Date: Jul 10, 2019
• Publication Date: 2019-10
• Deposit Date: Sep 25, 2019
• Publicly Available Date: Oct 6, 2021
• Journal: European Journal of Combinatorics
• Print ISSN: 0195-6698
• Electronic ISSN: 1095-9971
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 81
• Pages: 378-393
• DOI: https://doi.org/10.1016/j.ejc.2019.07.001
• Public URL: https://durham-repository.worktribe.com/output/1290459