Percolation threshold

From Wikipedia, the free encyclopedia

Percolation threshold is a mathematical term related to percolation theory, which is the formation of long-range connectivity in random systems. In engineering and coffee making, percolation is the slow flow of fluids through porous media, but in the mathematics and physics worlds it generally refers to simplified lattice models of random systems, and the nature of the connectivity on them. The percolation threshold is the critical value of the occupation probability p, or more generally a critical surface for a group of parameters p1, p2, ..., such that infinite connectivity (percolation) first occurs.

Contents

[edit] Percolation models

The most common percolation model is to take a regular lattice, like a square lattice, and make it into a random network by randomly "occupying" sites (vertices) or bonds (edges) with a statistically independent probability p. At a critical threshold pc, long-range connectivity first appears, and this is called the percolation threshold. More general systems have several probabilities p1, p2, etc., and the transition is characterized by a critical surface or manifold. One can also consider continuum systems, such as overlapping disks and spheres placed randomly, or the negative space (Swiss-cheese models).

In the systems described so far, it has been assumed that the occupation of a site or bond is completely random -- this is the so-called Bernoulli percolation. For a continuum system, random occupancy corresponds to the points being placed by a Poisson process. Further variations involve correlated percolation, such as percolation clusters related to Ising and Potts models of ferromagnets, in which the bonds are put down by the Fortuin-Kasteleyn method. [1] In bootstrap or k-sat percolation, sites and/or bonds are first occupied and then successively culled from a system if a site does not have at least k neighbors. Another important model of percolation, in a different universality class altogether, is directed percolation, where connectivity along a bond depends upon the direction of the flow.

Over the last several decades, a tremendous amount of work has gone into finding exact and approximate values of the percolation thresholds for a variety of these systems. Exact thresholds are only known for certain two-dimensional lattices that can be broken up into a self-dual array, such that under a triangle-triangle transformation, the system remains the same. Studies using numerical methods have led to numerous improvements in algorithms and several theoretical discoveries.

The purpose of this page is to gather in one place the most up-to-date precise values of percolation thresholds and critical surfaces, including all the exact results that are known.

The notation such as (4,82) comes from Grünbaum and Shepard, [2] and indicates that around a given vertex, going in the clockwise direction, one encounters first a square and then two octagons. Besides the eleven Archimedean lattices composed of regular polygons with every site equivalent, many other more complicated lattices with sites of different classes have been studied.

[edit] Thresholds on 2d regular and Archimedean lattices


Lattice z Site Percolation Threshold Bond Percolation Threshold
(3, 122 ) 3 0.807900764... = (1 - 2 sin (π/18))1/2 [3] 0.74042195(80)[4]
(4, 6, 12) 3 0.747806(4) [3] 0.69373383(72)[4]
honeycomb (63) 3 0.697043(3)[3] {\scriptstyle 0.652703645\dots = 1 - 2 \, \sin (\pi/18), 3 p^2 - p^3= 1 } [5]
(4, 82) 4 0.729724(3) [3] 0.67680232(63)[4]
kagomé (3, 6, 3, 6) 4 0.652703645... = 1 - 2 sin(π/18) [5] 0.5244053(3) [6]
(3, 4, 6, 4) 4 0.621819(3) [3] 0.52483258(53)[4]
square (44) 4 0.59274621(13) [7] 0.59274603(9) [8] 1/2
(34,6 ) 5 0.579498(3) [3] 0.43430621(50)[4]
(32, 4, 3, 4 ) 5 0.550806(3) [3] 0.41413743(46)[4]
(33, 42) 5 0.550213(3) [3] 0.41964191(43) [4]
triangular (36) 6 1/2 0.347296355... = 2 sin (π/18), 3p − p3 = 1 [5]

Note: sometimes "hexagonal" is used in place of honeycomb, although in some fields, a triangular lattice is also called "hexagonal" (as in hexagonal lattice). z = coordination number.

[edit] 2-Uniform Lattices

Top 3 Lattices: (1/2)(36)+(1/2)(34,6) (1/4)(36)+(3/4)(34,6) (1/7)(36)+(6/7)(32,4,12)
Bottom 3 Lattices: (1/7)(36)+(6/7)(32,62) (1/2)(33)+(1/2)(42;3,4,6,4) (1/2)(34,6)+(1/2)(32,62)

20 2 uniform lattices

[2]
Top 2 Lattices: (2/3)(3,42,6)+(1/3)(3,4,6,4) (1/2)(32,4,3,4)+(1/2)(3,4,6,4)
Bottom 2 Lattices: (1/2)(3,4,3,12)+(1/2)(3,122) (1/3)(3,4,6,4)+(2/3)(4,6,12)

20 2 uniform lattices

[2]
Top 4 Lattices: (2/3)(33,42)+(1/3)(44) (1/2)(33,42)+(1/2)(44) (1/3)(36)+(2/3)(33,42) (1/2)(36)+(1/2)(33,42)
Bottom 3 Lattices: (4/5)(3,42,6)+(1/5)(3,6,3,6) (4/5)(3,42,6)+(1/5)(3,6,3,6)* (2/3)(32,62)+(1/3)(3,6,3,6)

20 2 uniform lattices

[2]
Top 2 Lattices: (1/7)(36)+(6/7)(32,4,3,4) (1/3)(33,42)+(2/3)(32,4,3,4)
Bottom Lattice: (1/2)(33,42)+(1/2) (32,4,3,4)

20 2 uniform lattices

[2]

Lattice z, z Site Percolation Threshold Bond Percolation Threshold
(1/2)(3,4,3,12) + (1/2)(3, 122) 4,3 0.7680(2)[9] 0.67493(5) [10]
(1/3)(3,4,6,4) + (2/3)(4,6,12) 4,3 0.7157(2) [9] 0.63909(5) [10]
(1/7)(36) + (6/7)(32,4,12) 6,4 0.6808(2) [9] 0.55778(5) [10]
(2/3)(32,62) + (1/3)(3,6,3,6) 4,4 0.6499(2) [9] 0.53632(5) [10]
(1/7)(36) + (6/7)(32,6) 6,3 0.6329(2) [9] 0.51708(5) [10]
(4/5)(3,42,6) + (1/5)(3,6,3,6) 4,4 0.6286(2) [9] 0.51892(5) [10]
(4/5)(3,42,6) + (1/5)(3,6,3,6) 4,4 0.6279(2) [9] 0.51769(5) [10]
(2/3)(3,42,6) + (1/3)(3,4,6,4) 4,4 0.6221(2) [9] 0.54810(5) [10]
(1/2)(34,6) + (1/2)(32,62) 5,4 0.6171(2) [9] 0.48921(5) [10]
(1/2)(33,42) + (1/2)(3,4,6,4) 5,4 0.5885(2) [9] 0.47351(5) [10]
(1/2)(32,4,3,4) + (1/2)(3,4,6,4) 5,4 0.5883(2) [9] 0.46573(5) [10]
(1/2)(33,42) + (1/2)(44) 5,4 0.5720(2) [9] 0.45845(5) [10]
(2/3)(33,42) + (1/3)(44) 5,4 0.5648(2) [9] 0.44529(5) [10]
(1/4)(36) + (3/4)(34,6) 6,5 0.5607(2) [9] 0.41110(5) [10]
(1/2)(33,42) + (1/2)(32,4,3,4) 5,5 0.5505(2) [9] 0.41628(5) [10]
(1/3)(33,42) + (2/3)(32,4,3,4) 5,5 0.5504(2) [9] 0.41549(5) [10]
(1/7)(36) + (6/7)(32,4,3,4) 6,5 0.5440(2) [9] 0.40380(5) [10]
(1/2)(36) + (1/2)(34,6) 6,5 0.5407(2) [9] 0.38915(5) [10]
(1/3)(36) + (2/3)(33,42) 6,5 0.5342(2) [9] 0.39492(5) [10]
(1/2)(36) + (1/2)(33,42) 6,5 0.5258(2) [9] 0.38285(5) [10]

[edit] Thresholds on 2d bowtie and martini lattices

Lattice z Site Percolation Threshold Bond Percolation Threshold
martini 3 0.764826..., 3 p3 - p4 = 1 [11] 0.707107... = 1/\sqrt{2} [12]
bowtie 5 0.5472(2) [13] [14] 0.404518..., p + 6 p2 - 6 p3 + p5 = 1 [15]


[edit] Thresholds on other 2d lattices

Lattice z Site Percolation Threshold Bond Percolation Threshold
square covering lattice 6 1/2 0.3371(1) [16]

[edit] Thresholds on 2d inhomogeneous lattices

Lattice z Site Percolation Threshold Bond Percolation Threshold
bowtie with p = 1/2 on one non-diagonal bond 3 0.381966(3) [17]

[edit] Thresholds on 2d random lattices

Lattice z Site Percolation Threshold Bond Percolation Threshold
Delauney triangulation 6 (average) 1/2 0.3333(1) [18]
Voronoi tessellation 3 0.6670(1) [18]


[edit] Thresholds on 3d lattices

Lattice z Site Percolation Threshold Bond Percolation Threshold Dimer Percolation Threshold
simple cubic 6 0.3116081(21)[19] 0.2488126(5) [20] 0.2555(1)[21]
bcc 8 0.2459615(10)[22] 0.1802875(10)[20]
fcc 12 0.1992365(10)[22] 0.1201635(10)[20]
hcp 12 0.1992555(10)[23] 0.1201640(10)[23]
La2-x Srx Cu O4 12 0.19927(2) [24]
cubic with n.n.n. 18 0.13735(5) [25]
cubic with n.n.n.n. 26 0.0976445(10) [25]

n.n.n. = next-nearest neighbor, n.n.n.n. = next-next nearest neighbor

[edit] Thresholds for continuum and random-lattice models

Lattice Φc (critical volume fraction) n (critical total number)
Disks 0.6763475(6) [26]



[edit] Thresholds for directed percolation

Lattice z Site Percolation Threshold Bond Percolation Threshold
1+1d square lattice 2 0.70548522(4) [27] 0.64470015(5) [28]
1+1d triangular lattice 3 0.5956468(5) [28] 0.478025(1) [28]


[edit] General formulas for exact results

Inhomogeneous triangular lattice

Inhomogeneous honeycomb lattice

Inhomogeneous martini lattice [29]

1 − (p1p2r3 + p2p3r1 + p1p3r2) − (p1p2r1r2 + p1p3r1r3 + p2p3r2r3) + p1p2p3(r1r2 + r1r3 + r2r3) + r1r2r3(p1p2 + p1p3 + p2p3) − 2p1p2p3r1r2r3 = 0

Inhomogeneous martini-A (3-7) lattice

Inhomogeneous martini-B (3-5) lattice

Inhomogeneous checkerboard lattice (conjecture) [30]

1 − (p1p2 + p1p3 + p1p4 + p2p3 + p2p4 + p3p4) + p1p2p3 + p1p2p4 + p1p3p4 + p2p3p4 = 0

[edit] See also

[edit] References

  1. ^ Kasteleyn, P. W.; C. M. Fortuin (1969). "Phase transitions in lattice systems with random local properties". Journal of the Physical Society of Japan 26: 11–14. 
  2. ^ a b c d e Grünbaum, Branko; and Shephard, G. C. (1987). Tilings and Patterns. New York: W. H. Freeman. ISBN 0-716-71193-1. 
  3. ^ a b c d e f g h Suding, P. N.; R. M. Ziff (1999). "Site percolation thresholds for Archimedean lattices". Physical Review E 60 (1): 275–283. doi:10.1103/PhysRevE.60.275. 
  4. ^ a b c d e f g Parviainen, Robert (2007). "Estimation of bond percolation thresholds on the Archimedean lattices". J. Phys. A 40: 9253--9258. doi:10.1088/1751-8113/40/31/005. 
  5. ^ a b c Sykes, M. F.; J. W. Essam (1964). "Exact critical percolation probabilities for site and bond problems in two dimensions". Journal of Mathematical Physics (N.Y.) 5 (8): 1117–1127. doi:10.1063/1.1704215. 
  6. ^ Ziff, R. M.; P. W. Suding (1997). "Determination of the bond percolation threshold for the kagomé lattice". Journal of Physics A 30: 5351–5359. doi:10.1088/0305-4470/30/15/021. 
  7. ^ Newman, M. E. J.; R. M. Ziff (2000). "Efficient Monte-Carlo algorithm and high-precision results for percolation". Physical Review Letters 85 (19): 4104–4107. doi:10.1103/PhysRevLett.85.4104. ,
  8. ^ Lee, M. J. (2007). "Complementary algorithms for graphs and percolation". arXiv:0708.0600. 
  9. ^ a b c d e f g h i j k l m n o p q r s t Neher, Richard; Mecke, Klaus and Wagner, Herbert (8 Oct 2007). "Topological estimation of percolation thresholds". Preprint arXiv:0708.3250. 
  10. ^ a b c d e f g h i j k l m n o p q r s t Gu, Hang; R. M. Ziff (2007). "Percolation thresholds of 2-uniform lattice". To be published. 
  11. ^ Scullard, C. R. (2006). "Exact site percolation thresholds using a site-to-bond transformation and the star-triangle transformation". Physical Review E 73: 016107. doi:10.1103/PhysRevE.73.016107. 
  12. ^ Ziff, R. M. (2006). "Generalized cell–dual-cell transformation and exact thresholds for percolation". Physical Review E 73: 016134. doi:10.1103/PhysRevE.73.016134. 
  13. ^ van der Marck, S. C. (1997). "Percolation thresholds and universal formulas". Physical Review E 55: 1514–1517. doi:10.1103/PhysRevE.55.1514. 
  14. ^ van der Marck, S. C. (1998). "unpublished". 
  15. ^ Wierman, J. C. (1984). "A bond percolation critical probability determination based on the star-triangle transformation". Journal of Physics A 17: 1525–1530. doi:10.1088/0305-4470/17/7/020. 
  16. ^ Ziff, R. M. (2007). "". to be published. 
  17. ^ Scullard, C. R; R. M. Ziff (2007). "". to be published. 
  18. ^ a b Hsu, H. P.; M. C. Huang (1999). "Percolation thresholds, critical exponents, and scaling functions on planar random lattices and their duals". Physical Review E 60 (1999): 6361–6370. doi:10.1103/PhysRevE.60.6361. 
  19. ^ Ballesteros, P. N.; L. A. Fernández, V. Martín-Mayor, A. Muñoz, Sudepe, G. Parisi, and J. J. Ruiz-Lorenzo (1999). "Scaling corrections: site percolation and Ising model in three dimensions". Journal of Physics A 32: 1–13. doi:10.1088/0305-4470/32/1/004. 
  20. ^ a b c Lorenz, C. D.; R. M. Ziff (1998). "Precise determination of the bond percolation thresholds and finite-size scaling corrections for the sc, fcc, and bcc lattices". Physical Review E 57: 230–236. doi:10.1103/PhysRevE.57.230. 
  21. ^ Tarasevich, Yu. Yu.; V. A. Cherkasova (2007). "Dimer percolation and jamming on simple cubic lattice". European Physical Journal B 60 (1): 97–100. doi:10.1140/epjb/e2007-00321-2. 
  22. ^ a b Lorenz, C. D.; R. M. Ziff (1998). "Universality of the excess number of clusters and the crossing probability function in three-dimensional percolation". Journal of Physics A 31: 8147–8157. doi:10.1088/0305-4470/31/40/009. 
  23. ^ a b Lorenz, C. D.; R. May, R. M. Ziff (2000). "Universality of the excess number of clusters and the crossing probability function in three-dimensional percolation". Journal of Statistical Physics 98: 961–970. doi:10.1023/A:1018648130343. 
  24. ^ Tahir-Kheli, Jamil; W. A. Goddard III (2007). "Chiral plaquette polaron theory of cuprate superconductivity". Physical Review B 76: 014514. doi:10.1103/PhysRevB.76.014514. 
  25. ^ a b Ziff, R. M.; S. Torquato (2007). "". to be published. 
  26. ^ Quintanilla, John A.; R. M. Ziff (2007). "Near symmetry of percolation thresholds of fully penetrable disks with two different radii". Preprint. 
  27. ^ Jensen, Iwan (1999). "Low-density series expansions for directed percolation: I. A new efficient algorithm with applications to the square lattice". J. Phys. A 32: 5233–5249. doi:10.1088/0305-4470/32/28/304. 
  28. ^ a b c Jensen, Iwan (1996). "Low-density series expansions for directed percolation on square and triangular lattices". J. Phys. A 29: 7013–7040. doi:10.1088/0305-4470/29/22/007. 
  29. ^ Scullard, Christian R.; R. M. Ziff (2006). "Predictions of bond percolation thresholds for the kagomé and Archimedean (3,122) lattices". Physical Review E 73: 045102R. doi:10.1103/PhysRevE.73.045102. 
  30. ^ Wu, F. Y. (1979). "Critical point of planar Potts models". Journal of Physics C 12: L645–L650. doi:10.1088/0022-3719/12/17/002.