Ends in Uniform Spanning Forests

Russell Lyons (Indiana University)
Benjamin J. Morris (U. Calif., Davis)
Oded Schramm (Microsoft Research)

Abstract


It has hitherto been known that in a transitive unimodular graph, each tree in the wired spanning forest has only one end a.s. We dispense with the assumptions of transitivity and unimodularity, replacing them with a much broader condition on the isoperimetric profile that requires just slightly more than uniform transience.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1702-1725

Publication Date: September 21, 2008

DOI: 10.1214/EJP.v13-566

References

  1. Aldous, D.J. ; Lyons, R. (2007). Processes on unimodular random networks. Electron. J. Probab. 12, no. 54, 1454--1508 (electronic).
  2. Benjamini, I.; Lyons, R.; Peres, Y.; Schramm, O. Group-invariant percolation on graphs. Geom. Funct. Anal. 9 (1999), no. 1, 29--66. MR1675890 (99m:60149)
  3. Benjamini, Itai; Lyons, Russell; Peres, Yuval; Schramm, Oded. Uniform spanning forests. Ann. Probab. 29 (2001), no. 1, 1--65. MR1825141 (2003a:60015)
  4. Chen, Dayue; Peres, Yuval. Anchored expansion, percolation and speed.With an appendix by Gábor Pete. Ann. Probab. 32 (2004), no. 4, 2978--2995. MR2094436 (2005g:60022)
  5. Coulhon, Thierry; Saloff-Coste, Laurent. Isopérimétrie pour les groupes et les variétés.(French) [Isoperimetry for groups and manifolds] Rev. Mat. Iberoamericana 9 (1993), no. 2, 293--314. MR1232845 (94g:58263)
  6. Feder, T.; Mihail, M. (1992). Balanced matroids. In Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, pages 26--38, New York. Association for Computing Machinery (ACM). Held in Victoria, BC, Canada.
  7. Gromov, Mikhael. Groups of polynomial growth and expanding maps. Inst. Hautes Études Sci. Publ. Math. No. 53 (1981), 53--73. MR0623534 (83b:53041)
  8. Häggström, Olle. Random-cluster measures and uniform spanning trees. Stochastic Process. Appl. 59 (1995), no. 2, 267--275. MR1357655 (97b:60170)
  9. Häggström, Olle. Uniform and minimal essential spanning forests on trees. Random Structures Algorithms 12 (1998), no. 1, 27--50. MR1637387 (99i:05186)
  10. He, Zheng-Xu; Schramm, O. Hyperbolic and parabolic packings. Discrete Comput. Geom. 14 (1995), no. 2, 123--149. MR1331923 (96h:52017)
  11. Járai, Antal A.; Redig, Frank. Infinite volume limit of the abelian sandpile model in dimensions $dgeq 3$. Probab. Theory Related Fields 141 (2008), no. 1-2, 181--212. MR2372969
  12. Kirchhoff, G. (1847). Ueber die Auflosung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Strome gefuhrt wird. Ann. Phys. und Chem. 72, 497--508.
  13. Krikun, Maxim. Connected allocation to Poisson points in $Bbb Rsp 2$. Electron. Comm. Probab. 12 (2007), 140--145 (electronic). MR2318161 (2008b:60023)
  14. Lawler, Gregory F. Intersections of random walks.Probability and its Applications. Birkhäuser Boston, Inc., Boston, MA, 1991. 219 pp. ISBN: 0-8176-3557-2 MR1117680 (92f:60122)
  15. Lyons, Russell. A bird's-eye view of uniform spanning trees and forests. Microsurveys in discrete probability (Princeton, NJ, 1997), 135--162, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 41, Amer. Math. Soc., Providence, RI, 1998. MR1630412 (99e:60029)
  16. Morris, Ben. The components of the wired spanning forest are recurrent. Probab. Theory Related Fields 125 (2003), no. 2, 259--265. MR1961344 (2004a:60024)
  17. Pemantle, Robin. Choosing a spanning tree for the integer lattice uniformly. Ann. Probab. 19 (1991), no. 4, 1559--1574. MR1127715 (92g:60014)
  18. Saloff-Coste, L. Isoperimetric inequalities and decay of iterated kernels for almost-transitive Markov chains. Combin. Probab. Comput. 4 (1995), no. 4, 419--442. MR1377559 (97c:60171)
  19. Soardi, Paolo M.; Woess, Wolfgang. Amenability, unimodularity, and the spectral radius of random walks on infinite graphs. Math. Z. 205 (1990), no. 3, 471--486. MR1082868 (91m:43002)
  20. Thomassen, Carsten. Isoperimetric inequalities and transient random walks on graphs. Ann. Probab. 20 (1992), no. 3, 1592--1600. MR1175279 (94a:60106)
  21. Trofimov, V. I. Groups of automorphisms of graphs as topological groups.(Russian) Mat. Zametki 38 (1985), no. 3, 378--385, 476. MR0811571 (87d:05091)
  22. Woess, W. (2000). Random Walks on Infinite Graphs and Groups, volume 138 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge.MR1743100
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.