Uniform spanning forests of planar graphs. (English) Zbl 1422.60022
Summary: We prove that the free uniform spanning forest of any bounded degree proper plane graph is connected almost surely, answering a question of Benjamini, Lyons, Peres and Schramm [I. Benjamini et al., Ann. Probab. 29, No. 1, 1–65 (2001; Zbl 1016.60009)]. We provide a quantitative form of this result, calculating the critical exponents governing the geometry of the uniform spanning forests of transient proper plane graphs with bounded degrees and codegrees. We find that the same exponents hold universally over this entire class of graphs provided that measurements are made using the hyperbolic geometry of their circle packings rather than their usual combinatorial geometry.
MSC:
| 60D05 | Geometric probability and stochastic geometry |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
Citations:
Zbl 1016.60009Software:
CirclePackReferences:
| [1] | D.Aharonov, ‘The sharp constant in the ring lemma’, Complex Var. Theory Appl.33(1-4) (1997), 27-31. · Zbl 0903.30006 |
| [2] | D.Aldous and R.Lyons, ‘Processes on unimodular random networks’, Electron. J. Probab.12(54) (2007), 1454-1508. · Zbl 1131.60003 |
| [3] | J. W.Anderson, Hyperbolic Geometry, 2nd edn, Springer Undergraduate Mathematics Series (Springer London, Ltd., London, 2005), xii+276. · Zbl 1077.51008 |
| [4] | O.Angel, M. T.Barlow, O.Gurel-Gurevich and A.Nachmias, ‘Boundaries of planar graphs, via circle packings’, Ann. Probab.44(3) (2016), 1956-1984. · Zbl 1339.05061 |
| [5] | O.Angel, T.Hutchcroft, A.Nachmias and G.Ray, ‘Unimodular hyperbolic triangulations: circle packing and random walk’, Invent. Math.206(1) (2016), 229-268. · Zbl 1360.52012 |
| [6] | O.Angel, T.Hutchcroft, A.Nachmias and G.Ray, ‘Hyperbolic and parabolic unimodular random maps’, Geom. Funct. Anal.28(4) (2018), 879-942. · Zbl 1459.60018 |
| [7] | O.Angel and G.Ray, ‘The half plane UIPT is recurrent’, Probab. Theory Related Fields170(3-4) (2018), 657-683. · Zbl 1482.05316 |
| [8] | M. T.Barlow, ‘Loop erased walks and uniform spanning trees’, inDiscrete Geometric Analysis, MSJ Mem., 34 (Math. Soc. Japan, Tokyo, 2016), 1-32. · Zbl 1343.05139 |
| [9] | M. T.Barlow and R.Masson, ‘Spectral dimension and random walks on the two dimensional uniform spanning tree’, Commun. Math. Phys.305(1) (2011), 23-57. · Zbl 1223.05285 |
| [10] | I.Benjamini, R.Lyons, Y.Peres and O.Schramm, ‘Uniform spanning forests’, Ann. Probab.29(1) (2001), 1-65. · Zbl 1016.60009 |
| [11] | I.Benjamini and O.Schramm, ‘Harmonic functions on planar and almost planar graphs and manifolds, via circle packings’, Invent. Math.126(3) (1996), 565-587. · Zbl 0868.31008 |
| [12] | I.Benjamini and O.Schramm, ‘Recurrence of distributional limits of finite planar graphs’, Electron. J. Probab.6(23) (2001), 1-13. · Zbl 1010.82021 |
| [13] | S.Bhupatiraju, J.Hanson and A. A.Járai, ‘Inequalities for critical exponents in d-dimensional sandpiles’, Electron. J. Probab.22(85) (2017), 51. · Zbl 1386.60318 |
| [14] | G. R.Brightwell and E. R.Scheinerman, ‘Representations of planar graphs’, SIAM J. Discrete Math.6(2) (1993), 214-229. · Zbl 0782.05026 |
| [15] | R.Burton and R.Pemantle, ‘Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances’, Ann. Probab.21(3) (1993), 1329-1371. · Zbl 0785.60007 |
| [16] | D.Chelkak, ‘Robust discrete complex analysis: A toolbox’, Ann. Probab.44(1) (2016), 628-683. · Zbl 1347.60050 |
| [17] | C.Garban, ‘Quantum gravity and the KPZ formula [after Duplantier-Sheffield]’, Astérisque352 (2013), 315-354. · Zbl 1295.83034 |
| [18] | O.Gurel-Gurevich and A.Nachmias, ‘Recurrence of planar graph limits’, Ann. of Math. (2)177(2) (2013), 761-781. · Zbl 1262.05031 |
| [19] | O.Gurel-Gurevich, A.Nachmias and J.Souto, ‘Recurrence of multiply-ended planar triangulations’, Electron. Commun. Probab.22(5) (2017), 6. · Zbl 1360.52013 |
| [20] | O.Häggström, ‘Random-cluster measures and uniform spanning trees’, Stochastic Process. Appl.59(2) (1995), 267-275. · Zbl 0840.60089 |
| [21] | L. J.Hansen, ‘On the Rodin and Sullivan ring lemma’, Complex Var. Theory Appl.10(1) (1988), 23-30. · Zbl 0617.30006 |
| [22] | Z.-X.He, ‘Rigidity of infinite disk patterns’, Ann. of Math. (2)149 (1999), 1-33. · Zbl 0922.30020 |
| [23] | Z.-X.He and O.Schramm, ‘Fixed points, Koebe uniformization and circle packings’, Ann. of Math. (2)137(2) (1993), 369-406. · Zbl 0777.30002 |
| [24] | Z.-X.He and O.Schramm, ‘Hyperbolic and parabolic packings’, Discrete Comput. Geom.14(2) (1995), 123-149. · Zbl 0830.52010 |
| [25] | Z.-X.He and O.Schramm, ‘The C^∞-convergence of hexagonal disk packings to the Riemann map’, Acta Math.180(2) (1998), 219-245. · Zbl 0913.30004 |
| [26] | T.Hutchcroft, ‘Wired cycle-breaking dynamics for uniform spanning forests’, Ann. Probab.44(6) (2016), 3879-3892. · Zbl 1364.05062 |
| [27] | T.Hutchcroft, ‘Harmonic Dirichlet functions on planar graphs’, Discrete Comput. Geom.61(3) 479-506. · Zbl 1412.31011 |
| [28] | T.Hutchcroft, ‘Interlacements and the wired uniform spanning forest’, Ann. Probab.46(2) (2018), 1170-1200. · Zbl 1391.60021 |
| [29] | T.Hutchcroft and Y.Peres, ‘Boundaries of planar graphs: a unified approach’, Electron. J. Probab.22(100) (2017), 20. · Zbl 1378.05189 |
| [30] | J.Jonasson and O.Schramm, ‘On the cover time of planar graphs’, Electron. Comm. Probab.5 (2000), 85-90 (electronic). · Zbl 0949.60083 |
| [31] | R.Kenyon, ‘The asymptotic determinant of the discrete Laplacian’, Acta Math.185(2) (2000), 239-286. · Zbl 0982.05013 |
| [32] | G.Kirchhoff, ‘Ueber die auflösung der gleichungen, auf welche man bei der untersuchung der linearen vertheilung galvanischer ströme geführt wird’, Ann. Phys.148(12) (1847), 497-508. |
| [33] | P.Koebe, Kontaktprobleme der konformen Abbildung, (Hirzel, 1936). · Zbl 0017.21701 |
| [34] | G. F.Lawler, Conformally Invariant Processes in the Plane, Mathematical Surveys and Monographs, 114 (American Mathematical Society, Providence, RI, 2005), xii+242. · Zbl 1074.60002 |
| [35] | G. F.Lawler, ‘A self-avoiding random walk’, Duke Math. J.47(3) (1980), 655-693. · Zbl 0445.60058 |
| [36] | G. F.Lawler, O.Schramm and W.Werner, ‘Conformal invariance of planar loop-erased random walks and uniform spanning trees’, Ann. Probab.32(1) (2004), 939-995. · Zbl 1126.82011 |
| [37] | R.Lyons, B. J.Morris and O.Schramm, ‘Ends in uniform spanning forests’, Electron. J. Probab.13(58) (2008), 1702-1725. · Zbl 1191.60016 |
| [38] | R.Lyons and Y.Peres, Probability on Trees and Networks, Cambridge Series in Statistical and Probabilistic Mathematics, 42 (Cambridge University Press, New York, 2016). · Zbl 1376.05002 |
| [39] | A.Marden and B.Rodin, ‘On Thurston’s formulation and proof of Andreev’s theorem’, inComputational Methods and Function Theory (Valparaíso, 1989), Lecture Notes in Math., 1435 (Springer, Berlin, 1990), 103-115. · Zbl 0717.52014 |
| [40] | R.Masson, ‘The growth exponent for planar loop-erased random walk’, Electron. J. Probab.14(36) (2009), 1012-1073. · Zbl 1191.60061 |
| [41] | B.Morris, ‘The components of the wired spanning forest are recurrent’, Probab. Theory Related Fields125(2) (2003), 259-265. · Zbl 1031.60035 |
| [42] | M.Murugan, ‘Quasisymmetric uniformization and heat kernel estimates’, Preprint, 2018,arXiv:1803.11296. · Zbl 1480.52014 |
| [43] | R.Pemantle, ‘Choosing a spanning tree for the integer lattice uniformly’, Ann. Probab.19(4) (1991), 1559-1574. · Zbl 0758.60010 |
| [44] | Y.Peres, ‘Probability on trees: an introductory climb’, inLectures on Probability Theory and Statistics (Saint-Flour, 1997), Lecture Notes in Math., 1717 (Springer, Berlin, 1999), 193-280. · Zbl 0957.60001 |
| [45] | B.Rodin and D.Sullivan, ‘The convergence of circle packings to the Riemann mapping’, J. Differential Geom.26(2) (1987), 349-360. · Zbl 0694.30006 |
| [46] | S.Rohde, ‘Oded Schramm: from circle packing to SLE’, Ann. Probab.39 (2011), 1621-1667. · Zbl 1236.60004 |
| [47] | O.Schramm, ‘Rigidity of infinite (circle) packings’, J. Amer. Math. Soc.4(1) (1991), 127-149. · Zbl 0726.52008 |
| [48] | O.Schramm, ‘Scaling limits of loop-erased random walks and uniform spanning trees’, Israel J. Math.118 (2000), 221-288. · Zbl 0968.60093 |
| [49] | D.Shiraishi, ‘Growth exponent for loop-erased random walk in three dimensions’, Ann. Probab.46(2) (2018), 687-774. · Zbl 1387.60067 |
| [50] | R.Siders, ‘Layered circlepackings and the type problem’, Proc. Amer. Math. Soc.126(10) (1998), 3071-3074. · Zbl 0910.52012 |
| [51] | K.Stephenson, ‘Circle pack, Java 2.0’, http://www.math.utk.edu/∼kens/CirclePack. |
| [52] | K.Stephenson, Introduction to Circle Packing: The Theory of Discrete Analytic Functions, (Cambridge University Press, Cambridge, 2005). · Zbl 1074.52008 |
| [53] | W.Thurston, ‘Hyperbolic geometry and 3-manifolds’, inLow-dimensional Topology (Bangor, 1979), London Math. Soc. Lecture Note Ser., 48 (Cambridge Univ. Press, Cambridge-New York, 1982), 9-25. · Zbl 0483.57007 |
| [54] | D. B.Wilson, ‘Generating random spanning trees more quickly than the cover time’, inProceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing (Philadelphia, PA, 1996) (ACM, New York, 1996), 296-303. · Zbl 0946.60070 |
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.
