= Solution
Assume $0<\lambda=1-\varepsilon<1$, as required for this nontrivial subcritical <binomial random graph>. Put $\delta=\lambda-1-\log\lambda>0$. A <breadth-first exploration of a binomial random graph> is dominated by a <Galton-Watson process> whose offspring counts are <independent random variables> with law $\operatorname{Bin}(n,\lambda/n)$. If its <total progeny> $T$ is at least $j$, the first $j-1$ offspring counts sum to at least $j-1$. Their <moment-generating function> is bounded by that of a <Poisson distribution> of mean $\lambda(j-1)$. The exponential <Markov inequality>, optimized at $t=-\log\lambda$, yields
$$
\mathbb P(T\geq j)\leq e^{-\delta(j-1)}.
$$
Taking $j=\lceil(1+\eta)\log n/\delta\rceil$ for any fixed $\eta>0$, a <union bound> over all starting <vertices> gives $\mathbb P(L_1\geq j)=o(1)$.
For the matching lower bound, let $X_j$ count <tree components> of order $j$. The <tree-component expectation in the Erdős-Rényi model> is exactly
$$
\mathbb EX_j=\binom nj j^{j-2}p^{j-1}(1-p)^{j(n-j)+\binom j2-j+1}.
$$
For $j=O(\log n)$, the <Stirling formula> gives
$$
\mathbb EX_j=(1+o(1))\frac{n}{\lambda\sqrt{2\pi}\,j^{5/2}}e^{-\delta j}.
$$
Choose $j=\lfloor(1-\eta)\log n/\delta\rfloor$, with $0<\eta<1$. Then $\mathbb EX_j\to\infty$. Distinct overlapping vertex sets cannot both be <graph components>. For disjoint sets, the joint <probability> differs from the product only because the $j^2$ between-set <edges> were counted twice as absent. Thus
$$
\frac{\mathbb E[X_j(X_j-1)]}{(\mathbb EX_j)^2}
=\frac{\binom{n-j}j}{\binom nj}(1-p)^{-j^2}
=1+O(j^2/n).
$$
It follows that $\operatorname{var}X_j/(\mathbb EX_j)^2=o(1)$. The <second moment method> gives $X_j>0$ <with high probability>. Combining both bounds, and then taking arbitrarily small fixed $\eta$, proves the <sharp subcritical largest-component scale>
$$
\boxed{L_1=(1+o(1))\frac{\log n}{\delta}=(1+o(1))\ell_0\quad\text{with high probability}.}
$$
Finally the <Taylor expansion> of $-\log(1-\varepsilon)$ gives $\delta=\varepsilon^2/2+\varepsilon^3/3+\cdots$. The endpoint $\lambda=0$ has no <edges> and is excluded from this logarithmic asymptotic.
Back to article page
