Hostname: page-component-745bb68f8f-v2bm5 Total loading time: 0 Render date: 2025-02-06T22:46:36.190Z Has data issue: false hasContentIssue false
  • English
  • Français

Eigenvalue Ratios of Non-Negatively Curved Graphs

Part of: Global differential geometry Graph theory

Published online by Cambridge University Press:  23 May 2018

SHIPING LIU  and
NORBERT PEYERIMHOFF
SHIPING LIU
Affiliation:
Wu Wen-Tsun Key Laboratory of Mathematics, Chinese Academy of Sciences, School of Mathematical Sciences, University of Science and Technology of China, Hefei 230026, Anhui Province, China (e-mail: spliu@ustc.edu.cn)
NORBERT PEYERIMHOFF
Affiliation:
Department of Mathematical Sciences, Durham University, DH1 3LE Durham, UK (e-mail: norbert.peyerimhoff@durham.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We derive an optimal eigenvalue ratio estimate for finite weighted graphs satisfying the curvature-dimension inequality CD(0, ∞). This estimate is independent of the size of the graph and provides a general method to obtain higher-order spectral estimates. The operation of taking Cartesian products is shown to be an efficient way for constructing new weighted graphs satisfying CD(0, ∞). We also discuss a higher-order Cheeger constant-ratio estimate and related topics about expanders.

MSC classification

Primary: 05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)
Secondary: 53C23: Global geometric and topological methods (à la Gromov); differential geometric analysis on metric spaces
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Issue 5 , September 2018 , pp. 829 - 850
Copyright
Copyright © Cambridge University Press 2018 

References

[1] Alon, N. and Milman, V. (1985) λ1, isoperimetric inequalities for graphs, and superconcentrators. J. Combin. Theory Ser. B 38 73–88.Google Scholar
[2] Alon, N. and Roichman, Y. (1994) Random Cayley graphs and expanders. Random Struct. Alg. 5 271–284.Google Scholar
[3] Bakry, D. (2006) Functional inequalities for Markov semigroups. In Probability Measures on Groups: Recent Directions and Trends, Tata Institute of Fundamental Research, pp. 91–147.Google Scholar
[4] Bakry, D. and Émery, M. (1985) Diffusions hypercontractives (in French), In Séminaire de Probabilités XIX, 1983/84, Vol. 1123 of Lecture Notes in Mathematics, (Azéma, J. and Yor, M., eds), Springer, pp. 177–206.Google Scholar
[5] Bauer, F., Horn, P., Lin, Y., Lippner, G., Mangoubi, D. and Yau, S.-T. (2015) Li–Yau inequality on graphs. J. Differ. Geom. 99 359–405.Google Scholar
[6] Buser, P. (1982) A note on the isoperimetric constant. Ann. Sci. École Norm. Sup. (4) 15 213–230.Google Scholar
[7] Chen, G., Davis, G., Hall, F., Li, Z., Patel, K. and Stewart, M. (2004) An interlacing result on normalized Laplacians. SIAM J. Discrete Math. 18 353–361.Google Scholar
[8] Cheng, S.-Y. (1975) Eigenvalue comparison theorems and its geometric applications. Math. Z. 143 289–297.Google Scholar
[9] Chung, F. R. K. (1989) Diameters and eigenvalues. J. Amer. Math. Soc. 2 187–196.Google Scholar
[10] Chung, F. R. K. (1997) Spectral Graph Theory, Vol. 92 of CBMS Regional Conference Series in Mathematics, AMS.Google Scholar
[11] Chung, F. R. K., Grigor'yan, A. and Yau, S.-T. (1997) Eigenvalues and diameters for manifolds and graphs. In Tsing Hua Lectures on Geometry and Analysis (Hsinchu, 1990-1991), International Press, pp. 79–105.Google Scholar
[12] Chung, F. R. K., Lin, Y. and Yau, S.-T. (2014) Harnack inequalities for graphs with non-negative Ricci curvature. J. Math. Anal. Appl. 415 25–32.Google Scholar
[13] Chung, F. R. K. and Yau, S.-T. (1996) Logarithmic Harnack inequalities. Math. Res. Lett. 3 793–812.Google Scholar
[14] Elworthy, K. D. (1991) Manifolds and graphs with mostly positive curvatures. In Stochastic analysis and applications (Lisbon, 1989), Birkhäuser Boston, Boston, MA, Progr. Probab. 26 96–110.Google Scholar
[15] Friedman, J., Murty, R. and Tillich, J.-P. (2006) Spectral estimates for Abelian Cayley graphs. J. Combin. Theory Ser. B 96 111–121.Google Scholar
[16] Funano, K. (2013) Eigenvalues of Laplacian and multi-way isoperimetric constants on weighted Riemannian manifolds. arXiv:1307.3919v1Google Scholar
[17] van den Heuvel, J. (1995) Hamilton cycles and eigenvalues of graphs. Linear Algebra Appl. 226/228 723–730.Google Scholar
[18] Houdré, C. and Tetali, P. (2001) Concentration of measure for products of Markov kernels and graph products via functional inequalities. Combin. Probab. Comput. 10 1–28.Google Scholar
[19] Jost, J. and Liu, S. (2014) Ollivier's Ricci curvature, local clustering and curvature-dimension inequalities on graphs. Discrete Comput. Geom. 51 300–322.Google Scholar
[20] Klartag, B., Kozma, G., Ralli, P. and Tetali, P. (2016) Discrete curvature and abelian groups. Canad. J. Math. 68 655–674.Google Scholar
[21] Kwok, T.-C., Lau, L.-C., Lee, Y.-T., Oveis Gharan, S. and Trevisan, L. (2013) Improved Cheeger's inequality: Analysis of spectral partitioning algorithms through higher order spectral gap. In STOC '13: Proceedings of the 2013 ACM Symposium on Theory of Computing, ACM, pp. 11–20.Google Scholar
[22] Ledoux, M. (2004) Spectral gap, logarithmic Sobolev constant, and geometric bounds. In Surveys in Differential Geometry, Vol. IX, International Press, pp. 219–240.Google Scholar
[23] Lee, J. R., Oveis Gharan, S. and Trevisan, L. (2012) Multi-way spectral partitioning and higher-order Cheeger inequalities, In STOC '12: Proceedings of the 2012 ACM Symposium on Theory of Computing, ACM, pp. 1117–1130.Google Scholar
[24] Lin, Y. and Yau, S.-T. (2010) Ricci curvature and eigenvalue estimate on locally finite graphs. Math. Res. Lett. 17 343–356.Google Scholar
[25] Liu, S. (2014) An optimal dimension-free upper bound for eigenvalue ratios. arXiv:1405.2213Google Scholar
[26] Liu, S. (2015) Multi-way dual Cheeger constants and spectral bounds of graphs. Adv. Math. 268 306–338.Google Scholar
[27] Liu, S. and Peyerimhoff, N. (2014) Eigenvaue ratios of nonnegatively curved graphs. arXiv:1406.6617Google Scholar
[28] Miclo, L. (1999) Relations entre isopérimétrie et trou spectral pour les chaî nes de Markov finies. Probab. Theory Rel. Fields 114 431–485.Google Scholar
[29] Miclo, L. (2008) On eigenfunctions of Markov processes on trees. Probab. Theory Rel. Fields 142 561–594.Google Scholar
[30] Mimura, M. (2016) Multi-way expanders and imprimitive group actions on graphs. Int. Math. Res. Not. 2016 2522–2543.Google Scholar
[31] Mohar, B. (1991) Eigenvalues, diameter, and mean distance in graphs. Graphs Combin. 7 53–64.Google Scholar
[32] Schmuckenschläger, M. (1999) Curvature of nonlocal Markov generators. In Convex Geometric Analysis, Vol. 34 of Mathematical Sciences Research Institute Publications, Cambridge University Press, pp. 189–197.Google Scholar
[33] Tanaka, M. (2013) Multi-way expansion constants and partitions of a graph. arXiv:1112.3434Google Scholar