HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

A transfer principle and applications to eigenvalue estimates for graphs

Omid Amini 1 David Cohen-Steiner 2
2 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. Our result is tight up to a change in the value of the constant C, and improves recent results of Kelner, Lee, Price and Teng on bounded genus graphs. To show that the transfer theorem might be of independent interest, we 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, extending results of Miller-Teng-Thurston- Vavasis and Spielman-Teng to arbitrary meshes.
Document type :
Journal articles
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download

Contributor : David Cohen-Steiner Connect in order to contact the contributor
Submitted on : Friday, March 29, 2019 - 3:53:08 PM
Last modification on : Thursday, March 17, 2022 - 10:08:19 AM
Long-term archiving on: : Sunday, June 30, 2019 - 3:42:15 PM


Files produced by the author(s)


  • HAL Id : hal-01109634, version 2


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



Record views


Files downloads