Hostname: page-component-7b9c58cd5d-hpxsc Total loading time: 0 Render date: 2025-03-15T07:55:38.341Z Has data issue: false hasContentIssue false
  • English
  • Français

The probability of unusually large components in the near-critical Erdős–Rényi graph

Part of: Graph theory Combinatorial probability

Published online by Cambridge University Press:  20 March 2018

Matthew I. Roberts
Matthew I. Roberts*
Affiliation:
University of Bath
*
* Postal address: Department of Mathematical Sciences, University of Bath, Bath BA2 7AY, UK. Email address: mattiroberts@gmail.com
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The largest components of the critical Erdős–Rényi graph, G(n, p) with p = 1 / n, have size of order n2/3 with high probability. We give detailed asymptotics for the probability that there is an unusually large component, i.e. of size an2/3 for large a. Our results, which extend the work of Pittel (2001), allow a to depend upon n and also hold for a range of values of p around 1 / n. We also provide asymptotics for the distribution of the size of the component containing a particular vertex.

Keywords

Erdős–Rényirandom graphcomponent sizecritical window

MSC classification

Primary: 60C05: Combinatorial probability
Secondary: 05C80: Random graphs
Type
Original Article
Information
Advances in Applied Probability , Volume 50 , Issue 1 , March 2018 , pp. 245 - 271
Copyright
Copyright © Applied Probability Trust 2018 

References

[1] Addario-Berry, L., Broutin, N. and Goldschmidt, C. (2010). Critical random graphs: limiting constructions and distributional properties. Electron. J. Prob. 15, 741–775. Google Scholar
[2] Addario-Berry, L., Broutin, N. and Goldschmidt, C. (2012). The continuum limit of critical random graphs. Prob. Theory Relat. Fields 152, 367–406. CrossRefGoogle Scholar
[3] Aïdékon, E., van der Hofstad, R., Kliem, S. and van Leeuwaarden, J. S. H. (2016). Large deviations for power-law thinned Lévy processes. Stoch. Process. Appl. 126, 1353–1384. Google Scholar
[4] Aldous, D. (1997). Brownian excursions, critical random graphs and the multiplicative coalescent. Ann. Prob. 25, 812–854. Google Scholar
[5] Bender, E. A., Canfield, E. R. and McKay, B. D. (1990). The asymptotic number of labeled connected graphs with a given number of vertices and edges. Random Structures Algorithms 1, 127–169. Google Scholar
[6] Bet, G., van der Hofstad, R. and van Leeuwaarden, J. S. H. (2014). Heavy-traffic analysis through uniform acceleration of queues with diminishing populations. Preprint. Available at https://arxiv.org/abs/1412.5329. Google Scholar
[7] Bhamidi, S., van der Hofstad, R. and van Leeuwaarden, J. S. H. (2010). Scaling limits for critical inhomogeneous random graphs with finite third moments. Electron. J. Prob. 15, 1682–1702. CrossRefGoogle Scholar
[8] Bollobás, B. (2001). Random Graphs (Camb. Stud. Adv. Math. 73), 2nd edn. Cambridge University Press. Google Scholar
[9] Bollobás, B. and Riordan, O. (2012). Asymptotic normality of the size of the giant component via a random walk. J. Combin. Theory B 102, 53–61. Google Scholar
[10] Dembo, A., Levit, A. and Vadlamani, S. (2017). Component sizes for large quantum Erdős–Rényi graph near criticality. To appear in Ann. Prob. Google Scholar
[11] Dhara, S., van der Hofstad, R., van Leeuwaarden, J. S. H. and Sen, S. (2017). Critical window for the configuration model: finite third moment degrees. Electron. J. Prob. 22, 16. Google Scholar
[12] Durrett, R. (2007). Random Graph Dynamics. Cambridge University Press. Google Scholar
[13] Erdős, P. and Rényi, A. (1959). On random graphs. I. Publ. Math. Debrecen 6, 290–297. Google Scholar
[14] Erdős, P. and Rényi, A. (1960). On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci A 5, 17–61. Google Scholar
[15] Erdős, P. and Rényi, A. (1961). On the evolution of random graphs. II. Bull. Inst. Internat. Statist. 38, 343–347. Google Scholar
[16] Janson, S. (2007). Brownian excursion area, Wright's constants in graph enumeration, and other Brownian areas. Prob. Surveys 4, 80–145. Google Scholar
[17] Janson, S., Łuczak, T. and Rucinski, A. (2000). Random Graphs. John Wiley, New York. Google Scholar
[18] Joseph, A. (2014). The component sizes of a critical random graph with given degree sequence. Ann. Appl. Prob. 24, 2560–2594. Google Scholar
[19] Łuczak, T. (1990). On the number of sparse connected graphs. Random Structures Algorithms 1, 171–173. Google Scholar
[20] Łuczak, T., Pittel, B. and Wierman, J. C. (1994). The structure of a random graph at the point of the phase transition. Trans. Amer. Math. Soc. 341, 721–748. CrossRefGoogle Scholar
[21] Nachmias, A. and Peres, Y. (2010). The critical random graph, with martingales. Israel J. Math. 176, 29–41. Google Scholar
[22] O'Connell, N. (1998). Some large deviation results for sparse random graphs. Prob. Theory Relat. Fields 110, 277–285. Google Scholar
[23] Pittel, B. (2001). On the largest component of the random graph at a nearcritical stage. J. Combin. Theory B 82, 237–269. Google Scholar
[24] Riordan, O. (2012). The phase transition in the configuration model. Combin. Prob. Comput. 21, 265–299. Google Scholar
[25] Robbins, H. (1955). A remark on Stirling's formula. Amer. Math. Monthly 62, 26–29. Google Scholar
[26] Roberts, M. and Şengül, B. (2017). Exceptional times of the critical dynamical Erdős–Rényi graph. To appear in Ann. Appl. Prob. Google Scholar
[27] Steif, J. E. (2009). A survey of dynamical percolation. In Fractal Geometry and Stochastics IV, Birkhäuser, Basel, pp. 145–174. Google Scholar
[28] Van der Hofstad, R. and Spencer, J. (2006). Counting connected graphs asymptotically. Europ. J. Combinatorics 27, 1294–1320. Google Scholar
[29] Van der Hofstad, R., Janssen, A. J. E. M. and van Leeuwaarden, J. S. H. (2010). Critical epidemics, random graphs, and Brownian motion with a parabolic drift. Adv. Appl. Prob 42, 1187–1206. Google Scholar
[30] Van der Hofstad, R., Kager, W. and Müller, T. (2009). A local limit theorem for the critical random graph. Electron. Commun. Prob. 14, 122–131. Google Scholar
[31] Van der Hofstad, R., Kliem, S. and van Leeuwaarden, J. S. H. (2014). Cluster tails for critical power-law inhomogeneous random graphs. Preprint. Available at https://arxiv.org/abs/1404.1727. Google Scholar
[32] Van der Hofstad, R., van Leeuwaarden, J. S. H. and Stegehuis, C. (2016). Mesoscopic scales in hierarchical configuration models. Preprint. Available at https://arxiv.org/abs/1612.02668. Google Scholar
[33] Voblyĭ, V. A. (1987). Wright and Stepanov–Wright coefficients. Mat. Zametki 42, 854–862. Google Scholar
[34] Wright, E. M. (1980). The number of connected sparsely edged graphs. III. Asymptotic results. J. Graph Theory 4, 393–407. Google Scholar