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

Matthew Roberts

OAI: oai:purehost.bath.ac.uk:publications/1de9ecc3-f85d-4df3-b99e-177d8796322e • DOI: https://doi.org/10.1017/apr.2018.12

The largest components of the critical Erdös-Rényi graph, G(n,p) with p=1/n, have size of order n^{2/3} with high probability. We give detailed asymptotics for the probability that there is an unusually large component, i.e. of size an^{2/3} for large a. Our results, which extend work of Pittel, 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.

Erdos-Rényi component size critical window Random graph /dk/atira/pure/subjectarea/asjc/2600/2613 name=Statistics and Probability /dk/atira/pure/subjectarea/asjc/2600/2604 name=Applied Mathematics