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

Abstract

We consider the near-critical Erdős-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+\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{λA^2}{2}-\frac{λ^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 Erdős-Rényi graphs, together with analytic estimates.

arXiv comment28 pages, 1 figure