Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-23T19:27:55.884Z Has data issue: false hasContentIssue false
  • English
  • Français

EXPANSION CONSTANTS AND HYPERBOLIC EMBEDDINGS OF FINITE GRAPHS

Part of: Discrete mathematics in relation to computer science Graph theory Spectral theory and eigenvalue problems

Published online by Cambridge University Press:  19 November 2014

Tae Hattori  and
Atsushi Kasue
Tae Hattori
Affiliation:
Ishikawa National College of Technology, Tsubata Kahoku-gun, Ishikawa, 920-0329, Japan email [email protected]
Atsushi Kasue
Affiliation:
Department of Mathematics, Kanazawa University, Kanazawa, Ishikawa, 920-1192, Japan email [email protected]
Get access

Abstract

In this paper, we study a finite connected graph which admits a quasi-monomorphism to hyperbolic spaces and give a geometric bound for the Cheeger constants in terms of the volume, an upper bound of the degree, and the quasi-monomorphism.

MSC classification

Primary: 05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)
Secondary: 35P15: Estimation of eigenvalues, upper and lower bounds 68R10: Graph theory (including graph drawing)
Type
Research Article
Information
Mathematika , Volume 61 , Issue 1 , January 2015 , pp. 1 - 13
Copyright
Copyright © University College London 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Alexander, S. B. and Bishop, R. L., Gauss equation and injectivity radii for subspaces in spaces of curvature bounded above. Geom. Dedicata 117 2006, 65–84.CrossRefGoogle Scholar
Alon, N. and Milman, V. D., 𝜆1, isoperimetric inequalities for graphs and superconcentrators. J. Combin. Theory Ser. B 38 1985, 78–88.Google Scholar
Benjamini, I., Expanders are not hyperbolic. Israel J. Math. 108 1998, 33–36.Google Scholar
Benjamini, I. and Schramm, O., Harmonic functions on planar and almost planar graphs and manifolds, via circle packings. Invent. Math. 126 1996, 565–587.Google Scholar
Bonk, M. and Schramm, O., Embedding of Gromov hyperbolic spaces. Geom. Funct. Anal. 10 2000, 266–306.Google Scholar
Bühler, T. and Hein, M., Spectral clustering based on the graph p-Laplacian. Proc. 26th Int. Conf. Machine Learning, Omnipress (Montreal, 2009), 81–88.Google Scholar
Chandra, A. K., Raghavan, P., Ruzzo, W. L., Smolensky, R. and Tiwari, P., The electrical resistance of a graph captures its commute and cover times. Comput. Complexity 6 1996–1997, 312–340.Google Scholar
Chavel, I., Riemannian Geometry: A Modern Introduction, 2nd edn, Cambridge University Press (New York, 2006).CrossRefGoogle Scholar
Coulhon, T., Espace de Lipschitz et inegalités de Poincaré. J. Funct. Anal. 136 1996, 81–113.Google Scholar
Coulhon, T. and Koskela, P., Geometric interpretations of L p-Poincaré inequalities on graphs with polynominal volume growth. Milan J. Math. 72 2004, 209–248.Google Scholar
Daneshgar, A., Javadi, R. and Miclo, L., On nodal domains and higher-order Cheeger inequalities of finite reversible Markov processes. Stochastic Process. Appl. 122 2012, 1748–1776.Google Scholar
Dodziuk, J., Difference equations, isoperimetric inequality and transience of certain random walks. Trans. Amer. Math. Soc. 284 1984, 787–794.CrossRefGoogle Scholar
Duffin, R. J., The extremal length of a network. J. Math. Anal. Appl. 5 1962, 200–215.Google Scholar
Hattori, T. and Kasue, A., Functions with finite Dirichlet sum and compactifications of infinite graphs. In Probabilistic Approach to Geometry (Kyoto, 2008) (Advanced Studies in Pure Mathematics 57), Mathematical Society of Japan (Tokyo, 2010), 141–153.CrossRefGoogle Scholar
Hattori, T. and Kasue, A., Functions with finite Dirichlet sums of order p and quasi-monomorphisms of infinite graphs. Nagoya Math. J. 207 2012, 95–138.Google Scholar
Kasue, A., Convergence of finite metric graphs and energy forms. Rev. Mat. Iberoam. 26 2010, 367–448.Google Scholar
Lee, J. R., Gharan, S. O. and Trevisan, L., Multi-way spectral partitioning and higher-order Cheeger inequalitites. In Proceedings of the 44th Annual Symposium on Theory of Computing (STOC), ACM (New York, 2012), 1117–1130.Google Scholar
Mantuano, T., Discretization of compact Riemannian manifolds applied to the spectrum of Laplacian. Ann. Global Anal. Geom. 27 2005, 33–46.Google Scholar
Matoušec, J., On embedding expanders into ℓ p spaces. Israel J. Math. 102 1997, 189–197.CrossRefGoogle Scholar
Miclo, L., On eigenfunctions of Markov processes on trees. Probab. Theory Related Fields 142 2008, 561–594.Google Scholar
Nakamura, T. and Yamasaki, M., Generalized extremal length of an infinite network. Hiroshima Math. J. 6 1976, 95–111.CrossRefGoogle Scholar
Tanaka, M., Multi-way expansion constants and partitions of a graph. Preprint, 2011,arXiv:1112.3434.Google Scholar