Unusually large components in near-critical Erd\H{o}s-R\'{e}nyi graphs via ballot theorems

DOI10.1017/S0963548321000584MaRDI QIDQ6358240arXivWikidataFDO

Authors Umberto De Ambroggio, Matthew I. Roberts

Publication date 13 January 2021

Published in arXiv

Full work available at URL https://doi.org/10.1017/S0963548321000584

Mathematics Subject Classification ID

Combinatorial probability (60C05) Sums of independent random variables; random walks (60G50)

arXiv classification

math.COmath.PR

Abstract: We consider the near-critical ErdH{o}s-R'{e}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+lambda/n^{4/3}$ and $A$ is large, [mathbb{P}(|mathcal{C}_{max}|>An^{2/3})asymp A^{-3/2}e^{-frac{A^3}{8}+frac{lambda A^2}{2}-frac{lambda^2A}{2}}] where $mathcal{C}_{max}$ is the largest connected component of the graph. Our result allows $A$ and $lambda$ 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 ErdH{o}s-R'{e}nyi graphs, together with analytic estimates.

This page was built for publication: Unusually large components in near-critical Erd\H{o}s-R\'{e}nyi graphs via ballot theorems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6358240)