Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-28T06:54:13.375Z Has data issue: false hasContentIssue false
  • English
  • Français

UNIFORM SPANNING FORESTS OF PLANAR GRAPHS

Part of: Graph theory Geometric probability and stochastic geometry

Published online by Cambridge University Press:  13 September 2019

TOM HUTCHCROFT  and
ASAF NACHMIAS
TOM HUTCHCROFT
Affiliation:
Statslab, DPMMS, University of Cambridge, Cambridge CB3 0WB, UK; [email protected]
ASAF NACHMIAS
Affiliation:
Department of Mathematical Sciences, Tel Aviv University, Tel Aviv 6997801, Israel; [email protected]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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. 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 classification

Primary: 60D05: Geometric probability and stochastic geometry
Secondary: 05C10: Planar graphs; geometric and topological aspects of graph theory
Type
Research Article
Information
Forum of Mathematics, Sigma , Volume 7 , 2019 , e29
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
© The Author(s) 2019

References

Aharonov, D., ‘The sharp constant in the ring lemma’, Complex Var. Theory Appl. 33(1–4) (1997), 27–31.Google Scholar
Aldous, D. and Lyons, R., ‘Processes on unimodular random networks’, Electron. J. Probab. 12(54) (2007), 1454–1508.Google Scholar
Anderson, J. W., Hyperbolic Geometry, 2nd edn, Springer Undergraduate Mathematics Series (Springer London, Ltd., London, 2005), xii+276.Google Scholar
Angel, O., Barlow, M. T., Gurel-Gurevich, O. and Nachmias, A., ‘Boundaries of planar graphs, via circle packings’, Ann. Probab. 44(3) (2016), 1956–1984.Google Scholar
Angel, O., Hutchcroft, T., Nachmias, A. and Ray, G., ‘Unimodular hyperbolic triangulations: circle packing and random walk’, Invent. Math. 206(1) (2016), 229–268.Google Scholar
Angel, O., Hutchcroft, T., Nachmias, A. and Ray, G., ‘Hyperbolic and parabolic unimodular random maps’, Geom. Funct. Anal. 28(4) (2018), 879–942.Google Scholar
Angel, O. and Ray, G., ‘The half plane UIPT is recurrent’, Probab. Theory Related Fields 170(3–4) (2018), 657–683.Google Scholar
Barlow, M. T., ‘Loop erased walks and uniform spanning trees’, inDiscrete Geometric Analysis, MSJ Mem., 34 (Math. Soc. Japan, Tokyo, 2016), 1–32.Google Scholar
Barlow, M. T. and Masson, R., ‘Spectral dimension and random walks on the two dimensional uniform spanning tree’, Commun. Math. Phys. 305(1) (2011), 23–57.Google Scholar
Benjamini, I., Lyons, R., Peres, Y. and Schramm, O., ‘Uniform spanning forests’, Ann. Probab. 29(1) (2001), 1–65.Google Scholar
Benjamini, I. and Schramm, O., ‘Harmonic functions on planar and almost planar graphs and manifolds, via circle packings’, Invent. Math. 126(3) (1996), 565–587.Google Scholar
Benjamini, I. and Schramm, O., ‘Recurrence of distributional limits of finite planar graphs’, Electron. J. Probab. 6(23) (2001), 1–13.Google Scholar
Bhupatiraju, S., Hanson, J. and Járai, A. A., ‘Inequalities for critical exponents in d-dimensional sandpiles’, Electron. J. Probab. 22(85) (2017), 51.Google Scholar
Brightwell, G. R. and Scheinerman, E. R., ‘Representations of planar graphs’, SIAM J. Discrete Math. 6(2) (1993), 214–229.Google Scholar
Burton, R. and Pemantle, R., ‘Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances’, Ann. Probab. 21(3) (1993), 1329–1371.Google Scholar
Chelkak, D. et al. , ‘Robust discrete complex analysis: A toolbox’, Ann. Probab. 44(1) (2016), 628–683.Google Scholar
Garban, C., ‘Quantum gravity and the KPZ formula [after Duplantier-Sheffield]’, Astérisque 352 (2013), 315–354.Google Scholar
Gurel-Gurevich, O. and Nachmias, A., ‘Recurrence of planar graph limits’, Ann. of Math. (2) 177(2) (2013), 761–781.Google Scholar
Gurel-Gurevich, O., Nachmias, A. and Souto, J., ‘Recurrence of multiply-ended planar triangulations’, Electron. Commun. Probab. 22(5) (2017), 6.Google Scholar
Häggström, O., ‘Random-cluster measures and uniform spanning trees’, Stochastic Process. Appl. 59(2) (1995), 267–275.Google Scholar
Hansen, L. J., ‘On the Rodin and Sullivan ring lemma’, Complex Var. Theory Appl. 10(1) (1988), 23–30.Google Scholar
He, Z.-X., ‘Rigidity of infinite disk patterns’, Ann. of Math. (2) 149 (1999), 1–33.Google Scholar
He, Z.-X. and Schramm, O., ‘Fixed points, Koebe uniformization and circle packings’, Ann. of Math. (2) 137(2) (1993), 369–406.Google Scholar
He, Z.-X. and Schramm, O., ‘Hyperbolic and parabolic packings’, Discrete Comput. Geom. 14(2) (1995), 123–149.Google Scholar
He, Z.-X. and Schramm, O., ‘The C ∞ -convergence of hexagonal disk packings to the Riemann map’, Acta Math. 180(2) (1998), 219–245.Google Scholar
Hutchcroft, T., ‘Wired cycle-breaking dynamics for uniform spanning forests’, Ann. Probab. 44(6) (2016), 3879–3892.Google Scholar
Hutchcroft, T., ‘Harmonic Dirichlet functions on planar graphs’, Discrete Comput. Geom. 61(3) 479–506.Google Scholar
Hutchcroft, T., ‘Interlacements and the wired uniform spanning forest’, Ann. Probab. 46(2) (2018), 1170–1200.Google Scholar
Hutchcroft, T. and Peres, Y., ‘Boundaries of planar graphs: a unified approach’, Electron. J. Probab. 22(100) (2017), 20.Google Scholar
Jonasson, J. and Schramm, O., ‘On the cover time of planar graphs’, Electron. Comm. Probab. 5 (2000), 85–90 (electronic).Google Scholar
Kenyon, R., ‘The asymptotic determinant of the discrete Laplacian’, Acta Math. 185(2) (2000), 239–286.Google Scholar
Kirchhoff, G., ‘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.Google Scholar
Koebe, P., Kontaktprobleme der konformen Abbildung, (Hirzel, 1936).Google Scholar
Lawler, G. F., Conformally Invariant Processes in the Plane, Mathematical Surveys and Monographs, 114 (American Mathematical Society, Providence, RI, 2005), xii+242.Google Scholar
Lawler, G. F. et al. , ‘A self-avoiding random walk’, Duke Math. J. 47(3) (1980), 655–693.Google Scholar
Lawler, G. F., Schramm, O. and Werner, W., ‘Conformal invariance of planar loop-erased random walks and uniform spanning trees’, Ann. Probab. 32(1) (2004), 939–995.Google Scholar
Lyons, R., Morris, B. J. and Schramm, O., ‘Ends in uniform spanning forests’, Electron. J. Probab. 13(58) (2008), 1702–1725.Google Scholar
Lyons, R. and Peres, Y., Probability on Trees and Networks, Cambridge Series in Statistical and Probabilistic Mathematics, 42 (Cambridge University Press, New York, 2016).Google Scholar
Marden, A. and Rodin, B., ‘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.Google Scholar
Masson, R., ‘The growth exponent for planar loop-erased random walk’, Electron. J. Probab. 14(36) (2009), 1012–1073.Google Scholar
Morris, B., ‘The components of the wired spanning forest are recurrent’, Probab. Theory Related Fields 125(2) (2003), 259–265.Google Scholar
Murugan, M., ‘Quasisymmetric uniformization and heat kernel estimates’, Preprint, 2018,arXiv:1803.11296.Google Scholar
Pemantle, R., ‘Choosing a spanning tree for the integer lattice uniformly’, Ann. Probab. 19(4) (1991), 1559–1574.Google Scholar
Peres, Y., ‘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.Google Scholar
Rodin, B. and Sullivan, D., ‘The convergence of circle packings to the Riemann mapping’, J. Differential Geom. 26(2) (1987), 349–360.Google Scholar
Rohde, S., ‘Oded Schramm: from circle packing to SLE’, Ann. Probab. 39 (2011), 1621–1667.Google Scholar
Schramm, O., ‘Rigidity of infinite (circle) packings’, J. Amer. Math. Soc. 4(1) (1991), 127–149.Google Scholar
Schramm, O., ‘Scaling limits of loop-erased random walks and uniform spanning trees’, Israel J. Math. 118 (2000), 221–288.Google Scholar
Shiraishi, D., ‘Growth exponent for loop-erased random walk in three dimensions’, Ann. Probab. 46(2) (2018), 687–774.Google Scholar
Siders, R., ‘Layered circlepackings and the type problem’, Proc. Amer. Math. Soc. 126(10) (1998), 3071–3074.Google Scholar
Stephenson, K., ‘Circle pack, Java 2.0’, http://www.math.utk.edu/∼kens/CirclePack.Google Scholar
Stephenson, K., Introduction to Circle Packing: The Theory of Discrete Analytic Functions, (Cambridge University Press, Cambridge, 2005).Google Scholar
Thurston, W., ‘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.Google Scholar
Wilson, D. B., ‘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.Google Scholar