On the critical probability in percolation. (English) Zbl 1387.05239
Summary: For percolation on finite transitive graphs, A. Nachmias and Y. Peres [Ann. Probab. 36, No. 4, 1267–1286 (2008; Zbl 1160.05053)] suggested a characterization of the critical probability based on the logarithmic derivative of the susceptibility. As a first test-case, we study their suggestion for the Erdős-Rényi random graph \(G_{n,p}\), and confirm that the logarithmic derivative has the desired properties: (i) its maximizer lies inside the critical window \(p=1/n+\Theta (n^{-4/3})\), and (ii) the inverse of its maximum value coincides with the \(\Theta (n^{-4/3})\)-width of the critical window. We also prove that the maximizer is not located at \(p=1/n\) or \(p=1/(n-1)\), refuting a speculation of Peres.
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
| 60C05 | Combinatorial probability |
| 82B43 | Percolation |
| 60K35 | Interacting random processes; statistical mechanics type models; percolation theory |
Citations:
Zbl 1160.05053Software:
DLMFReferences:
| [1] | M. Aizenman and C. M. Newman. Tree graph inequalities and critical behavior in percolation models. J. Statist. Phys.36 (1984), 107-143. · Zbl 0586.60096 |
| [2] | M. Ajtai, J. Komlós and E. Szemerédi. Largest random component of a \(k\)-cube. Combinatorica2 (1982), 1-7. · Zbl 0489.05053 |
| [3] | D. Aldous. Brownian excursions, critical random graphs and the multiplicative coalescent. Ann. Probab.25 (1997), 812-854. · Zbl 0877.60010 |
| [4] | B. Bollobás. The evolution of random graphs. Trans. Amer. Math. Soc.286 (1984), 257-274. · Zbl 0579.05046 |
| [5] | B. Bollobás, Y. Kohayakawa and T. Łuczak. The evolution of random subgraphs of the cube. Rand. Struct. & Algor.3 (1992), 55-90. · Zbl 0779.05045 |
| [6] | B. Bollobás and O. Riordan. Exploring hypergraphs with martingales. Rand. Struct. & Algor.50 (2017), 325-352. · Zbl 1364.05051 |
| [7] | 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. Rand. Struct. & Algor.27 (2005), 137-184. · Zbl 1076.05071 |
| [8] | 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. · Zbl 1079.05087 |
| [9] | C. Borgs, J. T. Chayes, R. van der Hofstad, G. Slade and J. Spencer. Random subgraphs of finite graphs. III. The phase transition for the \(n\)-cube. Combinatorica26 (2006), 395-410. · Zbl 1121.05108 |
| [10] | M. Dwass. The total progeny in a branching process and a related random walk. J. Appl. Probability6 (1969), 682-686. · Zbl 0192.54401 · doi:10.2307/3212112 |
| [11] | P. Erdős and A. Rényi. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl5 (1960), 17-61. · Zbl 0103.16301 |
| [12] | P. Erdős and A. Rényi. On the strength of connectedness of a random graph. Acta Math. Acad. Sci. Hungar.12 (1961), 261-267. · Zbl 0103.16302 |
| [13] | G. Grimmett. Percolation. Second edition, Springer, Berlin (1999). · Zbl 0926.60004 |
| [14] | A. Gut. Probability: a Graduate Course. Springer, New York (2005). · Zbl 1076.60001 |
| [15] | R. van der Hofstad and M. J. Luczak. Random subgraphs of the 2D Hamming graph: the supercritical phase. Probab. Theory & Related Fields147 (2010), 1-41. · Zbl 1188.05141 |
| [16] | R. van der Hofstad and A. Nachmias. Hypercube percolation. J. Eur. Math. Soc.19 (2017), 725-814. · Zbl 1381.60119 |
| [17] | R. van der Hofstad and A. Nachmias. Unlacing hypercube percolation: a survey. Metrika77 (2014), 23-50. · Zbl 1455.60132 |
| [18] | R. van der Hofstad and G. Slade. Expansion in \(n^{-1}\) for percolation critical values on the \(n\)-cube and \(\mathbb Z^n\): the first three terms. Combin. Probab. Comput.15 (2006), 695-713. · Zbl 1102.60090 · doi:10.1017/S0963548306007498 |
| [19] | S. Janson. Brownian excursion area, Wright’s constants in graph enumeration, and other Brownian areas. Probab. Surv.4 (2007), 80-145. · Zbl 1189.60147 |
| [20] | S. Janson and G. Louchard. Tail estimates for the Brownian excursion area and other Brownian areas. Electronic J. Probab.12 (2007), no. 58, 1600-1632. · Zbl 1189.60148 · doi:10.1214/EJP.v12-471 |
| [21] | S. Janson, T. Łuczak and A. Ruciński. Random Graphs. Wiley-Interscience, New York (2000). · Zbl 0968.05003 |
| [22] | S. Janson and M. J. Luczak. Susceptibility in subcritical random graphs. J. Math. Phys.49 (2008), 125207. · Zbl 1159.81324 |
| [23] | S. Janson and J. Spencer. A point process describing the component sizes in the critical window of the random graph evolution. Combin. Probab. Comput.16 (2007), 631-658. · Zbl 1136.05069 |
| [24] | G. Kozma and A. Nachmias. The Alexander-Orbach conjecture holds in high dimensions. Invent. Math.178 (2009), 635-654. · Zbl 1180.82094 |
| [25] | G. Kozma and A. Nachmias. A note about critical percolation on finite graphs. J. Theoret. Probab.24 (2011), 1087-1096. · Zbl 1235.60138 |
| [26] | Y. Long, A. Nachmias, W. Ning and Y. Peres. A power law of order \(1/4\) for critical mean field Swendsen-Wang dynamics. Mem. Amer. Math. Soc.232 (2014). · Zbl 1304.60078 |
| [27] | G. Louchard. The Brownian excursion area: a numerical analysis. Comput. Math. Appl.10 (1984), 413-417. · Zbl 0569.65097 |
| [28] | T. Łuczak. Component behavior near the critical point of the random graph process. Rand. Struct. & Algor.1 (1990), 287-310. · Zbl 0745.05048 |
| [29] | G. A. Margulis. Probabilistic characteristics of graphs with large connectivity. (Russian.) Problemy Peredači Informacii10 (1974), 101-108. · Zbl 0322.05147 |
| [30] | A. Nachmias and Y. Peres. Critical random graphs: diameter and mixing time. Ann. Probab.36 (2008), 1267-1286. · Zbl 1160.05053 |
| [31] | NIST Handbook of Mathematical Functions. Eds. F. W. J. Olver, D. W. Lozier, R. F. Boisvert and C. W. Clark. Cambridge University Press (2010). Also available as NIST Digital Library of Mathematical Functions, http://dlmf.nist.gov/. · Zbl 1198.00002 |
| [32] | O. Riordan and L. Warnke. The evolution of subcritical Achlioptas processes. Rand. Struct. & Algor.47 (2015), 174-203. · Zbl 1332.05130 |
| [33] | O. Riordan and L. Warnke. The phase transition in bounded-size Achlioptas processes. Preprint (2017). arXiv:1704.08714 · Zbl 1332.05130 |
| [34] | L. Russo. On the critical percolation probabilities. Z. Wahrsch. Verw. Gebiete56 (1981), 229-237. · Zbl 0457.60084 |
| [35] | J. Spencer. Enumerating graphs and Brownian motion. Comm. Pure Appl. Math.50 (1997), 291-294. · Zbl 0457.60084 |
| [36] | E. M. Wright. The number of connected sparsely edged graphs. J. Graph Theory1 (1977), 317-330. · Zbl 0871.05032 |
| [37] | L. Warnke. Percolation thoughts. MSR-Internship Report (2012). |
| [38] | E. M. Wright. The number of connected sparsely edged graphs. J. Graph Theory 1 (1977), 317-330. · Zbl 0337.05119 · doi:10.1002/jgt.3190010407 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
