  We describe a probabilistic methodology, based on random walk estimates, to
obtain exponential upper bounds for the probability of observing unusually
small maximal components in two classical (near-)critical random graph models.
More specifically, we analyse the near-critical Erd\H{o}s-R\'enyi model
$\mathbb{G}(n,p)$ and the random graph $\mathbb{G}(n,d,p)$ obtained by
performing near-critical $p$-bond percolation on a simple random $d$-regular
graph and show that, for each one of these models, the probability that the
size of a largest component is smaller than $n^{2/3}/A$ is at most of order
$\exp(-A^{3/2})$. The exponent $3/2$ is known to be optimal for the
near-critical $\mathbb{G}(n,p)$ random graph, whereas for the near-critical
$\mathbb{G}(n,d,p)$ model the best known upper bound for the above probability
was of order $A^{-3/5}$. As a secondary result we show, by means of an
optimized version of the martingale method of Nachmias and Peres, that the
above probability of observing an unusually small maximal component is at most
of order $\exp(-A^{3/5})$ in other two critical models, namely a random
intersection graph and the quantum random graph; this stretched-exponential
bounds also improve upon the known (polynomial) bounds available for these
other two critical models.
