A transfer principle and applications to eigenvalue estimates for graphs

Omid Amini 1 David Cohen-Steiner 2, 3
2 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
3 DATASHAPE - Understanding the Shape of Data
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 :
Article dans une revue
Commentarii Mathematici Helvetici, European Mathematical Society, 2018
Liste complète des métadonnées

Littérature citée [37 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01109634
Contributeur : David Cohen-Steiner <>
Soumis le : lundi 26 janvier 2015 - 16:28:55
Dernière modification le : jeudi 7 février 2019 - 17:15:45
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

Citation

Omid Amini, David Cohen-Steiner. A transfer principle and applications to eigenvalue estimates for graphs. Commentarii Mathematici Helvetici, European Mathematical Society, 2018. 〈hal-01109634〉

Partager

Métriques

Consultations de la notice

375

Téléchargements de fichiers

358