Spectra of infinite graphs with summable weight functions

arXiv2206.07688MaRDI QIDQ6402207FDOQ6402207

Authors: Michael Farber, Lewin Strauss 

Publication date: 15 June 2022

Abstract: In this paper we study spectra of Laplacians of infinite weighted graphs. Instead of the assumption of local finiteness we impose the condition of summability of the weight function. Such graphs correspond to reversible Markov chains with countable state spaces. We adopt the concept of the Cheeger constant to this setting and prove an analogue of the Cheeger inequality characterising the spectral gap. We also analyse the concept of the dual Cheeger constant originally introduced in cite{B14}, which allows estimating the top of the spectrum. In this paper we also introduce a new combinatorial invariant, k$(G,m)$, which allows a complete characterisation of bipartite graphs and measures the asymmetry of the spectrum (the Hausdorff distance between the spectrum and its reflection at point $1inBbbR$). We compare k$(G,m)$ to the Cheeger and the dual Cheeger constants. Finally, we analyse in full detail a class of infinite complete graphs and their spectra.

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Infinite graphs (05C63) Random walks on graphs (05C81) Expander graphs (05C48)

This page was built for publication: Spectra of infinite graphs with summable weight functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6402207)