Home | Contents | Submissions, editors, etc. | Login | Search | ECP
 Electronic Journal of Probability > Vol. 13 (2008) > Paper 58 open journal systems 


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: PDF

Pages: 1702-1725

Published on: September 21, 2008
Bibliography
  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
















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | ECP

Electronic Journal of Probability. ISSN: 1083-6489