On adjacency operators of locally finite graphs

V. I. Trofimov

Izvestiya. Mathematics , Tome 88 (2024) no. 3, pp. 542-589.

Résumé

A graph $\Gamma$ is called locally finite if, for each vertex $v\in \Gamma$, the set $\Gamma(v)$ of its adjacent vertices is finite. For an arbitrary locally finite graph $\Gamma$ with vertex set $V(\Gamma)$ and an arbitrary field $F$, let $F^{V(\Gamma)}$ be the vector space over $F$ of all functions $V(\Gamma) \to F$ (with natural componentwise operations) and let $A^{(\mathrm{alg})}_{\Gamma,F}$ be the linear operator $F^{V(\Gamma)} \to F^{V(\Gamma)}$ defined by $(A^{(\mathrm{alg})}_{\Gamma,F}(f))(v) = \sum_{u \in \Gamma(v)}f(u)$ for all $f \in F^{V(\Gamma)}$, $v \in V(\Gamma)$. In the case of a finite graph $\Gamma$, the mapping $A^{({\mathrm{alg}})}_{\Gamma,F}$ is the well-known operator defined by the adjacency matrix of the graph $\Gamma$ (over $F$), and the theory of eigenvalues and eigenfunctions of such operators is a well developed part of the theory of finite graphs (at least, in the case $F = \mathbb{C}$). In the present paper, we develop the theory of eigenvalues and eigenfunctions of the operators $A^{({\mathrm{alg}})}_{\Gamma,F}$ for infinite locally finite graphs $\Gamma$ (however, some results that follow may present certain interest for the theory of finite graphs) and arbitrary fields $F$, even though in the present paper special emphasis is placed on the case of a connected graph $\Gamma$ with uniformly bounded degrees of vertices and $F = \mathbb{C}$. The previous attempts in this direction were not, in the author's opinion, quite satisfactory in the sense that they have been concerned only with eigenfunctions (and corresponding eigenvalues) of rather special type.

Détail

Keywords: locally finite graph, adjacency matrix, eigenvalue, eigenfunction.

Bibliographie

[1] S. Lang, Algebra, Addison-Wesley Publishing Co., Inc., Reading, MA, 1965 | MR | Zbl

[2] D. Cvetković, M. Doob, and H. Sachs, Spectra of graphs. Theory and applications, Pure Appl. Math., 87, Academic Press, Inc., New York–London; DVW, Berlin, 1980 | MR | Zbl

[3] A. E. Brouwer and W. H. Haemers, Spectra of graphs, Universitext, Springer, New York, 2012 | DOI | MR | Zbl

[4] B. Mohar, “The spectrum of an infinite graph”, Linear Algebra Appl., 48 (1982), 245–256 | DOI | MR | Zbl

[5] B. Mohar and W. Woess, “A survey on spectra of infinite graphs”, Bull. London Math. Soc., 21:3 (1989), 209–234 | DOI | MR | Zbl

[6] O. Toeplitz, “Über die Auflösung unendlichvieler linearer Gleichungen mit unendlichvielen Unbekannten”, Rend. Circ. Mat. Palermo, 28 (1909), 88–96 | DOI | Zbl

[7] A. Abian, “Solvability of infinite systems of linear equations”, Arch. Math. (Brno), 12:1 (1976), 43–44 | MR | Zbl

[8] Yu. I. Lyubich, “Linear functional analysis”, Functional analysis I, Encyclopaedia Math. Sci., 19, Springer-Verlag, Berlin, 1992, 1–283 | DOI | MR | Zbl

[9] Shi Qiang Wang, “The inverses of infinite matrices over a field”, (­ ЄЁв. п§.), Beijing Shifan Daxue Xuebao [J. Beijing Normal Univ. (Nat. Sci.)], 29:3 (1993), 327–330 | MR | Zbl

[10] V. I. Trofimov, “The existence of nonconstant harmonic functions on infinite vertex-symmetric graphs”, European J. Combin., 19:4 (1998), 519–523 | DOI | MR | Zbl

[11] The Kourovka notebook. Unsolved problems in group theory, 15th augm. ed., eds. V. D. Mazurov and E. I. Khukhro, Rus. Acad. Sci. Sib. Branch Inst. Math., Novosibirsk, 2002 | MR | Zbl

[12] C. D. Godsil, Algebraic combinatorics, Chapman and Hall Math. Ser., Chapman Hall, New York, 1993 | MR | Zbl

[13] W. Woess, Random walks on infinite graphs and groups, Cambridge Tracts in Math., 138, Cambridge Univ. Press, Cambridge, 2000 | DOI | MR | Zbl

[14] N. Bourbaki, Éléments de mathématique. Livre II: Algèbre, Ch. IV: Polynomes et fractions rationnelles. Ch. V: Corps commutatifs, Actualités Sci. Indust., 1102, Hermann Cie, Paris, 1950 ; Ch. VI: Groupes et corps ordonnés, Actualités Sci. Indust., 1179, Hermann Cie, Paris, 1952 | MR | Zbl | MR | Zbl

[15] L. Bartholdi, “Counting paths in graphs”, Enseign. Math. (2), 45:1-2 (1999), 83–131 | MR | Zbl

[16] A. E. Taylor, Introduction to functional analysis, John Wiley Sons, Inc., New York; Chapman Hall, Ltd., London, 1958 | MR | Zbl

[17] O. Bratteli and D. W. Robinson, Operator algebras and quantum statistical mechanics, v. 1, Texts Monogr. Phys., Springer-Verlag, New York–Heidelberg–Berlin, 1979 | DOI | MR | Zbl

[18] M. H. Stone, Linear transformations in Hilbert space and their applications to analysis, Amer. Math. Soc. Colloq. Publ., 15, Amer. Math. Soc., New York, 1932 | DOI | MR | Zbl