Hostname: page-component-7b7567c8c-2jgqx Total loading time: 0 Render date: 2026-11-19T17:14:17.709Z Has data issue: false hasContentIssue false

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

Published online by Cambridge University Press:  20 March 2018

Matthew I. Roberts*
Affiliation:
University of Bath
*
* Postal address: Department of Mathematical Sciences, University of Bath, Bath BA2 7AY, UK. Email address: mattiroberts@gmail.com
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 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.

MSC classification

Information

Type
Original Article
Copyright
Copyright © Applied Probability Trust 2018