</script> This paper is an up-to-date introduction to the problem of uniqueness versus non-uniqueness of infinite clusters for percolation on (mathbb{Z}^d) and, more generally, on transitive graphs. For iid percolation on (mathbb{Z}^d), uniqueness of the infinite cluster is a classical result, while on certain other transitive graphs uniqueness may fail. Key properties of the graphs in this context turn out to be amenability and nonamenability. The same problem is considered for certain dependent percolation models &ndash; most prominently the Fortuin&ndash;Kasteleyn random-cluster model &ndash; and in situations where the standard connectivity notion is replaced by entanglement or rigidity. So-called simultaneous uniqueness in couplings of percolation processes is also considered. Some of the main results are proved in detail, while for others the proofs are merely sketched, and for yet others they are omitted. Several open problems are discussed.">
Home | Current | Past volumes | About | Login | Notify | Contact | Search
 Probability Surveys > Vol. 3 (2006) open journal systems 


Uniqueness and non-uniqueness in percolation theory

Olle Haggstrom, Chalmers University of Technology
Johan Jonasson, Chalmers University of Technology


Abstract
This paper is an up-to-date introduction to the problem of uniqueness versus non-uniqueness of infinite clusters for percolation on \(\mathbb{Z}^d\) and, more generally, on transitive graphs. For iid percolation on \(\mathbb{Z}^d\), uniqueness of the infinite cluster is a classical result, while on certain other transitive graphs uniqueness may fail. Key properties of the graphs in this context turn out to be amenability and nonamenability. The same problem is considered for certain dependent percolation models – most prominently the Fortuin–Kasteleyn random-cluster model – and in situations where the standard connectivity notion is replaced by entanglement or rigidity. So-called simultaneous uniqueness in couplings of percolation processes is also considered. Some of the main results are proved in detail, while for others the proofs are merely sketched, and for yet others they are omitted. Several open problems are discussed.

AMS 2000 subject classifications: Primary 60K35, 82B43.

Keywords: percolation, uniqueness of the infinite cluster, transitive graphs, amenability.

Creative Common LOGO

Full Text: PDF


Haggstrom, Olle, Jonasson, Johan, Uniqueness and non-uniqueness in percolation theory, Probability Surveys, 3, (2006), 289-344 (electronic).

References

[1]   Aizenman, M., Chayes, J.T., Chayes, L. and Newman, C.M. (1988) Discontinuity of the magnetization in one-dimensional 1x-y2 Ising and Potts models, J. Statist. Phys. 50, 1–40. MR0939480

[2]   Aizenman, M. and Grimmett, G.R. (1991) Strict monotonicity for critical points in percolation and ferromagnetic models, J. Statist. Phys. 63, 817–835. MR1116036

[3]   Aizenman, M., Kesten, H. and Newman, C.M. (1987) Uniqueness of the infinite cluster and continuity of connectivity functions for short- and long-range precolation, Comm. Math. Phys. 111, 505–532. MR0901151

[4]   Alexander, K.S. (1995a) Simultaneous uniqueness of infinite clusters in stationary random labeled graphs, Comm. Math. Phys. 168, 39–55. MR1324390

[5]   Alexander, K.S. (1995b) Percolation and minimal spanning forests in infinite graphs, Ann. Probab. 23, 87–104. MR1330762

[6]   Babson, E. and Benjamini, I. (1999) Cut sets and normed cohomology with application to percolation, Proc. Amer. Math. Soc. 127, 589–597. MR1622785

[7]   Barsky, D.J., Grimmett, G.R. and Newman, C.M (1991) Percolation in half-spaces: equality of critical densities and continuity of the percolation probability, Probab. Th. Rel. Fields 90, 111–148. MR1124831

[8]   Benjamini, I., Kesten, H., Peres, Y. and Schramm, O. (2004) Geometry of the uniform spanning forest: transitions in dimensions 4, 8, 12,..., Ann. Math. 160, 465–491. MR2123930

[9]   Benjamini, I., Lyons, R., Peres, Y. and Schramm, O. (1999a) Critical percolation on any nonamenable graph has no infinite clusters, Ann. Probab. 27, 1347–1356. MR1733151

[10]   Benjamini, I., Lyons, R., Peres Y. and Schramm, O. (1999b) Group-invariant percolation on graphs, Geom. Funct. Analysis 9, 29–66. MR1675890

[11]   Benjamini, I., Lyons, R., Peres Y. and Schramm, O. (2001) Uniform spanning forests, Ann. Probab. 29, 1–65. MR1825141

[12]   Benjamini, I. and Schramm, O. (1996) Percolation beyond d, many questions and a few answers, Electr. Comm. Probab. 1, 71–82. MR1423907

[13]   Benjamini, I. and Schramm, O. (2001) Percolation in the hyperbolic plane, J. Amer. Math. Soc. 14, 487–507. MR1815220

[14]   van den Berg, J. and Steif, J.E. (1994) Percolation and the hard-core lattice gas model, Stoch. Proc. Appl. 49, 179–197. MR1260188

[15]   Bollobás, B. (1998) Modern Graph Theory, Springer, New York. MR1633290

[16]   Borgs, C., Chayes, J.T., van der Hofstad, R., Slade, G., and Spencer, J. (2005) Random subgraphs of finite graphs: I. The scaling window under the triangle condition, Random Structures Algorithms, to appear. MR2155704

[17]   Borgs, C., Chayes, J.T., Kesten, H., and Spencer, J. (2001) The birth of the infinite cluster: finite-size scaling in percolation. Comm. Math. Phys. 224, 153–204. MR1868996

[18]   Broadbent, S.R. and Hammersley, J.M. (1957) Percolation processes I: Crystals and mazes, Proc. Cambridge. Phil. Soc. 53, 629–641. MR0091567

[19]   Burton, R.M. and Keane, M.S. (1989) Density and uniqueness in percolation, Comm. Math. Phys. 121, 501–505. MR0990777

[20]   Burton, R.M. and Keane, M.S. (1991) Topological and metric properties of infinite clusters in stationary two-dimensional site percolation, Israel J. Math. 76, 299–316. MR1177347

[21]   Campanino, M. and Russo, L. (1985) An upper bound on the critical percolation probability for the three-dimensional cubic lattice, Ann. Probab. 13, 478–491. MR0781418

[22]   Chaboud, T. and Kenyon, C. (1996) Planar Cayley graphs with regular dual, Internat. J. Algebra Comput. 6, 553–561. MR1419130

[23]   Chayes, J.T., Chayes, L. and Newman, C.M. (1985) The stochastic geometry of invasion percolation, Comm. Math. Phys. 101, 383–407. MR0815191

[24]   Chayes, L. (1995) Aspects of the fractal percolation process, in Fractal geometry and stochastics (Finsterbergen, 1994), pp 113–143, Progr. Probab. 37, Birkhäuser, Basel. MR1391973

[25]   Chayes, L. (1996) Percolation and ferromagnetism on 2: the q-state Potts cases, Stoch. Proc. Appl. 65, 209–216. MR1425356

[26]   Coniglio, A., Nappi, C.R., Peruggi, F. and Russo, L. (1976) Percolation and phase transitions in the Ising model, Comm. Math. Phys. 51, 315–323. MR0426745

[27]   Durrett, R. (1991) Probability: Theory and Examples, Wadsworth & Brooks/Cole, Pacific Grove. MR1068527

[28]   Edwards, R.G. and Sokal, A.D. (1988) Generalization of the Fortuin–Kasteleyn–Swendsen–Wang representation and Monte Carlo algorithm, Phys. Rev. D 38, 2009–2012. MR0965465

[29]   van Enter, A.C.D. (1987) Proof of Straley’s argument for bootstrap percolation, J. Statist. Phys. 48, 943–945. MR0914911

[30]   Erdʺo   s, P. and Rényi, A. (1959) On random graphs, Publicationes Mathematicae Debrecen 6, 290–297. MR0120167

[31]   Fortuin, C.M. and Kasteleyn, P.W. (1972) On the random-cluster model. I. Introduction and relation to other models, Physica 57, 536–564. MR0359655

[32]   Gandolfi, A., Keane, M. and Newman, C.M. (1992) Uniqueness of the infinite component in a random graph with applications to percolation and spin glasses, Probab. Th. Rel. Fields 92, 511–527. MR1169017

[33]   Gandolfi, A., Keane, M. and Russo, L. (1988) On the uniqueness of the infinite occupied cluster in dependent two-dimensional site percolation Ann. Probab. 16, 1147–1157. MR0942759

[34]   Georgii, H.-O., Häggström, O. and Maes, C. (2001) The random geometry of equilibrium phases, Phase Transitions and Critical Phenomena, Volume 18 (C. Domb and J.L. Lebowitz, eds), pp 1-142, Academic Press, London. MR2014386

[35]   Grimmett, G.R. (1994) Percolative problems, Probability and Phase Transition (ed. G.R. Grimmett), Kluwer, Dordrecht, 69–86. MR1283176

[36]   Grimmett, G.R. (1995) The stochastic random-cluster process, and the uniqueness of random-cluster measures, Ann. Probab. 23, 1461–1510. MR1379156

[37]   Grimmett, G.R. (1999) Percolation, Springer, Berlin. MR1707339

[38]   Grimmett, G.R. (2003) The random-cluster model, in Probability on Discrete Structures, vol 110 of Encyclopedia of Mathematical Sciences, pp 73–123, Springer, Berlin. MR2023651

[39]   Grimmett, G.R. (2005) Uniqueness and multiplicity of infinite clusters, in Dynamics and Stochastics: Festschrift in Honor of Michael Keane, IMS Lecture Notes-Monograph Series, pp 24–36.

[40]   Grimmett, G.R. (2006) The Random-Cluster Model, Springer, Berlin. MR2243761

[41]   Grimmett, G.R. and Holroyd, A.E. (2000) Entanglement in percolation, Proc. London Math. Soc. 81, 485–512. MR1770617

[42]   Grimmett, G.R. and Newman, C.M. (1990) Percolation in + 1 dimensions, In Disorder in Physical Systems (G.R. Grimmett and D.J.A. Welsh, eds), pp. 167–190, Oxford University Press, New York. MR1064560

[43]   Grossman, J.W. (2002) The evolution of the mathematical research collaboration graph, Congressus Numerantium 158, 201–212. MR1985159

[44]   Grossman, J.W. (2003) The Erdʺo       s Number Project, http://www.oakland.edu/enp/

[45]   Häggström, O. (1995) Random-cluster measures and uniform spanning trees, Stoch. Proc. Appl. 59, 267–275. MR1357655

[46]   Häggström, O. (1996) The random-cluster model on a homogeneous tree, Probab. Th. Rel. Fields 104, 231–253. MR1373377

[47]   Häggström, O. (1997a) Infinite clusters in dependent automorphism invariant percolation on trees, Ann. Probab. 25, 1423–1436. MR1457624

[48]   Häggström, O. (1997b) Ergodicity of the hard-core model on Z2 with parity-dependent activities, Ark. Mat. 35, 171–184. MR1443040

[49]   Häggström, O. (1999) Positive correlations in the fuzzy Potts model, Ann. Appl. Probab. 9, 1149–1159. MR1728557

[50]   Häggström, O. (2001a) Uniqueness of the infinite entangled component in three-dimensional bond percolation, Ann. Probab. 29, 127–136. MR1825145

[51]   Häggström, O. (2001b) Uniqueness in two-dimensional rigidity percolation, Math. Proc. Cambridge Phil. Soc. 130, 175–188. MR1797779

[52]   Häggström, O. (2003) Uniqueness of infinite rigid components in percolation models: the case of nonplanar lattices, Probab. Th. Rel. Fields 127, 513–534. MR2021194

[53]   Häggström, O. and Jonasson, J. (1999) Phase transition in the random triangle model, J. Appl. Probab. 36, 1101–1115. MR1742153

[54]   Häggström, O., Jonasson, J. and Lyons, R. (2002) Explicit isoperimetric constants and phase transitions in the random-cluster model, Ann. Probab. 30, 443–473. MR1894115

[55]   Häggström, O. and Pemantle, R. (2000) Absence of mutual unbounded growth for almost all parameter values in the two-type Richardson model, Stoch. Proc. Appl. 90, 207–222. MR1794536

[56]   Häggström, O. and Peres, Y. (1999) Monotonicity of uniqueness for percolation on transitive graphs: all infinite clusters are born simultaneously, Probab. Th. Rel. Fields 113, 273–285. MR1676835

[57]   Häggström, O., Peres, Y., and Schonmann, R.H. (1999) Percolation on transitive graphs as a coalescent process: relentless merging followed by simultaneous uniqueness, in Perplexing Probability Problems: Papers in Honor of Harry Kesten (M. Bramson and R. Durrett, eds), pp. 53–67, Birkhäuser, Boston. MR1703125

[58]   Häggström, O., Peres, Y., and Steif, J. (1997) Dynamical percolation, Ann. Inst. H. Poincaré, Probab. Stat. 33, 497–528. MR1465800

[59]   Hallberg, P. (2004) Gibbs Measures and Phase Transitions in Potts and Beach Models, Ph.D. thesis, Royal Institute of Technology, Stockholm,
http://media.lib.kth.se/dissengrefhit.asp?dissnr=3837

[60]   Hammersley, J.M. (1961) Comparison of atom and bond percolation processes, J. Math. Phys. 2, 728–733. MR0130722

[61]   Hara, T. and Slade, G. (1994) Mean-field behaviour and the lace expansion, in Probability and Phase Transition (G. R. Grimmett, ed.), pp. 87–122, Kluwer Acad. Publ., Dordrecht. MR1283177

[62]   Harris, T.E. (1960) A lower bound for the critical probability in a certain percolation process, Proc. Cambridge Phil. Soc. 56, 13–20. MR0115221

[63]   Higuchi, Y. (1982) Coexistence of the infinite *-clusters: a remark on the square lattice site percolation, Z. Wahrsch. Verw. Gebiete 61, 75–81. MR0671244

[64]   Holroyd, A.E. (1998) Existence and uniqueness of infinite components in generic rigidity percolation, Ann. Appl. Probab. 8, 944–973. MR1627815

[65]   Holroyd, A.E. (2000) Existence of a phase transition for entanglement percolation, Math. Proc. Cambridge Phil. Soc. 129, 231–251. MR1765912

[66]   Holroyd, A.E. (2001) Rigidity percolation and boundary conditions, Ann. Appl. Probab. 11, 1063–1078. MR1878290

[67]   Holroyd, A.E. (2002) Entanglement and rigidity in percolation models, In and Out of Equilibrium (Mambucaba, 2000), pp 299–307, Progr. Probab. 51, Birkhäuser, Boston. MR1901959

[68]   Jacobs, D.J. and Thorpe, M.F. (1995) Generic rigidity percolation: the pebble game, Phys. Rev. Lett 75, 4051–4054.

[69]   Jacobs, D.J. and Thorpe, M.F. (1996) Generic rigidity percolation in two dimensions, Phys. Rev. E 53, 3682–2693.

[70]   Janson, S., Łuczak, T. and Rucinski, A. (2000) Random Graphs, Wiley, New York. MR1782847

[71]   Jonasson, J. (1999) The random cluster model on a general graph and a phase transition characterization of nonamenability, Stoch. Proc. Appl. 79, 335–354. MR1671859

[72]   Jonasson, J. and Steif, J. (1999) Amenability and phase transition in the Ising model, J. Theor. Prob. 12, 549–559. MR1684757

[73]   Kantor, T. and Hassold, G.N. (1988) Topological entanglements in the percolation problems, Phys. Rev. Lett. 60, 1457–1460. MR0935098

[74]   Kesten, H. (1959) Full Banach mean values on countable groups, Math. Scand. 7, 146–156. MR0112053

[75]   Kesten, H. (1959) Symmetric random walks on groups, Trans. Amer. Math. Soc. 92, 336–354. MR0109367

[76]   Kesten, H. (1980) The critical probability of bond percolation on the square lattice equals 1
2, Comm. Math. Phys. 74, 41–59. MR0575895

[77]   Kesten, H. (1982) Percolation Theory for Mathematicians, Birkhäuser, Boston. MR0692943

[78]   Lalley, S. (1998) Percolation on Fuchsian groups, Ann. Inst. H. Poincaré, Probab. Stat. 34, 151–178. MR1614583

[79]   Lyons, R (2000) Phase transitions on nonamenable graphs, J. Math. Phys. 41, 1099–1126. MR1757952

[80]   Lyons, R. and Peres, Y. (2005) Probability on Trees and Networks, Cambridge University Press, to appear, http://mypage.iu.edu/~  rdlyons/prbtree/prbtree.html

[81]   Lyons, R., Peres, Y. and Schramm, O. (2006) Minimal spanning forests, Ann. Probab., to appear.

[82]   Lyons, R. and Schramm, O. (1999) Indistinguishability of percolation clusters, Ann. Probab. 27, 1809–1836. MR1742889

[83]   Meester, R. (1994) Uniqueness in percolation theory, Statist. Neerl. 48, 237–252. MR1310339

[84]   Meester, R. and Roy, R. (1996) Continuum Percolation, Cambridge University Press. MR1409145

[85]   Mohar, B. (1988) Isoperimetric inequalities, growth and the spectrum of graphs, Lin. Alg. Appl. 103, 119–131. MR0943998

[86]   Newman, C.M. and Schulman, L.S. (1981) Infinite clusters in percolation models, J. Statist. Phys. 26, 613–628. MR0648202

[87]   Newman, C.M. and Stein, D.L. (1996) Ground-state structure in a highly disordered spin-glass model, J. Statist. Phys. 82, 1113–1132. MR1372437

[88]   Pak, I. and Smirnova-Nagnibeda, T. (2000) Uniqueness of percolation on nonamenable Cayley graphs, Comptes Rendus Acad. Sci. Paris, Ser. I Math. 330, 495–500. MR1756965

[89]   Pemantle, R. (1991) Choosing a spanning tree for the integer lattice uniformly, Ann. Probab. 19, 1559–1574. MR1127715

[90]   Peres, Y. (2000) Percolation on nonamenable products at the uniqueness threshold, Ann. Inst. H. Poincaré, Probab. Stat. 36, 395–406. MR1770624

[91]   Peres, Y., Pete, G. and Scolnicov, A. (2006) Critical percolation on certain nonunimodular graphs, New York J. Math. 12, 1–18. MR2217160

[92]   Peres, Y. and Steif, J.E. (1998) The number of infinite clusters in dynamical percolation, Probab. Th. Rel. Fields 111, 141–165. MR1626782

[93]   Pfister, C.-E. and Vande Velde, K. (1995) Almost sure quasilocality in the random cluster model, J. Statist. Phys. 79, 765–774. MR1327908

[94]   Schonmann, R.H. (1999) Percolation in + 1 dimensions at the uniqueness threshold, in Perplexing Probability Problems: Papers in Honor of Harry Kesten (M. Bramson and R. Durrett, ed.), pp. 53–67, Birkhäuser, Boston. MR1703124

[95]   Schonmann, R.H. (1999) Stability of infinite clusters in supercritical percolation, Probab. Th. Rel. Fields 113, 287–300. MR1676831

[96]   Schramm, O. and Steif, J.E. (2005) Quantitative noise sensitivity and exceptional times for percolation, preprint.

[97]   Sheffield, S. (2005) Random surfaces, Astrisque 304, vi+175 pp. MR2251117

[98]   Stacey, A.M. (1996) The existence of an intermediate phase for the contact process on trees, Ann. Probab. 24, 1711–1726. MR1415226

[99]   Timár, A. (2006a) Cutsets in infinite graphs, Comb. Probab. Computing 16, 1–8.

[100]   Timár, A. (2006b) Percolation on nonunimodular graphs, Ann. Probab., to appear.

[101]   Timár, A. (2006c) Neighboring clusters in Bernoulli percolation,Ann. Probab., to appear.

[102]   Trofimov, V.I. (1985) Automorphism groups of graphs as topological groups, Math. Notes 38, 717–720. MR0811571

[103]   Wierman, J.C. (1981) Bond percolation on honeycomb and triangular lattices, Avd. Appl. Probab. 13, 298–313. MR0612205

[104]   Zhang, Y. (1988) Unpublished, although see Grimmett [37, pp. 289–291].




Home | Current | Past volumes | About | Login | Notify | Contact | Search

Probability Surveys. ISSN: 1549-5787