Brice Huang
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 |
Files
Accepted Journal Article
(433 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by-nc-nd/4.0/
Copyright Statement
© 2021 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
You might also like
On inhomogeneous polynuclear growth
(2022)
Journal Article
Multi-time distribution in discrete polynuclear growth
(2021)
Journal Article
TASEP fluctuations with soft-shock initial data
(2020)
Journal Article
Geometry of Permutation Limits
(2019)
Journal Article
Suboptimality of local algorithms for a class of max-cut problems
(2019)
Journal Article