Article contents
The probability of unusually large components in the near-critical Erdős–Rényi graph
Published online by Cambridge University Press: 20 March 2018
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.
- Type
- Original Article
- Information
- Copyright
- Copyright © Applied Probability Trust 2018
References
- 5
- Cited by