= Barely-supercritical largest-component expectation
{title2=$\mathbb EL_1(G(n,(1+\varepsilon)/n))\sim2\varepsilon n$}
Suppose $\varepsilon=o(1)$ and $\varepsilon\geq n^{-1/6}$. The <breadth-first exploration of a binomial random graph> has deterministic drift $F(t)=\varepsilon t-t^2/(2n)+O(\varepsilon^3n+\varepsilon)$ up to $3\varepsilon n$ steps. Its weighted <martingale> has <variance> $O(\varepsilon n)$. For $h=\sqrt\varepsilon+(n\varepsilon^3)^{-1/8}$, the <Doob L2 maximal inequality> makes its maximum smaller than $h\varepsilon^2n/6$ <with high probability>. Then $A_t>0$ throughout $[h\varepsilon n,(2-h)\varepsilon n]$, giving a <graph component> of order $(2-o(1))\varepsilon n$.
For the upper expectation bound, let $K=\lceil\varepsilon^{-3}\rceil$. The dominating <binomial branching process> has <branching survival probability> $(2+o(1))\varepsilon$ by the <binomial branching survival correction>. Its <branching process conditioned on extinction> has mean $1-\varepsilon+O(\varepsilon^2+\varepsilon/n)$ and total-progeny <expected value> $O(1/\varepsilon)$. Therefore $\mathbb EN_{\geq K}\leq n\rho+O(n/(\varepsilon K))$. Since $L_1\leq K+N_{\geq K}$ and $K=o(\varepsilon n)$, this yields the matching upper bound. Controlling rare large components is necessary to conclude an <expected value> asymptotic from a typical-size statement.
Back to article page
