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

Research output: Contribution to journalArticlepeer-review

6 Citations (SciVal)
46 Downloads (Pure)

Abstract

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.
Original languageEnglish
Pages (from-to)245-271
Number of pages27
JournalAdvances in Applied Probability
Volume50
Issue number1
DOIs
Publication statusPublished - 1 Mar 2018

Keywords

  • Erdos-Rényi
  • component size
  • critical window
  • random graph

ASJC Scopus subject areas

  • Statistics and Probability
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'The probability of unusually large components in the near-critical Erdős-Rényi graph'. Together they form a unique fingerprint.

Cite this