= Solution
Put $d=np=\gamma\log n$ and $\mu=n^{1-\gamma}$. The hypothesis implies $\mu\geq e^{\omega(n)}\to\infty$. For the number $I$ of <isolated vertices>, the <isolated vertices in the Erdős-Rényi model> formulas give
$$
\mathbb EI=n(1-p)^{n-1}=(1+o(1))\mu,\qquad
\frac{\operatorname{var}I}{(\mathbb EI)^2}\leq\frac1{\mathbb EI}+\frac p{1-p}=o(1).
$$
Thus the <Chebyshev inequality> gives $I=(1+o(1))\mu$ <with high probability>, uniformly over the specified $\gamma$ range.
The <Cayley formula> supplies a <spanning tree> on any connected vertex set. Consequently the <expected value> $C_j$ of the number of <graph components> of order $j\geq2$ is bounded by
$$
\mathbb EC_j\leq\binom nj j^{j-2}p^{j-1}(1-p)^{j(n-j)}.
$$
Choose a fixed $\eta\in(0,1/2)$ with $\gamma_0(1-\eta)(k+1)>1$. For $k+1\leq j\leq\eta n$, with $j\geq2$, the <binomial coefficient> bound $\binom nj\leq(en/j)^j$ gives
$$
\mathbb EC_j\leq\frac n{d j^2}\left(ed\,e^{-d(1-\eta)}\right)^j.
$$
Here $ed\,e^{-d(1-\eta)}\leq e\log n\,n^{-\gamma_0(1-\eta)}\to0$. The <geometric series> and a <union bound> therefore exclude this entire size range, since $n[ e\log n\,n^{-\gamma_0(1-\eta)}]^{k+1}=o(1)$. For $\eta n\leq j\leq n/2$, an empty <graph cut> would be necessary. Its total <probability> is at most
$$
2^n e^{-p\eta n^2/2}=o(1).
$$
There are consequently no <graph components> of orders between $k+1$ and $n/2$, <with high probability>.
For each fixed $2\leq j\leq k$, a <graph component> containing a <graph cycle> has a <spanning tree> and at least one extra <edge>. Counting that extra <edge> gives an <expected value> $O_k(d^j e^{-dj})=o(1)$; hence every small <graph component> is a <tree component>. The total number $R_2$ of <vertices> in <tree components> of orders $2,\ldots,k$ satisfies
$$
\mathbb ER_2=O_k\left(n d e^{-2d}\right)=O_k(\mu d e^{-d})=o(\mu).
$$
The <Markov inequality> gives $R_2=o(\mu)$ <with high probability>. When $k=1$, this sum is empty and $R_2=0$. Since $\mu=o(n)$, the remaining <vertices> must lie in one <graph component> larger than $n/2$. It is unique, and its order is \b[$n-(1+o(1))n^{1-\gamma}$]. Every other <graph component> is a <tree> with at most $k$ <vertices>. This is the <logarithmic-regime giant component> mechanism: almost all missing <vertices> are isolated.
Back to article page
