A transfer principle and applications to eigenvalue estimates for graphs

Omid Amini 1 David Cohen-Steiner 2
2 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : In this paper, we prove a variant of the Burger-Brooks transfer principle which, combined with recent eigenvalue bounds for surfaces, allows to obtain upper bounds on the eigenvalues of graphs as a function of their genus. More precisely, we show the existence of a universal constants C such that the k-th eigenvalue λ_k of the normalized Laplacian of a graph G of (geometric) genus g on n vertices satisfies λ_k ≤Cdmax(g+k) / kn where dmax denotes the maximum valence of vertices of the graph. This result is tight up to a change in the value of the constant C. We also use our transfer theorem to relate eigenvalues of the Laplacian on a metric graph to the eigenvalues of its simple graph models, and discuss an application to the mesh partitioning problem.
Type de document :
Rapport
[Research Report] RR-8673, INRIA. 2015
Liste complète des métadonnées


https://hal.inria.fr/hal-01109634
Contributeur : David Cohen-Steiner <>
Soumis le : lundi 26 janvier 2015 - 16:28:55
Dernière modification le : samedi 18 février 2017 - 01:14:41
Document(s) archivé(s) le : lundi 27 avril 2015 - 10:46:30

Fichier

RR-8673.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01109634, version 1

Collections

Citation

Omid Amini, David Cohen-Steiner. A transfer principle and applications to eigenvalue estimates for graphs. [Research Report] RR-8673, INRIA. 2015. <hal-01109634>

Partager

Métriques

Consultations de
la notice

257

Téléchargements du document

310