A transfer principle and applications to eigenvalue estimates for graphs

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 kth eigenvalue^nr_k of the normalized Laplacian of a graph G of (geometric) genus g on n vertices satisfiesⁿ_k .G/ C^dmax.g C^k/ ; n where d_max 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.

This work was started during a stay of the first named author at Laboratoire J. A. Dieudonné at Université de Nice Sophia-Antipolis, and pursued during another visit at INRIA Sophia-Antipolis. He thanks both these institutions, specially Philippe Maisonobe and Jean-Daniel Boissonnat, for their support. This research has been partially supported by the European Research Council under Advanced Grant 339025 GUDHI (Geometry Understanding in High Dimensions).