A transfer principle and applications to eigenvalue estimates for graphs (Q2412934)

Summary: 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 \(\lambda_k^{\mathrm{nr}}\) of the normalized Laplacian of a graph \(G\) of (geometric) genus \(g\) on \(n\) vertices satisfies \[ \lambda_k^{\mathrm{nr}}(G)\leq C\frac{d_{\mathrm{max}}(g+k)}n, \] where \(d_{\mathrm{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 \textit{J. Kelner} et al. [Geom. Funct. Anal. 21, No. 5, 1117--1143 (2011; Zbl 1229.05094)] 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 \textit{G. L. Miller} et al. [SIAM J. Sci. Comput. 19, No. 2, 364--386 (1998; Zbl 0914.65123)] and \textit{D. Spielman} and \textit{S. H. Teng} [Linear Algebra Appl. 421, No. 2--3, 284--305 (2007; Zbl 1122.05062)] to arbitrary meshes.