Percolation in an ultrametric space

Donald A. Dawson (Carleton University)
Luis G. Gorostiza (CINVESTAV, Mexico City)

Abstract


We study percolation in the hierarchical lattice of order N where the probability of connection between two points separated by distance k is of the form ck/Nk(1+δ), δ>-1. Since the distance is an ultrametric, there are significant differences with percolation in the Euclidean lattice. We consider three regimes: δ<1, where percolation occurs, δ>1, where it does not occur and δ=1 which is the critical case corresponding to the phase transition. In the critical case we use an approach in the spirit of the renormalization group method of statistical physics, and connectivity results of Erdős-Rényi random graphs play a key role. We find sufficient conditions on ck such that percolation occurs, or that it does not occur. An intermediate situation called pre-percolation, which is necessary for percolation, is also considered. In the cases of percolation we prove uniqueness of the constructed percolation clusters. In a previous paper we studied percolation in the N→∞ limit (mean field percolation), which provided a simplification that allowed finding a necessary and sufficient condition for percolation. For fixed N there are open questions, in particular regarding the behaviour at the critical values of parameters in the definition of ck. Those questions suggest the need to study ultrametric random graphs.


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

Pages: 1-26

Publication Date: January 23, 2013

DOI: 10.1214/EJP.v18-1789

References

  • Aizenman, M.; Newman, C. M. Discontinuity of the percolation density in one-dimensional $1/\vert x- y\vert ^ 2$ percolation models. Comm. Math. Phys. 107 (1986), no. 4, 611--647. MR0868738
  • Barabási, Albert-László; Albert, Réka. Emergence of scaling in random networks. Science 286 (1999), no. 5439, 509--512. MR2091634
  • A.L. Barabási and E. Ravaz (2003). Hierarchical organization in complex networks, Phys. Rev. E. 67, 026112.
  • Benjamini, Itai; Berger, Noam. The diameter of long-range percolation clusters on finite cycles. Random Structures Algorithms 19 (2001), no. 2, 102--111. MR1848786
  • Benjamini, I.; Lyons, R.; Peres, Y.; Schramm, O. Group-invariant percolation on graphs. Geom. Funct. Anal. 9 (1999), no. 1, 29--66. MR1675890
  • Benjamini, Itai; Schramm, Oded. Percolation beyond $Z^ d$, many questions and a few answers. Electron. Comm. Probab. 1 (1996), no. 8, 71--82 (electronic). MR1423907
  • Berger, Noam. Transience, recurrence and critical behavior for long-range percolation. Comm. Math. Phys. 226 (2002), no. 3, 531--558. MR1896880
  • Biskup, Marek. On the scaling of the chemical distance in long-range percolation models. Ann. Probab. 32 (2004), no. 4, 2938--2977. MR2094435
  • Biskup, Marek. Graph diameter in long-range percolation. Random Structures Algorithms 39 (2011), no. 2, 210--227. MR2850269
  • Bollobás, Béla. Random graphs. Second edition. Cambridge Studies in Advanced Mathematics, 73. Cambridge University Press, Cambridge, 2001. xviii+498 pp. ISBN: 0-521-80920-7; 0-521-79722-5 MR1864966
  • Bollobás, Béla; Janson, Svante; Riordan, Oliver. The phase transition in inhomogeneous random graphs. Random Structures Algorithms 31 (2007), no. 1, 3--122. MR2337396
  • Bollobás, Béla; Riordan, Oliver. Percolation. Cambridge University Press, New York, 2006. x+323 pp. ISBN: 978-0-521-87232-4; 0-521-87232-4 MR2283880
  • Brydges, David; Evans, Steven N.; Imbrie, John Z. Self-avoiding walk on a hierarchical lattice in four dimensions. Ann. Probab. 20 (1992), no. 1, 82--124. MR1143413
  • Collet, Pierre; Eckmann, Jean-Pierre. A renormalization group analysis of the hierarchical model in statistical mechanics. Lecture Notes in Physics, Vol. 74. Springer-Verlag, Berlin-New York, 1978. i+199 pp. ISBN: 3-540-08670-6 MR0503070
  • Coppersmith, Don; Gamarnik, David; Sviridenko, Maxim. The diameter of a long-range percolation graph. Random Structures Algorithms 21 (2002), no. 1, 1--13. MR1913075
  • Dawson, D. A.; Gorostiza, L. G. Percolation in a hierarchical random graph. Commun. Stoch. Anal. 1 (2007), no. 1, 29--47. MR2404371
  • Dawson, D. A.; Gorostiza, L. G.; Wakolbinger, A. Degrees of transience and recurrence and hierarchical random walks. Potential Anal. 22 (2005), no. 4, 305--350. MR2135263
  • Dawson, D. A.; Gorostiza, L. G.; Wakolbinger, A. Hierarchical random walks. Asymptotic methods in stochastics, 173--193, Fields Inst. Commun., 44, Amer. Math. Soc., Providence, RI, 2004. MR2106854
  • Durrett, Rick. Random graph dynamics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2007. x+212 pp. ISBN: 978-0-521-86656-9; 0-521-86656-1 MR2271734
  • Dyson, Freeman J. Existence of a phase-transition in a one-dimensional Ising ferromagnet. Comm. Math. Phys. 12 (1969), no. 2, 91--107. MR0436850
  • Gandolfi, A.; Keane, M. S.; Newman, C. M. Uniqueness of the infinite component in a random graph with applications to percolation and spin glasses. Probab. Theory Related Fields 92 (1992), no. 4, 511--527. MR1169017
  • Grimmett, Geoffrey. Percolation. Second edition. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 321. Springer-Verlag, Berlin, 1999. xiv+444 pp. ISBN: 3-540-64902-6 MR1707339
  • Janson, Svante; ?uczak, Tomasz; Rucinski, Andrzej. Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000. xii+333 pp. ISBN: 0-471-17541-2 MR1782847
  • J. Kleinberg (2001). Small-world phenomena and the dynamics of information, in Advances in Neural Information Processing Systems (NIPS) 14, 431-438.
  • Kleinberg, Jon. Complex networks and decentralized search algorithms. International Congress of Mathematicians. Vol. III, 1019--1044, Eur. Math. Soc., Zürich, 2006. MR2275717
  • S. Koval, R. Meester and P. Trapman (2010). Long-range percolation on a hierarchical lattice, arXiv: PR1004, 1251.
  • Newman, C. M.; Schulman, L. S. One-dimensional $1/\vert j-i\vert ^ s$ percolation models: the existence of a transition for $s\leq 2$. Comm. Math. Phys. 104 (1986), no. 4, 547--571. MR0841669
  • Pak, Igor; Smirnova-Nagnibeda, Tatiana. On non-uniqueness of percolation on nonamenable Cayley graphs. C. R. Acad. Sci. Paris Sér. I Math. 330 (2000), no. 6, 495--500. MR1756965
  • Rammal, R.; Toulouse, G.; Virasoro, M. A. Ultrametricity for physicists. Rev. Modern Phys. 58 (1986), no. 3, 765--788. MR0854445
  • O. Sandberg (2008). Phase transitions in partially structured random graphs, arXiv: PR0804.0137. 1
  • Sawyer, Stanley; Felsenstein, Joseph. Isolation by distance in a hierarchically clustered population. J. Appl. Probab. 20 (1983), no. 1, 1--10. MR0688075
  • Schikhof, W. H. Ultrametric calculus. An introduction to $p$-adic analysis. Cambridge Studies in Advanced Mathematics, 4. Cambridge University Press, Cambridge, 1984. viii+306 pp. ISBN: 0-521-24234-7 MR0791759
  • Schulman, L. S. Long range percolation in one dimension. J. Phys. A 16 (1983), no. 17, L639--L641. MR0723249
  • Sina?, Ya. G. Theory of phase transitions: rigorous results. Translated from the Russian by J. Fritz, A. Krámli, P. Major and D. Szász. International Series in Natural Philosophy, 108. Pergamon Press, Oxford-Elmsford, N.Y., 1982. viii+150 pp. ISBN: 0-08-026469-7 MR0691854
  • Stauffer, Dietrich. Introduction to percolation theory. Taylor & Francis, Ltd., London, 1985. viii+124 pp. ISBN: 0-85066-315-6 MR0849782
  • Trapman, Pieter. The growth of the infinite long-range percolation cluster. Ann. Probab. 38 (2010), no. 4, 1583--1608. MR2663638
  • Turova, Tatyana S.; Vallier, Thomas. Merging percolation on $\Bbb Z^ d$ and classical random graphs: phase transition. Random Structures Algorithms 36 (2010), no. 2, 185--217. MR2583060
Bookmark and Share


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