×

zbMATH — the first resource for mathematics

Amenability, unimodularity, and the spectral radius of random walks on infinite graphs. (English) Zbl 0693.43001
Consider a locally finite, infinite connected graph G and a vertex- transitive group \(\Gamma\) of automorphisms of G, closed with respect to pointwise convergence. The transition operator \({\mathcal P}\) of the simple random walk on G has norm (spectral radius) \(\| {\mathcal P}\| =1\) if and only if \(\Gamma\) is both amenable and unimodular. If G has more than two ends, then \(\| {\mathcal P}\| <1\). If \(\Gamma\) is amenable then an explicit formula for \(\| {\mathcal P}\|\) is available even for more general transition operators. This allows, for example, easy calculation of the norm of radial transition operators on a homogeneous tree.
Reviewer: P.M.Soardi

MSC:
43A07 Means on groups, semigroups, etc.; amenable groups
60G50 Sums of independent random variables; random walks
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
22D05 General properties and structure of locally compact groups
PDF BibTeX XML Cite
Full Text: DOI EuDML
References:
[1] Berg, C., Christensen, J.P.R.: On the relation between amenability of locally compact groups and the norms of convolution operators. Math. Ann.,208, 149–153 (1974) · Zbl 0269.43002 · doi:10.1007/BF01432382
[2] Betori, W., Faraut, J., Pagliacci, M.: An inversion formula for the Radon transform on trees. Math. Z.201, 327–337 (1989) · Zbl 0651.43003 · doi:10.1007/BF01214899
[3] Biggs, N.L., Mohar, B., Shawe-Taylor, J.: The spectral radius of infinite graphs. Bull. Lond. Math. Soc.20, 116–120 (1988) · Zbl 0671.05052 · doi:10.1112/blms/20.2.116
[4] Brooks, R.: The fundamental group and the spectrum of the Laplacian. Comment. Math. Helv.56, 581–598 (1981) · Zbl 0495.58029 · doi:10.1007/BF02566228
[5] Cartier, P.: Fonctions harmoniques sur un arbre. Symposia Math.9, 203–270 (1972) · Zbl 0283.31005
[6] Cartier, P.: Harmonic analysis on trees. Proc. Symp. Pure Math.9, 419–424 (1972)
[7] Cohen, J.M.: Operator norms on free groups. Boll. Unione. Mat. Ital., VII. Ser., B1, 1055–1065 (1982) · Zbl 0518.46050
[8] Day, M.M.: Convolutions, means and spectra. Ill. J. Math.8, 100–111 (1964) · Zbl 0122.11703
[9] Dodziuk, J.: Difference equations, isoperimetric inequality and transience of certain random walks. Trans. Am. Math. Soc.284, 787–794 (1984) · Zbl 0512.39001 · doi:10.1090/S0002-9947-1984-0743744-X
[10] Dunwoody, M.J.: Cutting up graphs. Combinatorica2, 15–23 (1982) · Zbl 0504.05035 · doi:10.1007/BF02579278
[11] Figà-Talamanca, A., Picadello, M.A.: Harmonic analysis on free groups. (Lect. Notes Pure Appl. Math., Vol. 87) New York: Dekker 1983 · Zbl 0536.43001
[12] Freudenthal, H.: Über die Enden diskreter Räume und Gruppen. Comment. Math. Helv.17, 1–38 (1944) · Zbl 0060.40007 · doi:10.1007/BF02566233
[13] Gerl, P.: Random walks on graphs with a strong isoperimetric inequality. J. Theor. Probab.1, 171–188 (1988) · Zbl 0639.60072 · doi:10.1007/BF01046933
[14] Gromov, M.: Infinite groups as geometric objects. Proc. Int. Congress Math., Warszawa 1983, pp. 385–392 (1984)
[15] Guivarc’h, Y., Keane, M., Roynette, B.: Marches Aléatoires sur les Groupes de Lie. (Lect. Notes Math., Vol. 624) Berlin Heidelberg New York: Springer 1977
[16] Halin, R.: Über unendliche Wege in Graphen. Math. Ann.157, 125–137 (1964) · Zbl 0125.11701 · doi:10.1007/BF01362670
[17] Halin, R.: Automorphisms and endomorphisms of infinite locally finite graphs. Abh. Math. Semin. Univ. Hamb.39, 251–283 (1973) · Zbl 0265.05118 · doi:10.1007/BF02992834
[18] Hewitt, E., Ross, K.A.: Abstract harmonic analysis, I. Berlin Heidelberg New York: Springer 1963 · Zbl 0115.10603
[19] Ivanov, A.A.: Bounding the diameter of a distance-regular graph. Sov. Math. Dokl.28, 149–152 (1983) · Zbl 0552.05034
[20] Jung, H.A.: Connectivity in infinite graphs. In: L. Mirsky (ed.) Stud. Pure Math., pp. 137–143, New York London: Academic Press 1971 · Zbl 0217.02603
[21] Jung, H.A.: A note on fragments of infinite graphs. Combinatorica1, 285–288 (1981) · Zbl 0489.05036 · doi:10.1007/BF02579334
[22] Kesten, H.: Symmetric random walks on groups. Trans. Am. Math. Soc.92, 336–354 (1959) · Zbl 0092.33503 · doi:10.1090/S0002-9947-1959-0109367-6
[23] Kesten, H.: Full Banach mean values on countable groups. Math. Scand.7, 146–156 (1959) · Zbl 0092.26704
[24] Leptin, H.: On locally compact groups with invariant means. Proc. Am. Math. Soc.19, 489–494 (1968) · Zbl 0155.05702 · doi:10.1090/S0002-9939-1968-0239001-7
[25] Nebbia, C.: On the amenability and the Kunze-Stein property for groups acting on a tree. Pac. J. Math.135, 371–380 (1988) · Zbl 0671.43003
[26] Pier, J.P.: Amenable Locally Compact Groups. New York: Wiley 1984 · Zbl 0597.43001
[27] Stallings, J.: Group Theory and Three-Dimensional Manifolds. New Haven: Yale University Press 1971 · Zbl 0241.57001
[28] Trofimov, V.I.: Automorphism groups of graphs as topological objects. Math. Notes38, 717–720 (1985) · Zbl 0596.05033
[29] Woess, W.: Graphs and groups with tree-like properties. J. Comb. Theory, Ser. B47, 361–371 (1989) · Zbl 0696.05027 · doi:10.1016/0095-8956(89)90034-8
[30] Woess, W.: Amenable group actions on infinite graphs. Math. Ann.284, 251–265 (1989) · Zbl 0648.43002 · doi:10.1007/BF01442875
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.