Hostname: page-component-586b7cd67f-vdxz6 Total loading time: 0 Render date: 2024-11-24T05:45:07.512Z 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: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

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 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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