Unusually large components in near-critical Erdös-Rényi graphs via ballot theorems

Umberto De Ambroggio, Matthew I. Roberts

Research output: Contribution to journalArticlepeer-review

Abstract

We consider the near-critical Erdos-Rényi random graph G(n, p) and provide a new probabilistic proof of the fact that, when p is of the form p=p(n)=1/n+λ/n4/3 and A is large, {equation presented} where Cmax is the largest connected component of the graph. Our result allows A and λ to depend on n. While this result is already known, our proof relies only on conceptual and adaptable tools such as ballot theorems, whereas the existing proof relies on a combinatorial formula specific to Erdos-Rényi graphs, together with analytic estimates.

Original languageEnglish
Pages (from-to)840 - 869
Number of pages30
JournalCombinatorics, Probability and Computing
Volume31
Issue number5
Early online date11 Feb 2022
DOIs
Publication statusPublished - 30 Sep 2022

Keywords

  • ballot theorem
  • Brownian Motion
  • component size
  • Random graph
  • random walk

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Unusually large components in near-critical Erdös-Rényi graphs via ballot theorems'. Together they form a unique fingerprint.

Cite this