= Solution
Use the standard <Achlioptas process> with two independent uniform candidate <edges> per step and a rule choosing one. The <component-band vertex count> $N_{[k,Dk)}$ counts <vertices>, not the number of <graph components>. Integer time rounding changes the arguments below by $O(1)$ steps.
First, at $t_k$ the eventual <graph component> of order at least $\delta n$ is assembled from <graph components> already present at $t_k$. Contract those initial <graph components>. During $s=t_c-t_k$ steps, at most $s$ new <edges> are added, so the eventual connected contracted <graph> contains at most $s+1$ initial <graph components>. Initial <graph components> of order less than $k$ can therefore contribute at most
$$
(s+1)(k-1)\leq\delta n/2
$$
<vertices>, for sufficiently large $n$ and fixed $k$, since $s=\delta n/(2k)+O(1)$. For $k=1$ their contribution is zero. Consequently $N_{\geq k}(G_{t_k})\geq\delta n/2$.
We now use <forced merging of large components>. If at a time $m$ the <graph components> of order at least $K$ contain at least $an$ <vertices>, then after at most $A(a)n/K+O(1)$ steps there is a <graph component> of order at least $an/3$, except on an event of <probability> exponentially small in $n/K$. One explicit choice is $A(a)=81(\log2+2)/a^4$. The proof is a <union bound> over <set partitions> of the at most $n/K$ initial large <graph components>: if all final <graph components> were small, a <balanced component cut> would split their initial <vertices> into sets of size at least $an/3$, and both candidate <edges> cross that fixed cut with <probability> at least $a^4/81$ in every step. The rule cannot avoid such a forced crossing. The failure bound is $e^{-2n/K}$, and a <union bound> makes the estimate simultaneous over all starting times at most $3n$, for each fixed $K$.
Set $a=\delta/4$ and choose a fixed integer $D\geq2$ with $D\geq4A(a)/\delta$. If $N_{\geq Dk}(G_{t_k})\geq\delta n/4$, this lemma would produce a <graph component> of order at least $\delta n/12$ by time
$$
t_k+\frac{A(a)n}{Dk}+O(1)\leq t_c-\frac{\delta n}{4k}+O(1)<t'_c.
$$
That contradicts the assumed $L_1(G_{t'_c})=o(n)$. Thus $N_{\geq Dk}(G_{t_k})<\delta n/4$, and subtraction gives
$$
\boxed{N_{[k,Dk)}(G_{t_k})\geq\delta n/4\quad\text{with high probability}.}
$$
The same $D$ works for every fixed $k$; it depends only on $\delta$, with the number of offered <edges> fixed at two.
Back to article page
