Boundaries of planar graphs, via circle packings. (English) Zbl 1339.05061
Summary: We provide a geometric representation of the Poisson and Martin boundaries of a transient, bounded degree triangulation of the plane in terms of its circle packing in the unit disc. (This packing is unique up to Möbius transformations.) More precisely, we show that any bounded harmonic function on the graph is the harmonic extension of some measurable function on the boundary of the disk, and that the space of extremal positive harmonic functions, that is, the Martin boundary, is homeomorphic to the unit circle.
All our results hold more generally for any “good”-embedding of planar graphs, that is, an embedding in the unit disc with straight lines such that angles are bounded away from 0 and \(\pi\) uniformly, and lengths of adjacent edges are comparable. Furthermore, we show that in a good embedding of a planar graph the probability that a random walk exits a disc through a sufficiently wide arc is at least a constant, and that Brownian motion on such graphs takes time of order \(r^{2}\) to exit a disc of radius \(r\). These answer a question recently posed by D. Chelkak [Ann. Probab. 44, No. 1, 628–683 (2016; Zbl 1347.60050)].
All our results hold more generally for any “good”-embedding of planar graphs, that is, an embedding in the unit disc with straight lines such that angles are bounded away from 0 and \(\pi\) uniformly, and lengths of adjacent edges are comparable. Furthermore, we show that in a good embedding of a planar graph the probability that a random walk exits a disc through a sufficiently wide arc is at least a constant, and that Brownian motion on such graphs takes time of order \(r^{2}\) to exit a disc of radius \(r\). These answer a question recently posed by D. Chelkak [Ann. Probab. 44, No. 1, 628–683 (2016; Zbl 1347.60050)].
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C81 | Random walks on graphs |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
Citations:
Zbl 1347.60050Software:
CirclePackReferences:
| [1] | Aikawa, H. (2001). Boundary Harnack principle and Martin boundary for a uniform domain. J. Math. Soc. Japan 53 119-145. · Zbl 0976.31002 · doi:10.2969/jmsj/05310119 |
| [2] | Aikawa, H., Lundh, T. and Mizutani, T. (2003). Martin boundary of a fractal domain. Potential Anal. 18 311-357. · Zbl 1021.31002 · doi:10.1023/A:1021823023212 |
| [3] | Ancona, A. (1978). Principe de Harnack à la frontière et théorème de Fatou pour un opérateur elliptique dans un domaine lipschitzien. Ann. Inst. Fourier ( Grenoble ) 28 169-213. · Zbl 0377.31001 · doi:10.5802/aif.720 |
| [4] | Ancona, A., Lyons, R. and Peres, Y. (1999). Crossing estimates and convergence of Dirichlet functions along random walk and diffusion paths. Ann. Probab. 27 970-989. · Zbl 0945.60063 · doi:10.1214/aop/1022677392 |
| [5] | Barlow, M. T., Grigor’yan, A. and Kumagai, T. (2012). On the equivalence of parabolic Harnack inequalities and heat kernel estimates. J. Math. Soc. Japan 64 1091-1146. · Zbl 1281.58016 · doi:10.2969/jmsj/06441091 |
| [6] | Bass, R. F. and Burdzy, K. (1991). A boundary Harnack principle in twisted Hölder domains. Ann. of Math. (2) 134 253-276. · Zbl 0747.31008 · doi:10.2307/2944347 |
| [7] | Benjamini, I. and Schramm, O. (1996). Harmonic functions on planar and almost planar graphs and manifolds, via circle packings. Invent. Math. 126 565-587. · Zbl 0868.31008 · doi:10.1007/s002220050109 |
| [8] | Chelkak, D. (2016). Robust discrete complex analysis: A toolbox. Ann. Probab. 44 628-683. · Zbl 1347.60050 · doi:10.1214/14-AOP985 |
| [9] | Chen, Z.-Q. and Fukushima, M. (2012). Symmetric Markov Processes , Time Change , and Boundary Theory. London Mathematical Society Monographs Series 35 . Princeton Univ. Press, Princeton, NJ. · Zbl 1253.60002 |
| [10] | Derriennic, Y. (1976). Lois “zéro ou deux” pour les processus de Markov. Applications aux marches aléatoires. Ann. Inst. H. Poincaré Sect. B ( N.S. ) 12 111-129. · Zbl 0353.60075 |
| [11] | Durrett, R. (2010). Probability : Theory and Examples , 4th ed. Cambridge Univ. Press, Cambridge. · Zbl 1202.60001 · doi:10.1017/CBO9780511779398 |
| [12] | Dynkin, E. B. (1969). The boundary theory of Markov processes (discrete case). Uspekhi Mat. Nauk 24 3-42. · Zbl 0222.60048 · doi:10.1070/RM1969v024n02ABEH001341 |
| [13] | Folz, M. (2014). Volume growth and stochastic completeness of graphs. Trans. Amer. Math. Soc. 366 2089-2119. · Zbl 1325.60069 · doi:10.1090/S0002-9947-2013-05930-2 |
| [14] | Fukushima, M., Ōshima, Y. and Takeda, M. (1994). Dirichlet Forms and Symmetric Markov Processes. De Gruyter Studies in Mathematics 19 . de Gruyter, Berlin. |
| [15] | Georgakopoulos, A. (2016). The boundary of a square tiling of a graph coincides with the Poisson boundary. Inventiones Mathematicae . · Zbl 1332.05039 · doi:10.1007/s00222-015-0601-0 |
| [16] | He, Z.-X. and Schramm, O. (1995). Hyperbolic and parabolic packings. Discrete Comput. Geom. 14 123-149. · Zbl 0830.52010 · doi:10.1007/BF02570699 |
| [17] | Jerison, D. (1986). The Poincaré inequality for vector fields satisfying Hörmander’s condition. Duke Math. J. 53 503-523. · Zbl 0614.35066 · doi:10.1215/S0012-7094-86-05329-9 |
| [18] | Jerison, D. S. and Kenig, C. E. (1982). Boundary behavior of harmonic functions in nontangentially accessible domains. Adv. in Math. 46 80-147. · Zbl 0514.31003 · doi:10.1016/0001-8708(82)90055-X |
| [19] | Kaimanovich, V. A. (1992). Measure-theoretic boundaries of Markov chains, \(0\)-\(2\) laws and entropy. In Harmonic Analysis and Discrete Potential Theory ( Frascati , 1991) 145-180. Plenum, New York. · doi:10.1007/978-1-4899-2323-3_13 |
| [20] | Koebe, P. (1936). Kontaktprobleme der Konformen Abbildung. Ber. Sächs. Akad. Wiss. Leipzig , Math.-Phys. Kl. 88 141-164. · Zbl 0017.21701 |
| [21] | Lierl, J. and Saloff-Coste, L. (2014). Scale-invariant boundary Harnack principle in inner uniform domains. Osaka J. Math. 51 619-656. · Zbl 1301.31008 |
| [22] | Lyons, R. and Peres, Y. (2014). Probability on trees and networks. Cambridge Univ. Press, Preprint. Available at . · Zbl 1376.05002 |
| [23] | Martin, R. S. (1941). Minimal positive harmonic functions. Trans. Amer. Math. Soc. 49 137-172. · Zbl 0025.33302 · doi:10.2307/1990054 |
| [24] | Rodin, B. and Sullivan, D. (1987). The convergence of circle packings to the Riemann mapping. J. Differential Geom. 26 349-360. · Zbl 0694.30006 |
| [25] | Rohde, S. (2011). Oded Schramm: From circle packing to SLE. Ann. Probab. 39 1621-1667. · Zbl 1236.60004 · doi:10.1214/10-AOP590 |
| [26] | Saloff-Coste, L. (2002). Aspects of Sobolev-Type Inequalities. London Mathematical Society Lecture Note Series 289 . Cambridge Univ. Press, Cambridge. · Zbl 0991.35002 |
| [27] | Stephenson, K. (2005). Introduction to Circle Packing : The Theory of Discrete Analytic Functions . Cambridge Univ. Press, Cambridge. · Zbl 1074.52008 |
| [28] | Sturm, K. T. (1996). Analysis on local Dirichlet spaces. III. The parabolic Harnack inequality. J. Math. Pures Appl. (9) 75 273-297. · Zbl 0854.35016 |
| [29] | Varopoulos, N. T. (1985). Long range estimates for Markov chains. Bull. Math. Sci. 109 225-252. · Zbl 0583.60063 |
| [30] | Walsh, J. B. (1978). A diffusion with a discontinuous local time. Temps Locaux , Astérisque 52-53 37-45. |
| [31] | Woess, W. (2000). Random Walks on Infinite Graphs and Groups. Cambridge Tracts in Mathematics 138 . Cambridge Univ. Press, Cambridge. · Zbl 0951.60002 · doi:10.1017/CBO9780511470967 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
