The critical random graph, with martingales. (English) Zbl 1215.05168
Summary: We give a short proof that the largest component \(\mathcal C _{1}\) of the random graph \(G(n, 1/n)\) is of size approximately \(n ^{2/3}\). The proof gives explicit bounds for the probability that the ratio is very large or very small. In particular, the probability that \(n ^{ - 2/3}|\mathcal C _{1}\)| exceeds \(A\) is at most \({e^{ - c{A^3}}}\) for some \(c > 0\).
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
References:
| [1] | D. Aldous, Brownian excursions, critical random graphs and the multiplicative coalescent, The Annals of Probability 25 (1997), 812–854. · Zbl 0877.60010 · doi:10.1214/aop/1024404421 |
| [2] | N. and J. H. Spencer, The Probabilistic Method, 2nd edition, Wiley, New York, 2000. |
| [3] | E. A. Bender, E. R. Canfield and B. D. McKay, The asymptotic number of labeled connected graphs with a given number of vertices and edges, Random Structures & Algorithms 1 (1990), 127–169. · Zbl 0745.05022 · doi:10.1002/rsa.3240010202 |
| [4] | B. Bollobás, The evolution of random graphs, Transactions of the American Mathematical Society 286 (1984), 257–274. · Zbl 0579.05046 · doi:10.1090/S0002-9947-1984-0756039-5 |
| [5] | B. Bollobás, Random Graphs, Academic Press, London, 1985. |
| [6] | 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. · Zbl 1076.05071 · doi:10.1002/rsa.20051 |
| [7] | R. Durrett, Probability: Theory and Examples, 2nd edition, Duxbury Press, Belmont, California, 1996. · Zbl 1202.60001 |
| [8] | P. Erdos and A. Rényi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Kozl. 5 (1960), 17–61. |
| [9] | S. Janson, D. E. Knuth, T. Luczak and B. Pittel, The birth of the giant component. With an introduction by the editors, Random Structures & Algorithms 4 (1993), 231–358. · Zbl 0795.05127 · doi:10.1002/rsa.3240040302 |
| [10] | S. Janson, T. Luczak and A. Ruciński, Random Graphs, Wiley, New York, 2000. |
| [11] | R. M. Karp, The transitive closure of a random digraph, Random Structures & Algorithms 1 (1990), 73–93. · Zbl 0712.68076 · doi:10.1002/rsa.3240010106 |
| [12] | T. Luczak, Component behavior near the critical point of the random graph process, Random Structures & Algorithms 1 (1990), 287–310. · Zbl 0745.05048 · doi:10.1002/rsa.3240010305 |
| [13] | T. Luczak, B. Pittel and J. C. Wierman, The structure of a random graph at the point of the phase transition, Transactions of the American Mathematical Society 341 (1994), 721–748. · Zbl 0807.05065 · doi:10.2307/2154580 |
| [14] | A. Martin-Löf, Symmetric sampling procedures, general epidemic processes and their threshold limit theorems, Journal of Applied Probability 23 (1986), 265–282. · Zbl 0605.92009 · doi:10.2307/3214172 |
| [15] | A. Nachmias and Y. Peres, Critical percolation on random regular graphs, Random Structures & Algorithms, to appear. Available at http://www.arxiv.org/abs/0707.2839 . · Zbl 1209.05228 |
| [16] | B. Pittel, On the largest component of the random graph at a nearcritical stage, Journal of Combinatorial Theory. Series B 82 (2001), 237–269. · Zbl 1028.05102 · doi:10.1006/jctb.2000.2033 |
| [17] | A. D. Scott and G. B. Sorkin, Solving sparse random instances of Max Cut and Max 2-CSP in linear expected time, Combinatorics, Probability and Computing 15 (2006), 281–315. · Zbl 1082.05519 · doi:10.1017/S096354830500725X |
| [18] | D. Williams, Probability with martingales, Cambridge University Press, Cambridge, 1991. · Zbl 0722.60001 |
| [19] | E. M. Wright, The number of connected sparsely edged graphs, Journal of Graph Theory 1 (1977), 317–330. · 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.
