Hostname: page-component-6898cfcb55-w5hgh Total loading time: 0 Render date: 2026-11-11T19:25:20.099Z Has data issue: false hasContentIssue false
  • English
  • Français

The Application of Non-Crossing Partitions to Improving Percolation Threshold Bounds

Published online by Cambridge University Press:  01 March 2007

WILLIAM D. MAY and
JOHN C. WIERMAN
WILLIAM D. MAY
Affiliation:
Department of Applied Mathematics and Statistics, Johns Hopkins University, Baltimore MD, USA (e-mail: wdmay@jhu.edu, wierman@jhu.edu)
JOHN C. WIERMAN
Affiliation:
Department of Applied Mathematics and Statistics, Johns Hopkins University, Baltimore MD, USA (e-mail: wdmay@jhu.edu, wierman@jhu.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We describe how non-crossing partitions arise in substitution method calculations. By using efficient algorithms for computing non-crossing partitions we are able to substantially reduce the computational effort, which enables us to compute improved bounds on the percolation thresholds for three percolation models. For the Kagomé bond model we improve bounds from 0.5182 ≤ pc ≤ 0.5335 to 0.522197 ≤ pc ≤ 0.526873, improving the range from 0.0153 to 0.004676. For the (3, 122) bond model we improve bounds from 0.7393 ≤ pc ≤ 0.7418 to 0.739773 ≤ pc ≤ 0.741125, improving the range from 0.0025 to 0.001352. We also improve the upper bound for the hexagonal site model, from 0.794717 to 0.743359.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 16 , Issue 2 , March 2007, pp. 285 - 307
Copyright
Copyright © Cambridge University Press 2006

References

[1]Ahuja, R. K., Magnanti, T. L. and Orlin, J. B. (1993) Network Flows: Theory, Algorithms and Applications, Prentice-Hall, New Jersey.Google Scholar
[2]Edelman, P. H. (1982) Multichains, non-crossing partitions and trees. Discrete Math. 40 171–179.CrossRefGoogle Scholar
[3]Grimmett, G. (1999) Percolation, 2nd edn, Springer, Berlin.CrossRefGoogle Scholar
[4]Hughes, B. D. (1996) Random Walks and Random Environments, Vol: 2: Random Environments, Oxford University Press, Oxford.CrossRefGoogle Scholar
[5]Kerber, A. (1999) Applied Finite Group Actions, 2nd edn, Springer, Berlin.CrossRefGoogle Scholar
[6]Kreweras, G. (1972) Sur les partitions non croisées d'un cycle. Discrete Math. 1 333–350.CrossRefGoogle Scholar
[7]Łuczak, T. and Wierman, J. C. (1988) Critical probability bounds for two-dimensional site percolation models. J. Phys. A: Math. Gen. 21 3131–3138.CrossRefGoogle Scholar
[8]May, W. D. and Wierman, J. C. (2006) Algorithms for non-crossing partitions. Technical Report 654, Johns Hopkins University, Department of Applied Mathematics and Statistics. To appear in Congressus Numerantium.Google Scholar
[9]May, W. D. and Wierman, J. C. (2005) Using symmetry to improve percolation threshold bounds. Combin. Probab. Comput. 14 549–566.CrossRefGoogle Scholar
[10]Parviainen, R. (2004) Connectivity properties of Archimedean and Laves lattices. PhD thesis, Uppsala University.Google Scholar
[11]Preston, C. J. (1974) A generalization of the FKG inequalities. Comm. Math. Phys. 36 233–241.CrossRefGoogle Scholar
[12]Tsallis, C. (1982) Phase diagram of anisotropic planar Potts ferromagnets: A new conjecture. J. Phys. C: Solid State Physics 15 L757–L764.CrossRefGoogle Scholar
[13]van den Berg, J. and Ermakov, A. (1996) A new lower bound for the critical probability of site percolation on the square lattice. Random Struct. Alg. 8 199–212.3.0.CO;2-T>CrossRefGoogle Scholar
[14]Wierman, J. C. (1981) Bond percolation on honeycomb and triangular lattices. Adv. Appl. Probab. 13 298–313.CrossRefGoogle Scholar
[15]Wierman, J. C. (1989) Bond percolation critical probability bounds for the Kagomé lattice by a substitution method. In Disorder in Physical Systems (Grimmett, G. and Welsh, D. J. A., eds), Oxford University Press, pp. 349–360.Google Scholar
[16]Wierman, J. C. (2002) Bond percolation critical probability bounds for three Archimedean lattices. Random Struct. Alg. 20 508–518.CrossRefGoogle Scholar
[17]Wierman, J. C. (2002) An improved upper bound for the hexagonal lattice site percolation critical probability. Combin. Probab. Comput. 11 629–643.CrossRefGoogle Scholar
[18]Wierman, J. C. (2003) Upper and lower bounds for the Kagomé lattice bond percolation critical probability. Combin. Probab. Comput. 12 95–111.CrossRefGoogle Scholar
[19]Wierman, J. C. and Naor, D. P. (2003) Desirable properties of universal formulas for percolation thresholds. Congressus Numerantium 163 125–142.Google Scholar