Cycle structure of percolation on high-dimensional tori

van der Hofstad, Remco ; Sapozhnikov, Artëm

Annales de l'I.H.P. Probabilités et statistiques, Tome 50 (2014), p. 999-1027 / Harvested from Numdam

Résumé

Plusieurs propriétés du comportement des grandes composantes connexes de la percolation critique sur le tore en dimensions grandes ont été récemment établies, telles la taille et le diamétre. L’ordre de grandeur de ces quantités est égal à celle de la percolation sur le graphe complet ou sur le graphe aléatoire de Erdős-Rényi. Ce résultat suggère la question de savoir si les limites d’échelles des plus grandes composantes connexes, telles qu’identifiées par Aldous (1997), sont aussi égales. Dans ce travail, nous étudions la structure des cycles des plus grandes composantes connexes pour la percolation critique en grande dimension sur le tore $\lbrace -\lfloor r/2\rfloor ,\ldots ,\lceil r/2\rceil -1\rbrace ^{d}$. Alors que les amas de percolation ont plusieurs cycles courts, nous montrons que les cycles longs, c’est-à-dire ceux qui passent à travers la frontière de chacun des cubes de largeur $r/4$ centrés aux sommets du cycle, ont une longueur de l’ordre $r^{d/3}$, comme dans le cas du graphe aléatoire critique d’Erdős-Rényi. Sur ce dernier, les cycles jouent un rôle essentiel dans la limite d’échelle des grands amas critiques tels qu’identifiés par Addario-Berry, Broutin and Goldschmidt (2010). Les preuves sont basées de manière cruciale sur de nouvelles estimations de la probabilités d’existence de chemins ouverts dans la percolation critique de type Bernouilli sur $\mathbb {Z}^{d}$ avec des contraintes sur leurs longueurs. Ces estimations sont potentiellement intéressantes en soi.

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 structure of 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 many short cycles, we show that the long cycles, 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.

Détail

Publié le : 2014-01-01

MR 3224297 | Zbl 1297.05222

DOI : https://doi.org/10.1214/13-AIHP565
Classification:  05C80,  60K35,  82B43

Bibliographie

[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. | MR 2650781 | Zbl 1227.05224

[2] D. Aldous. Brownian excursions, critical random graphs and the multiplicative coalescent. Ann. Probab. 25 (1997) 812-854. | MR 1434128 | Zbl 0877.60010

[3] B. Bollobás. Random graphs, 2nd edition. Cambridge Studies in Advanced Mathematics 73. Cambridge Univ. Press, Cambridge, 2001. | MR 1864966 | Zbl 0979.05003

[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. | MR 2155704 | Zbl 1076.05071

[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. | MR 2165583 | Zbl 1079.05087

[6] C. Borgs, J. Chayes, R. Van Der Hofstad, G. Slade and J. Spencer. Random subgraphs of finite graphs2006) 395-410. | MR 2260845 | Zbl 1121.05108

[7] J. T. Chayes and L. Chayes. On the upper critical dimension of Bernoulli percolation. Commun. Math. Phys. 113 (1) (1987) 27-48. | MR 918403 | Zbl 0627.60100

[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. | MR 125031 | Zbl 0103.16301

[9] G. Grimmett. Percolation, 2nd edition. Springer, Berlin, 1999. | MR 1707339

[10] T. Hara. Decay of correlations in nearest-neighbor self-avoiding walk, percolation, lattice trees and animals. Ann. Probab. 36 (2) (2008) 530-593. | MR 2393990 | Zbl 1142.82006

[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. | MR 1959796 | Zbl 1044.82006

[12] T. Hara and G. Slade. Mean-field critical behaviour for percolation in high dimensions. Commun. Math. Phys. 128 (1990) 333-391. | MR 1043524 | Zbl 0698.60100

[13] M. Heydenreich and R. Van Der Hofstad. Random graph asymptotics on high-dimensional tori. Comm. Math. Phys. 270 (2) (2007) 335-358. | MR 2276449 | Zbl 1128.82010

[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. | MR 2776620 | Zbl 1229.60108

[15] R. Van Der Hofstad and A. Nachmias. Hypercube percolation. Preprint, 2012. Available at arXiv:1201.3953. | MR 3156736

[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. | MR 1220220 | Zbl 0795.05127

[17] S. Janson, T. Łuczak and A. Rucinski. Random Graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000. | MR 1801138 | Zbl 0968.05003

[18] H. Kesten. The critical probability of bond percolation on the square lattice equals $1/2$. Commun. Math. Phys. 74 (1) (1980) 41-59. | MR 575895 | Zbl 0441.60010

[19] G. Kozma and A. Nachmias. Arm exponents in high-dimensional percolation. J. Amer. Math. Soc. 24 (2) (2011) 375-409. | MR 2748397 | Zbl 1219.60085

[20] G. Kozma and A. Nachmias. The Alexander-Orbach conjecture holds in high dimensions. Invent. Math. 178 (3) (2009) 635-654. | MR 2551766 | Zbl 1180.82094

[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. | MR 1138950 | Zbl 0807.05065

[22] A. Nachmias and Y. Peres. Critical random graphs: Diameter and mixing time. Ann. Probab. 36 (2008) 1267-1286. | MR 2435849 | Zbl 1160.05053