Martin and end compactifications for non-locally finite graphs

Cartwright, Donald I.; Soardi, Paolo M.; Woess, Wolfgang

doi:10.1090/S0002-9947-1993-1102885-3

Martin and end compactifications for non-locally finite graphs
HTML articles powered by AMS MathViewer

by Donald I. Cartwright, Paolo M. Soardi and Wolfgang Woess PDF

Trans. Amer. Math. Soc. 338 (1993), 679-693 Request permission

Abstract:

We consider a connected graph, having countably infinite vertex set $X$, which is permitted to have vertices of infinite degree. For a transient irreducible transition matrix $P$ corresponding to a nearest neighbor random walk on $X$, we study the associated harmonic functions on $X$ and, in particular, the Martin compactification. We also study the end compactification of the graph. When the graph is a tree, we show that these compactifications coincide; they are a disjoint union of $X$, the set of ends, and the set of improper vertices—new points associated with vertices of infinite degree. Other results proved include a solution of the Dirichlet problem in the context of the end compactification of a general graph. Applications are given to, e.g., the Cayley graph of a free group on infinitely many generators.

References

P. Cartier, Fonctions harmoniques sur un arbre, Symposia Mathematica, Vol. IX (Convegno di Calcolo delle Probabilità, INDAM, Rome, 1971) Academic Press, London, 1972, pp. 203–270 (French). MR 0353467
Donald I. Cartwright and Stanley Sawyer, The Martin boundary for general isotropic random walks in a tree, J. Theoret. Probab. 4 (1991), no. 1, 111–136. MR 1088396, DOI 10.1007/BF01046997
Corneliu Constantinescu and Aurel Cornea, Ideale Ränder Riemannscher Flächen, Ergebnisse der Mathematik und ihrer Grenzgebiete, (N.F.), Band 32, Springer-Verlag, Berlin-Göttingen-Heidelberg, 1963 (German). MR 0159935, DOI 10.1007/978-3-642-87031-6
Yves Derriennic, Marche aléatoire sur le groupe libre et frontière de Martin, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 32 (1975), no. 4, 261–276 (French). MR 388545, DOI 10.1007/BF00535840
Yves Derriennic and Yves Guivarc’h, Théorème de renouvellement pour les groupes non moyennables, C. R. Acad. Sci. Paris Sér. A-B 277 (1973), A613–A615 (French). MR 328990
J. L. Doob, Discrete potential theory and boundaries, J. Math. Mech. 8 (1959), 433–458; erratum 993. MR 0107098, DOI 10.1512/iumj.1959.8.58063
Hans Freudenthal, Über die Enden diskreter Räume und Gruppen, Comment. Math. Helv. 17 (1945), 1–38 (German). MR 12214, DOI 10.1007/BF02566233
Harry Furstenberg, Random walks and discrete subgroups of Lie groups, Advances in Probability and Related Topics, Vol. 1, Dekker, New York, 1971, pp. 1–63. MR 0284569
R. Halin, Über unendliche Wege in Graphen, Math. Ann. 157 (1964), 125–137 (German). MR 170340, DOI 10.1007/BF01362670
G. A. Hunt, Markoff chains and Martin boundaries, Illinois J. Math. 4 (1960), 313–340. MR 123364
H. A. Jung, Connectivity in infinite graphs, Studies in Pure Mathematics (Presented to Richard Rado), Academic Press, London, 1971, pp. 137–143. MR 0278982
John L. Kelley, General topology, Graduate Texts in Mathematics, No. 27, Springer-Verlag, New York-Berlin, 1975. Reprint of the 1955 edition [Van Nostrand, Toronto, Ont.]. MR 0370454
John G. Kemeny, J. Laurie Snell, and Anthony W. Knapp, Denumerable Markov chains, 2nd ed., Graduate Texts in Mathematics, No. 40, Springer-Verlag, New York-Heidelberg-Berlin, 1976. With a chapter on Markov random fields, by David Griffeath. MR 0407981, DOI 10.1007/978-1-4684-9455-6
Norbert Polat, Aspects topologiques de la séparation dans les graphes infinis. I, Math. Z. 165 (1979), no. 1, 73–100 (French). MR 521521, DOI 10.1007/BF01175130
Massimo A. Picardello and Wolfgang Woess, Martin boundaries of random walks: ends of trees and groups, Trans. Amer. Math. Soc. 302 (1987), no. 1, 185–205. MR 887505, DOI 10.1090/S0002-9947-1987-0887505-2
Massimo A. Picardello and Wolfgang Woess, Harmonic functions and ends of graphs, Proc. Edinburgh Math. Soc. (2) 31 (1988), no. 3, 457–461. MR 969074, DOI 10.1017/S0013091500037640
D. Revuz, Markov chains, 2nd ed., North-Holland Mathematical Library, vol. 11, North-Holland Publishing Co., Amsterdam, 1984. MR 758799
J. C. Taylor, The Martin boundaries of equivalent sheaves, Ann. Inst. Fourier (Grenoble) 20 (1970), no. fasc. 1, 433–456 (English, with French summary). MR 267120, DOI 10.5802/aif.346
Wolfgang Woess, A description of the Martin boundary for nearest neighbour random walks on free products, Probability measures on groups, VIII (Oberwolfach, 1985) Lecture Notes in Math., vol. 1210, Springer, Berlin, 1986, pp. 203–215. MR 879007, DOI 10.1007/BFb0077185