×

zbMATH — the first resource for mathematics

A note about critical percolation on finite graphs. (English) Zbl 1235.60138
Summary: We study the geometry of the largest component \({\mathcal{C}}_{1}\) of the critical percolation on a finite graph \(G\) which satisfies the finite triangle condition, defined by C. Borgs et al. [Random Struct. Algorithms 27, No. 2, 137–184 (2005; Zbl 1076.05071)]. There it was shown that this component is of size \(n^{2/3}\); and, here, we show that its diameter is \(n^{1/3}\) and that the simple random walk takes \(n\) steps to mix on it. In the light of [C. Borgs et al., Ann. Probab. 33, No. 5, 1886–1944 (2005; Zbl 1079.05087)], our results apply to critical percolation on several high-dimensional finite graphs such as the finite torus \({\mathbb{Z}}_{n}^{d}\) (with \(d\) large and \(n \rightarrow \infty\)) and the Hamming cube \(\{0,1\}^{n}\).

MSC:
60K35 Interacting random processes; statistical mechanics type models; percolation theory
05C80 Random graphs (graph-theoretic aspects)
PDF BibTeX Cite
Full Text: DOI arXiv
References:
[1] Aizenman, M., Newman, C.M.: Tree graph inequalities and critical behavior in percolation models. J. Stat. Phys. 36(1–2), 107–143 (1984) · Zbl 0586.60096
[2] Barsky, D.J., Aizenman, M.: Percolation critical exponents under the triangle condition. Ann. Probab. 19(4), 1520–1536 (1991) · Zbl 0747.60093
[3] Borgs, C., Chayes, J.T., van der Hofstad, R., Slade, G., Spencer, J.: Random subgraphs of finite graphs: I. The scaling window under the triangle condition. Random Struct. Algorithms 27, 137–184 (2005) · Zbl 1076.05071
[4] Borgs, C., Chayes, J.T., van der Hofstad, R., Slade, G., Spencer, J.: Random subgraphs of finite graphs: II. The lace expansion and the triangle condition. Ann. Probab. 33, 1886–1944 (2005) · Zbl 1079.05087
[5] Bollobás, B.: The evolution of random graphs. Trans. Am. Math. Soc. 286, 257–274 (1984) · Zbl 0579.05046
[6] Erdos, P., Rényi, A.: On the evolution of random graphs. Magy. Tud. Akad. Mat. Kut. Intéz. Kozl. 5, 17–61 (1960) · Zbl 0103.16301
[7] Hara, T., Slade, G.: Mean-field critical behaviour for percolation in high dimensions. Commun. Math. Phys. 128, 333–391 (1990) · Zbl 0698.60100
[8] Heydenreich, M., van der Hofstad, R.: Random graph asymptotics on high-dimensional tori. Commun. Math. Phys. 270, 335–358 (2007) · Zbl 1128.82010
[9] Heydenreich, M., van der Hofstad, R.: Random graph asymptotics on high-dimensional tori II: volume, diameter and mixing time. Probab. Theory Rel. Fields. (2009). doi: 10.1007/s00440-009-0258-y · Zbl 1229.60108
[10] Kozma, G., Nachmias, A.: The Alexander–Orbach conjecture holds in high dimensions. Invent. Math. 178(3), 635–654 (2009) · Zbl 1180.82094
[11] Nachmias, A., Peres, Y.: Critical random graphs: diameter and mixing time. Ann. Probab. 36(4), 1267–1286 (2008) · Zbl 1160.05053
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.