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) no. 3, pp. 999-1027.

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 ${\{-\lfloor r/2\rfloor ,...,\lceil r/2\rceil -1\}}^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.

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 ${\{-\lfloor r/2\rfloor ,...,\lceil r/2\rceil -1\}}^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.

Classification : 05C80, 60K35, 82B43
Mots clés : random graph, phase transition, critical behavior, percolation, torus, cycle structure

[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 | Zbl

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

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

[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 | Zbl

[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 | Zbl

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

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

[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 | Zbl

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

[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 | Zbl

[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 | Zbl

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

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

[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 | Zbl

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

[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 | Zbl

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

[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 | Zbl

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

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

[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 | Zbl

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