On the Local Geometry of Graphs in Terms of Their Spectra
| Autor: | Huang, Brice, Rahman, Mustazee |
|---|---|
| Rok vydání: | 2018 |
| Předmět: | |
| Zdroj: | European J. Combin. 81 (2019) 378-393 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1016/j.ejc.2019.07.001 |
| Popis: | In this paper we consider the relation between the spectrum and the number of short cycles in large graphs. Suppose $G_1, G_2, G_3, \ldots$ is a sequence of finite and connected graphs that share a common universal cover $T$ and such that the proportion of eigenvalues of $G_n$ that lie within the support of the spectrum of $T$ tends to 1 in the large $n$ 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. Comment: 21 pages, 3 figures; simplified main proof |
| Databáze: | arXiv |
| Externí odkaz: |
|