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

Matthew Roberts

doi:10.1017/apr.2018.12

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

Matthew Roberts

Research output: Contribution to journal › Article › peer-review

6 Citations (SciVal)

66 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 language	English
Pages (from-to)	245-271
Number of pages	27
Journal	Advances in Applied Probability
Volume	50
Issue number	1
DOIs	https://doi.org/10.1017/apr.2018.12
Publication status	Published - 1 Mar 2018

Keywords

Erdos-Rényi
component size
critical window
random graph

ASJC Scopus subject areas

Statistics and Probability
Applied Mathematics

Access to Document

10.1017/apr.2018.12

1610.05485
This article has been published in Advances in Applied Probability DOI: https://doi.org/10.1017/apr.2018.12. This version is free to view and download for private research and study only. Not for re-distribution, re-sale or use in derivative works. © Applied Probability Trust 2018.
Accepted author manuscript, 297 KB

http://arxiv.org/abs/1610.05485

Cite this

@article{1de9ecc3f85d4df3b99e177d8796322e,

title = "The probability of unusually large components in the near-critical Erd{\H o}s-R{\'e}nyi graph",

abstract = "The largest components of the critical Erd{\"o}s-R{\'e}nyi graph, G(n,p) with p=1/n, have size of order n\textasciicircum{}\{2/3\} with high probability. We give detailed asymptotics for the probability that there is an unusually large component, i.e. of size an\textasciicircum{}\{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.",

keywords = "Erdos-R{\'e}nyi, component size, critical window, random graph",

author = "Matthew Roberts",

year = "2018",

month = mar,

day = "1",

doi = "10.1017/apr.2018.12",

language = "English",

volume = "50",

pages = "245--271",

journal = "Advances in Applied Probability",

issn = "0001-8678",

publisher = "Cambridge University Press",

number = "1",

}

TY - JOUR

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

AU - Roberts, Matthew

PY - 2018/3/1

Y1 - 2018/3/1

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

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

KW - Erdos-Rényi

KW - component size

KW - critical window

KW - random graph

UR - http://www.scopus.com/inward/record.url?scp=85044116768&partnerID=8YFLogxK

U2 - 10.1017/apr.2018.12

DO - 10.1017/apr.2018.12

M3 - Article

SN - 0001-8678

VL - 50

SP - 245

EP - 271

JO - Advances in Applied Probability

JF - Advances in Applied Probability

IS - 1

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

EPSRC Posdoctoral Fellowship in Applied Probability for Dr Matthew I Roberts

Cite this

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Projects

EPSRC Posdoctoral Fellowship in Applied Probability for Dr Matthew I Roberts

Cite this