On the local geometry of graphs in terms of their spectra. (English) Zbl 1420.05042
Summary: 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.
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
| 05C30 | Enumeration in graph theory |
| 05C38 | Paths and cycles |
References:
| [1] | Abért, M.; Glasner, Y.; Virág, B., The measurable Kesten theorem, Ann. Probab., 44, 3, 1601-1646 (2016) · Zbl 1339.05365 |
| [2] | Aldous, D.; Lyons, R., Processes on unimodular networks, Electron. J. Probab., 12, 54, 1454-1508 (2007) · Zbl 1131.60003 |
| [3] | Benjamini, I.; Schramm, O., Recurrence of distributional limits of finite planar graphs, Electron. J. Probab., 6, 23 (2001), 13pp · Zbl 1010.82021 |
| [4] | C. Bordenave, Spectrum of random graphs, Lecture notes, 2016, Available at http://www.math.univ-toulouse.fr/ bordenave/coursSRG.pdf; C. Bordenave, Spectrum of random graphs, Lecture notes, 2016, Available at http://www.math.univ-toulouse.fr/ bordenave/coursSRG.pdf |
| [5] | Bordenave, C., A new proof of friedman’s second eigenvlaue theorem and its extension to random lifts (2015), preprint arXiv:1502.04482 |
| [6] | Cioabă, S. M., Eigenvalues of graphs and a simple proof of a theorem of Greenberg, Linear Algebra Appl., 416, 776-782 (2006) · Zbl 1109.05068 |
| [7] | Elek, G., On the limit of large girth graph sequences, Combinatorica, 30, 5, 553-563 (2010) · Zbl 1231.05259 |
| [8] | Greenberg, Y., On the spectrum of graphs and their universal covering (1995), Hebrew University of Jerusalem, (in Hebrew) |
| [9] | Grigorchuk, R.; de la Harpe, P., On problems related to growth, entropy, and spectrum in group theory, J. Dyn. Control Syst., 3, 1, 51-89 (1997) · Zbl 0949.20033 |
| [10] | Grigorchuk, R.; Zuk, A., On the asymptotic spectrum of random walks on infinite families of graphs, (Picardello, M.; Woess, W., Random Walks and Discrete Potential Theory. Random Walks and Discrete Potential Theory, Symposia Mathematica, vol. XXXIX (1999), Cambridge Univ. Press), 188-204 · Zbl 0957.60044 |
| [11] | Hoory, S., A lower bound on the spectral radius of the universal cover of a graph, J. Combin. Theory, Ser B, 93, 1, 33-43 (2005) · Zbl 1063.05091 |
| [12] | Hoory, S.; Linial, N.; Wigderson, A., Expander graphs and their applications, Bull. Amer. Math. Soc., 43, 4, 439-562 (2006) · Zbl 1147.68608 |
| [13] | Kesten, H., Symmetric random walks on groups, Trans. Amer. Math. Soc., 92, 2, 336-354 (1959) · Zbl 0092.33503 |
| [14] | Leighton, F., Finite common coverings of graphs, J. Combin. Theory, Ser. B, 33, 231-238 (1982) · Zbl 0488.05033 |
| [15] | Lubetzky, E.; Peres, Y., Cutoff on all Ramanujan graphs, Geom. Funct. Anal., 26, 4, 1190-1216 (2016) · Zbl 1351.05208 |
| [16] | Lubotzky, A.; Phillips, R.; Sarnak, P., Ramanujan graphs, Combinatorica, 8, 3, 261-277 (1988) · Zbl 0661.05035 |
| [17] | Massey, W. S., Algebraic Topology: An Introduction (1977), Springer-Verlag · Zbl 0361.55002 |
| [18] | Rahman, M., A lower bound on the spectrum of unimodular networks (2016), preprint arXiv:1609.02209 |
| [19] | Serre, J.-P., Répartition asymptotique des valeurs propres de l’opérateur de Hecke \(T_p\), J. Amer. Math. Soc., 10, 1, 75-102 (1997) · Zbl 0871.11032 |
| [20] | Smirnova-Nagnibeda, T., Random walks on trees, spectral radii of groups, and Ramanujan graphs, (Kaimanovich, V., Random Walks and Geometry (2004), de Gruyter), 487-500 · Zbl 1058.60033 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
