The critical random graph, with martingales

Abstract

We give a short proof that the largest component 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.

13 pages, 1 figure. Revised version. Contains stronger probability deviation bounds and handles the entire scaling window. To appear in Israel Journal of Mathematics

References in corpus (2)

• Random subgraphs of finite graphs: I. The scaling window under the triangle condition
• A point process describing the component sizes in the critical window of the random graph evolution

Cited by in corpus (3)

• Critical random graphs: Diameter and mixing time
• Random graph asymptotics on high-dimensional tori. II. Volume, diameter and mixing time
• Universality for critical heavy-tailed network models: Metric structure of maximal components