Percolation beyond \(\mathbb Z^{d}\): the contributions of Oded Schramm. (English) Zbl 1231.60111

Häggström, Olle

Ann. Probab. 39, No. 5, 1668-1701 (2011).

This paper is dedicated to the memory of Oded Schramm. The author reviews some of Schramm’s work on percolation processes taking place on graph structures more exotic than the usual \(\mathbb Z^d\)-setting.

Reviewer: Nasir N. Ganikhodjaev (Kuantan)

MSC:

60K35	Interacting random processes; statistical mechanics type models; percolation theory
82B43	Percolation
60B99	Probability theory on algebraic and topological structures
51M10	Hyperbolic and elliptic geometries (general) and generalizations
60K37	Processes in random environments

Keywords:

percolation; amenability; hyperbolic plane; mass transport; uniform spanning forest

References:

[1]	Aizenman, M., Kesten, H. and Newman, C. M. (1987). Uniqueness of the infinite cluster and continuity of connectivity functions for short and long range percolation. Comm. Math. Phys. 111 505-531. · Zbl 0642.60102 · doi:10.1007/BF01219071
[2]	Aldous, D. J. (1990). The random walk construction of uniform spanning trees and uniform labelled trees. SIAM J. Discrete Math. 3 450-465. · Zbl 0717.05028 · doi:10.1137/0403039
[3]	Aldous, D. and Lyons, R. (2007). Processes on unimodular random networks. Electron. J. Probab. 12 1454-1508. · Zbl 1131.60003
[4]	Alexander, K. S. (1995). Percolation and minimal spanning forests in infinite graphs. Ann. Probab. 23 87-104. · Zbl 0827.60079 · doi:10.1214/aop/1176988378
[5]	Babai, L. (1997). The growth rate of vertex-transitive planar graphs. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms ( New Orleans , LA , 1997) 564-573. ACM, New York. · Zbl 1321.05059
[6]	Benjamini, I., Häggström, O. and Schramm, O. (2000). On the effect of adding \varepsilon -Bernoulli percolation to everywhere percolating subgraphs of \Bbb Z d . J. Math. Phys. 41 1294-1297. · Zbl 0977.82021 · doi:10.1063/1.533187
[7]	Benjamini, I., Jonasson, J., Schramm, O. and Tykesson, J. (2009). Visibility to infinity in the hyperbolic plane, despite obstacles. ALEA Lat. Am. J. Probab. Math. Stat. 6 323-342. · Zbl 1276.82012
[8]	Benjamini, I., Kesten, H., Peres, Y. and Schramm, O. (2004). Geometry of the uniform spanning forest: Transitions in dimensions 4, 8, 12, \cdots . Ann. of Math. (2) 160 465-491. · Zbl 1071.60006 · doi:10.4007/annals.2004.160.465
[9]	Benjamini, I., Lyons, R., Peres, Y. and Schramm, O. (1999). Group-invariant percolation on graphs. Geom. Funct. Anal. 9 29-66. · Zbl 0924.43002 · doi:10.1007/s000390050080
[10]	Benjamini, I., Lyons, R., Peres, Y. and Schramm, O. (1999). Critical percolation on any nonamenable group has no infinite clusters. Ann. Probab. 27 1347-1356. · Zbl 0961.60015 · doi:10.1214/aop/1022677450
[11]	Benjamini, I., Lyons, R., Peres, Y. and Schramm, O. (2001). Uniform spanning forests. Ann. Probab. 29 1-65. · Zbl 1016.60009
[12]	Benjamini, I., Lyons, R. and Schramm, O. (1999). Percolation perturbations in potential theory and random walks. In Random Walks and Discrete Potential Theory ( Cortona , 1997) 56-84. Cambridge Univ. Press, Cambridge. · Zbl 0958.05121
[13]	Benjamini, I. and Schramm, O. (1996). Percolation beyond \Bbb Z d , many questions and a few answers. Electron. Comm. Probab. 1 71-82 (electronic). · Zbl 0890.60091
[14]	Benjamini, I. and Schramm, O. (1998). Exceptional planes of percolation. Probab. Theory Related Fields 111 551-564. · Zbl 0910.60076 · doi:10.1007/s004400050177
[15]	Benjamini, I. and Schramm, O. (1999). Recent progress on percolation beyond \Bbb Z d . Microsoft Research. Available at .
[16]	Benjamini, I. and Schramm, O. (2001). Percolation in the hyperbolic plane. J. Amer. Math. Soc. 14 487-507 (electronic). · Zbl 1037.82018 · doi:10.1090/S0894-0347-00-00362-3
[17]	Berger, N. and Biskup, M. (2007). Quenched invariance principle for simple random walk on percolation clusters. Probab. Theory Related Fields 137 83-120. · Zbl 1107.60066 · doi:10.1007/s00440-006-0498-z
[18]	Bollobás, B. and Riordan, O. (2006). The critical probability for random Voronoi percolation in the plane is 1/2. Probab. Theory Related Fields 136 417-468. · Zbl 1100.60054 · doi:10.1007/s00440-005-0490-z
[19]	Bollobás, B. and Riordan, O. (2006). Percolation . Cambridge Univ. Press, New York. · Zbl 1118.60001
[20]	Broder, A. (1989). Genertaing random spanning trees. In 30 th Annual Symposium on the Foundations of Computer Science 442-447. IEEE, New York.
[21]	Burton, R. M. and Keane, M. (1989). Density and uniqueness in percolation. Comm. Math. Phys. 121 501-505. · Zbl 0662.60113 · doi:10.1007/BF01217735
[22]	Burton, R. M. and Keane, M. (1991). Topological and metric properties of infinite clusters in stationary two-dimensional site percolation. Israel J. Math. 76 299-316. · Zbl 0757.60102 · doi:10.1007/BF02773867
[23]	De Masi, A., Ferrari, P. A., Goldstein, S. and Wick, W. D. (1989). An invariance principle for reversible Markov processes. Applications to random motions in random environments. J. Stat. Phys. 55 787-855. · Zbl 0713.60041 · doi:10.1007/BF01041608
[24]	Doyle, P. G. and Snell, J. L. (1984). Random Walks and Electric Networks. Carus Mathematical Monographs 22 . Math. Assoc. America, Washington, DC. · Zbl 0583.60065
[25]	Gandolfi, A., Keane, M. S. and Newman, C. M. (1992). Uniqueness of the infinite component in a random graph with applications to percolation and spin glasses. Probab. Theory Related Fields 92 511-527. · Zbl 0767.60098 · doi:10.1007/BF01274266
[26]	Grimmett, G. (1999). Percolation , 2nd ed. Springer, Berlin. · Zbl 0926.60004
[27]	Grimmett, G. (2006). The Random-Cluster Model . Springer, Berlin. · Zbl 1122.60087
[28]	Grimmett, G. R., Kesten, H. and Zhang, Y. (1993). Random walk on the infinite cluster of the percolation model. Probab. Theory Related Fields 96 33-44. · Zbl 0791.60095 · doi:10.1007/BF01195881
[29]	Grimmett, G. R. and Newman, C. M. (1990). Percolation in \infty +1 dimensions. In Disorder in Physical Systems 167-190. Oxford Univ. Press, New York. · Zbl 0721.60121
[30]	Häggström, O. (1995). Random-cluster measures and uniform spanning trees. Stochastic Process. Appl. 59 267-275. · Zbl 0840.60089 · doi:10.1016/0304-4149(95)00042-6
[31]	Häggström, O. (1997). Infinite clusters in dependent automorphism invariant percolation on trees. Ann. Probab. 25 1423-1436. · Zbl 0895.60098 · doi:10.1214/aop/1024404518
[32]	Häggström, O. (2000). Markov random fields and percolation on general graphs. Adv. in Appl. Probab. 32 39-66. · Zbl 0988.60096 · doi:10.1239/aap/1013540021
[33]	Häggström, O. (2008). Oded Schramm 1961-2008. Svenska Matematikersamfundets Medlemsutskick 27-29. Available at . · Zbl 1231.60111
[34]	Häggström, O. and Jonasson, J. (2006). Uniqueness and non-uniqueness in percolation theory. Probab. Surv. 3 289-344 (electronic). · Zbl 1189.60175 · doi:10.1214/154957806000000096
[35]	Häggström, O. and Peres, Y. (1999). Monotonicity of uniqueness for percolation on Cayley graphs: All infinite clusters are born simultaneously. Probab. Theory Related Fields 113 273-285. · Zbl 0921.60091 · doi:10.1007/s004400050208
[36]	Hara, T. and Slade, G. (1994). Mean-field behaviour and the lace expansion. In Probability and Phase Transition ( Cambridge , 1993). NATO Advanced Science Institutes Series C : Mathematical and Physical Sciences 420 87-122. Kluwer, Dordrecht. · Zbl 0831.60107
[37]	Harris, T. E. (1960). A lower bound for the critical probability in a certain percolation process. Proc. Cambridge Philos. Soc. 56 13-20. · Zbl 0122.36403
[38]	Harrison, E. R. (1987). Darkness at Night : A Riddle of the Universe . Harvard Univ. Press, Cambridge, MA.
[39]	Kesten, H. (1959). Symmetric random walks on groups. Trans. Amer. Math. Soc. 92 336-354. · Zbl 0092.33503 · doi:10.2307/1993160
[40]	Kesten, H. (1959). Full Banach mean values on countable groups. Math. Scand. 7 146-156. · Zbl 0092.26704
[41]	Kesten, H. (1980). The critical probability of bond percolation on the square lattice equals \frac{1}{2} . Comm. Math. Phys. 74 41-59. · Zbl 0441.60010 · doi:10.1007/BF01197577
[42]	Kirchhoff, G. (1847). Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird. Ann. Phys. Chem. 72 497-508.
[43]	Lalley, S. P. (1998). Percolation on Fuchsian groups. Ann. Inst. H. Poincaré Probab. Statist. 34 151-177. · Zbl 0911.60084 · doi:10.1016/S0246-0203(98)80022-8
[44]	Lalley, S. P. (2001). Percolation clusters in hyperbolic tessellations. Geom. Funct. Anal. 11 971-1030. · Zbl 0997.60122 · doi:10.1007/s00039-001-8223-7
[45]	Lawler, G. F. (1991). Intersections of Random Walks . Birkhäuser, Boston, MA. · Zbl 1228.60004
[46]	Lawler, G. F., Schramm, O. and Werner, W. (2001). Values of Brownian intersection exponents. I. Half-plane exponents. Acta Math. 187 237-273. · Zbl 1005.60097 · doi:10.1007/BF02392618
[47]	Lawler, G. F., Schramm, O. and Werner, W. (2001). Values of Brownian intersection exponents. II. Plane exponents. Acta Math. 187 275-308. · Zbl 0993.60083 · doi:10.1007/BF02392619
[48]	Lawler, G. F., Schramm, O. and Werner, W. (2002). Values of Brownian intersection exponents. III. Two-sided exponents. Ann. Inst. H. Poincaré Probab. Statist. 38 109-123. · Zbl 1006.60075 · doi:10.1016/S0246-0203(01)01089-5
[49]	Lawler, G. F., Schramm, O. and Werner, W. (2002). Analyticity of intersection exponents for planar Brownian motion. Acta Math. 189 179-201. · Zbl 1024.60033 · doi:10.1007/BF02392842
[50]	Lyons, R. (1990). Random walks and percolation on trees. Ann. Probab. 18 931-958. · Zbl 0714.60089 · doi:10.1214/aop/1176990730
[51]	Lyons, R. (1992). Random walks, capacity and percolation on trees. Ann. Probab. 20 2043-2088. · Zbl 0766.60091 · doi:10.1214/aop/1176989540
[52]	Lyons, R. (1998). A bird’s-eye view of uniform spanning trees and forests. In Microsurveys in Discrete Probability ( Princeton , NJ , 1997). DIMACS Series in Discrete Mathematics and Theoretical Computer Science 41 135-162. Amer. Math. Soc., Providence, RI. · Zbl 0909.60016
[53]	Lyons, R. (2000). Phase transitions on nonamenable graphs. J. Math. Phys. 41 1099-1126. · Zbl 1034.82014 · doi:10.1063/1.533179
[54]	Lyons, R. (2008). Oded Schramm 1961-2008. IMS Bulletin 37 10-11.
[55]	Lyons, R., Peres, Y. and Schramm, O. (2006). Minimal spanning forests. Ann. Probab. 34 1665-1692. · Zbl 1142.60065 · doi:10.1214/009117906000000269
[56]	Lyons, R. and Schramm, O. (1999). Indistinguishability of percolation clusters. Ann. Probab. 27 1809-1836. · Zbl 0960.60013 · doi:10.1214/aop/1022677549
[57]	Lyons, R. and Schramm, O. (1999). Stationary measures for random walks in a random environment with random scenery. New York J. Math. 5 107-113 (electronic). · Zbl 0926.60021
[58]	Meester, R. and Roy, R. (1996). Continuum Percolation. Cambridge Tracts in Mathematics 119 . Cambridge Univ. Press, Cambridge. · Zbl 0858.60092
[59]	Memories of Oded Schramm. Available at .
[60]	Morris, B. (2003). The components of the wired spanning forest are recurrent. Probab. Theory Related Fields 125 259-265. · Zbl 1031.60035 · doi:10.1007/s00440-002-0236-0
[61]	Newman, C. M. and Schulman, L. S. (1981). Infinite clusters in percolation models. J. Stat. Phys. 26 613-628. · Zbl 0509.60095 · doi:10.1007/BF01011437
[62]	Newman, C. M. and Stein, D. L. (1996). Ground-state structure in a highly disordered spin-glass model. J. Stat. Phys. 82 1113-1132. · Zbl 1042.82568 · doi:10.1007/BF02179805
[63]	Pak, I. and Smirnova-Nagnibeda, T. (2000). On non-uniqueness of percolation on nonamenable Cayley graphs. C. R. Acad. Sci. Paris Sér. I Math. 330 495-500. · Zbl 0947.43003 · doi:10.1016/S0764-4442(00)00211-1
[64]	Pemantle, R. (1991). Choosing a spanning tree for the integer lattice uniformly. Ann. Probab. 19 1559-1574. · Zbl 0758.60010 · doi:10.1214/aop/1176990223
[65]	Peres, Y. (2000). Percolation on nonamenable products at the uniqueness threshold. Ann. Inst. H. Poincaré Probab. Statist. 36 395-406. · Zbl 0965.60094 · doi:10.1016/S0246-0203(00)00130-8
[66]	Peres, Y., Pete, G. and Scolnicov, A. (2006). Critical percolation on certain nonunimodular graphs. New York J. Math. 12 1-18 (electronic). · Zbl 1103.60079
[67]	Russo, L. (1981). On the critical percolation probabilities. Z. Wahrsch. Verw. Gebiete 56 229-237. · Zbl 0457.60084 · doi:10.1007/BF00535742
[68]	Schonmann, R. H. (1999). Stability of infinite clusters in supercritical percolation. Probab. Theory Related Fields 113 287-300. · Zbl 0921.60092 · doi:10.1007/s004400050209
[69]	Schonmann, R. H. (1999). Percolation in \infty +1 dimensions at the uniqueness threshold. In Perplexing Problems in Probability. Progress in Probability 44 53-67. Birkhäuser, Boston, MA. · Zbl 0948.60099
[70]	Schramm, O. (2000). Scaling limits of loop-erased random walks and uniform spanning trees. Israel J. Math. 118 221-288. · Zbl 0968.60093 · doi:10.1007/BF02803524
[71]	Schramm, O. (2001). A percolation formula. Electron. Comm. Probab. 6 115-120 (electronic). · Zbl 1008.60100
[72]	Schramm, O. (2008). Hyperfinite graph limits. Electron. Res. Announc. Math. Sci. 15 17-23. · Zbl 1140.60008
[73]	Schramm, O. and Steif, J. E. (2010). Quantitative noise sensitivity and exceptional times for percolation. Ann. of Math. (2) 171 619-672. · Zbl 1213.60160 · doi:10.4007/annals.2010.171.619
[74]	Soardi, P. M. (1994). Potential Theory on Infinite Networks. Lecture Notes in Math. 1590 . Springer, Berlin. · Zbl 0818.31001 · doi:10.1007/BFb0073995
[75]	Thomassen, C. (1989). Transient random walks, harmonic functions, and electrical currents in infinite electrical networks. Mat-Report 1989-07, Technical Univ. Denmark.
[76]	Timár, Á. (2006). Percolation on nonunimodular transitive graphs. Ann. Probab. 34 2344-2364. · Zbl 1114.60083 · doi:10.1214/009117906000000494
[77]	Trofimov, V. I. (1985). Groups of automorphisms of graphs as topological groups. Mat. Zametki 38 378-385, 476. · Zbl 0596.05033 · doi:10.1007/BF01163706
[78]	Tykesson, J. (2007). The number of unbounded components in the Poisson Boolean model of continuum percolation in hyperbolic space. Electron. J. Probab. 12 1379-1401 (electronic). · Zbl 1136.82010
[79]	Werner, W. (2009). Oded Schramm (1961-2008). EMS Newsletter March 9-13. · Zbl 1167.01333
[80]	Wilson, D. B. (1996). Generating random spanning trees more quickly than the cover time. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing ( Philadelphia , PA , 1996) 296-303. ACM, New York. · Zbl 0946.60070
[81]	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