Upper bounds for the probability of unusually small components in critical random graphs

Umberto De Ambroggio

Published 2022-01-04, updated 2022-05-20Version 3

We describe a methodology, mostly based on an estimate for the probability that a (mean zero) $\mathbb{Z}$-valued random walk remains below a constant barrier over a finite time interval and Kolmogorov's maximal inequality, to derive upper bounds for the probability of observing unusually small maximal components in two classical random graphs when considered near criticality. Specifically, we consider the random graph $\mathbb{G}(n,d,p)$ obtained by performing $p$-bond percolation on a (simple) random $d$-regular graph, as well as the Erd\H{o}s-R\'enyi random graph $\mathbb{G}(n,p)$, and show that, near criticality, the probability of observing a largest component containing less than $n^{2/3}/A$ vertices decays as $A^{-\epsilon}$ for some $\epsilon>0$ in both models. Even though this result is not new, our approach is quite robust since it yields similar proofs for both models considered here and, moreover, it allows us to provide a shorter analysis for the $\mathbb{G}(n,d,p)$ model with respect to the one available in the literature. We also provide a short, random-walk-based proof of the fact that, in the random graph obtained through critical percolation on \textit{any} $d$-regular graph with $d\geq 3$, the largest component contains less than $An^{2/3}$ with probability at least $1-3c_d/A^{3/2}$, for some explicit constant $c_d$ which depends on $d$.