Cycle structure of percolation on high-dimensional tori

Remco van der Hofstad; Artëm Sapozhnikov

Annales de l'I.H.P. Probabilités et statistiques (2014)

  • Volume: 50, Issue: 3, page 999-1027
  • ISSN: 0246-0203

Abstract

top
In the past years, many properties of the largest connected components of critical percolation on the high-dimensional torus, such as their sizes and diameter, have been established. The order of magnitude of these quantities equals the one for percolation on the complete graph or Erdős–Rényi random graph, raising the question whether the scaling limits of the largest connected components, as identified by Aldous (1997), are also equal. In this paper, we investigate the cycle structureof the largest critical components for high-dimensional percolation on the torus { - ⌊ r / 2 ⌋ , ... , ⌈ r / 2 ⌉ - 1 } d . While percolation clusters naturally have manyshort cycles, we show that the longcycles, i.e., cycles that pass through the boundary of the cube of width r / 4 centered around each of their vertices, have length of order r d / 3 , as on the critical Erdős–Rényi random graph. On the Erdős–Rényi random graph, cycles play an essential role in the scaling limit of the large critical clusters, as identified by Addario-Berry, Broutin and Goldschmidt (2010). Our proofs crucially rely on various new estimates of probabilities of the existence of open paths in critical Bernoulli percolation on ℤ d with constraints on their lengths. We believe these estimates are interesting in their own right.

How to cite

top

van der Hofstad, Remco, and Sapozhnikov, Artëm. "Cycle structure of percolation on high-dimensional tori." Annales de l'I.H.P. Probabilités et statistiques 50.3 (2014): 999-1027. <http://eudml.org/doc/271943>.

@article{vanderHofstad2014,
abstract = {In the past years, many properties of the largest connected components of critical percolation on the high-dimensional torus, such as their sizes and diameter, have been established. The order of magnitude of these quantities equals the one for percolation on the complete graph or Erdős–Rényi random graph, raising the question whether the scaling limits of the largest connected components, as identified by Aldous (1997), are also equal. In this paper, we investigate the cycle structureof the largest critical components for high-dimensional percolation on the torus $\lbrace -\lfloor r/2\rfloor ,\ldots ,\lceil r/2\rceil -1\rbrace ^\{d\}$. While percolation clusters naturally have manyshort cycles, we show that the longcycles, i.e., cycles that pass through the boundary of the cube of width $r/4$ centered around each of their vertices, have length of order $r^\{d/3\}$, as on the critical Erdős–Rényi random graph. On the Erdős–Rényi random graph, cycles play an essential role in the scaling limit of the large critical clusters, as identified by Addario-Berry, Broutin and Goldschmidt (2010). Our proofs crucially rely on various new estimates of probabilities of the existence of open paths in critical Bernoulli percolation on $\mathbb \{Z\}^\{d\}$ with constraints on their lengths. We believe these estimates are interesting in their own right.},
author = {van der Hofstad, Remco, Sapozhnikov, Artëm},
journal = {Annales de l'I.H.P. Probabilités et statistiques},
keywords = {random graph; phase transition; critical behavior; percolation; torus; cycle structure},
language = {eng},
number = {3},
pages = {999-1027},
publisher = {Gauthier-Villars},
title = {Cycle structure of percolation on high-dimensional tori},
url = {http://eudml.org/doc/271943},
volume = {50},
year = {2014},
}

TY - JOUR
AU - van der Hofstad, Remco
AU - Sapozhnikov, Artëm
TI - Cycle structure of percolation on high-dimensional tori
JO - Annales de l'I.H.P. Probabilités et statistiques
PY - 2014
PB - Gauthier-Villars
VL - 50
IS - 3
SP - 999
EP - 1027
AB - In the past years, many properties of the largest connected components of critical percolation on the high-dimensional torus, such as their sizes and diameter, have been established. The order of magnitude of these quantities equals the one for percolation on the complete graph or Erdős–Rényi random graph, raising the question whether the scaling limits of the largest connected components, as identified by Aldous (1997), are also equal. In this paper, we investigate the cycle structureof the largest critical components for high-dimensional percolation on the torus $\lbrace -\lfloor r/2\rfloor ,\ldots ,\lceil r/2\rceil -1\rbrace ^{d}$. While percolation clusters naturally have manyshort cycles, we show that the longcycles, i.e., cycles that pass through the boundary of the cube of width $r/4$ centered around each of their vertices, have length of order $r^{d/3}$, as on the critical Erdős–Rényi random graph. On the Erdős–Rényi random graph, cycles play an essential role in the scaling limit of the large critical clusters, as identified by Addario-Berry, Broutin and Goldschmidt (2010). Our proofs crucially rely on various new estimates of probabilities of the existence of open paths in critical Bernoulli percolation on $\mathbb {Z}^{d}$ with constraints on their lengths. We believe these estimates are interesting in their own right.
LA - eng
KW - random graph; phase transition; critical behavior; percolation; torus; cycle structure
UR - http://eudml.org/doc/271943
ER -

References

top
  1. [1] L. Addario-Berry, N. Broutin and C. Goldschmidt. Critical random graphs: Limiting constructions and distributional properties. Electron. J. Probab. 15 (25) (2010) 741–775. Zbl1227.05224MR2650781
  2. [2] D. Aldous. Brownian excursions, critical random graphs and the multiplicative coalescent. Ann. Probab.25 (1997) 812–854. Zbl0877.60010MR1434128
  3. [3] B. Bollobás. Random graphs, 2nd edition. Cambridge Studies in Advanced Mathematics 73. Cambridge Univ. Press, Cambridge, 2001. Zbl0979.05003MR1864966
  4. [4] C. Borgs, J. T. Chayes, R. van der Hofstad, G. Slade and J. Spencer. Random subgraphs of finite graphs. I. The scaling window under the triangle condition. Random Structures Algorithms 27 (2005) 137–184. Zbl1076.05071MR2155704
  5. [5] C. Borgs, J. T. Chayes, R. van der Hofstad, G. Slade and J. Spencer. Random subgraphs of finite graphs. II. The lace expansion and the triangle condition. Ann. Probab. 33 (2005) 1886–1944. Zbl1079.05087MR2165583
  6. [6] C. Borgs, J. Chayes, R. van der Hofstad, G. Slade and J. Spencer. Random subgraphs of finite graphs. III. The phase transition for the n -cube. Combinatorica 26 (4) (2006) 395–410. Zbl1121.05108MR2260845
  7. [7] J. T. Chayes and L. Chayes. On the upper critical dimension of Bernoulli percolation. Commun. Math. Phys. 113 (1) (1987) 27–48. Zbl0627.60100MR918403
  8. [8] P. Erdős and A. Rényi. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl.5 (1960) 17–61. Zbl0103.16301MR125031
  9. [9] G. Grimmett. Percolation, 2nd edition. Springer, Berlin, 1999. MR1707339
  10. [10] T. Hara. Decay of correlations in nearest-neighbor self-avoiding walk, percolation, lattice trees and animals. Ann. Probab. 36 (2) (2008) 530–593. Zbl1142.82006MR2393990
  11. [11] T. Hara, R. van der Hofstad and G. Slade. Critical two-point functions and the lace expansion for spread-out high-dimensional percolation and related models. Ann. Prob.31 (2003) 349–408. Zbl1044.82006MR1959796
  12. [12] T. Hara and G. Slade. Mean-field critical behaviour for percolation in high dimensions. Commun. Math. Phys.128 (1990) 333–391. Zbl0698.60100MR1043524
  13. [13] M. Heydenreich and R. van der Hofstad. Random graph asymptotics on high-dimensional tori. Comm. Math. Phys. 270 (2) (2007) 335–358. Zbl1128.82010MR2276449
  14. [14] M. Heydenreich and R. van der Hofstad. Random graph asymptotics on high-dimensional tori II: Volume, diameter and mixing time. Probab. Theory Related Fields 149 (3–4) (2011) 397–415. Zbl1229.60108MR2776620
  15. [15] R. van der Hofstad and A. Nachmias. Hypercube percolation. Preprint, 2012. Available at arXiv:1201.3953. MR3156736
  16. [16] S. Janson, D. E. Knuth, T. Łuczak and B. Pittel. The birth of the giant component. Random Structures Algorithms 4 (3) (1993) 231–358. Zbl0795.05127MR1220220
  17. [17] S. Janson, T. Łuczak and A. Rucinski. Random Graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000. Zbl0968.05003MR1801138
  18. [18] H. Kesten. The critical probability of bond percolation on the square lattice equals 1 / 2 . Commun. Math. Phys. 74 (1) (1980) 41–59. Zbl0441.60010MR575895
  19. [19] G. Kozma and A. Nachmias. Arm exponents in high-dimensional percolation. J. Amer. Math. Soc. 24 (2) (2011) 375–409. Zbl1219.60085MR2748397
  20. [20] G. Kozma and A. Nachmias. The Alexander–Orbach conjecture holds in high dimensions. Invent. Math. 178 (3) (2009) 635–654. Zbl1180.82094MR2551766
  21. [21] T. Łuczak, B. Pittel and J. Wierman. The structure of a random graph at the point of the phase transition. Trans. Amer. Math. Soc. 341 (2) (1994) 721–748. Zbl0807.05065MR1138950
  22. [22] A. Nachmias and Y. Peres. Critical random graphs: Diameter and mixing time. Ann. Probab.36 (2008) 1267–1286. Zbl1160.05053MR2435849

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.