Spectral preorder and perturbations of discrete weighted graphs
- PDF / 1,164,008 Bytes
- 49 Pages / 439.37 x 666.142 pts Page_size
- 22 Downloads / 230 Views
Mathematische Annalen
Spectral preorder and perturbations of discrete weighted graphs John Stewart Fabila-Carrasco1,2 · Fernando Lledó1,2
· Olaf Post3
Received: 20 May 2020 / Revised: 9 September 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract In this article, we introduce a geometric and a spectral preorder relation on the class of weighted graphs with a magnetic potential. The first preorder is expressed through the existence of a graph homomorphism respecting the magnetic potential and fulfilling certain inequalities for the weights. The second preorder refers to the spectrum of the associated Laplacian of the magnetic weighted graph. These relations give a quantitative control of the effect of elementary and composite perturbations of the graph (deleting edges, contracting vertices, etc.) on the spectrum of the corresponding Laplacians, generalising interlacing of eigenvalues. We give several applications of the preorders: we show how to classify graphs according to these preorders and we prove the stability of certain eigenvalues in graphs with a maximal d-clique. Moreover, we show the monotonicity of the eigenvalues when passing to spanning subgraphs and the monotonicity of magnetic Cheeger constants with respect to the geometric preorder. Finally, we prove a refined procedure to detect spectral gaps in the spectrum of an infinite covering graph. Keywords Preorder on graphs · Spectral graph theory · Discrete magnetic Laplacian · Cheeger constant · Frustration index · Covering graphs Mathematics Subject Classification 05C50 · 47B39 · 47A10 · 05C76 To Hagen Neidhardt in memoriam.
Communicated by Y. Giga. JSFC and FLl were supported by Spanish Ministry of Economy and Competitiveness through project DGI MTM2017-84098-P, from the Severo Ochoa Programme for Centres of Excellence in R& D (SEV-2015-0554) and from the Spanish National Research Council, through the Ayuda extraordinaria a Centros de Excelencia Severo Ochoa (20205CEX001). Extended author information available on the last page of the article
123
J. S. Fabila-Carrasco et al.
1 Introduction Analysis on graphs is an active area of research that combines several fields in mathematics including combinatorics, analysis, geometry or topology. Problems in this field range from discrete version of results in differential geometry to the study of several combinatorial aspects of the graph in terms of spectral properties of operators on graphs (typically discrete versions of continuous Laplacians), see e.g. [5,8,10,11,20,31,37,38]. The interplay between discrete and continuous structures are very apparent for the class of metric graphs together with their natural Laplacians (see e.g. [14,35] and references therein). The spectrum of a finite graph mostly refers to the spectrum of the adjacency matrix A (e.g. in Cvetkovi´c et al. [8] or in Brouwer and Haemers’ book [5], while the latter book also contains many results on the Laplacian L = D − A and its signless version Q = D + A. Here, D is the matrix with the degrees of the (number
Data Loading...
