= Forced merging of large components
{title2=$N_{\geq K}(G_m)\geq an\Rightarrow L_1(G_{m+\lceil A(a)n/K\rceil})\geq an/3$}
For the two-choice <Achlioptas process>, fix $a>0$ and $K\geq1$. Conditional on any current <graph> with $N_{\geq K}\geq an$, put $W$ equal to the <vertices> in its large <graph components>. There are at most $n/K$ such initial <graph components>. If after $s$ more steps no <graph component> contains $an/3$ <vertices> of $W$, greedily assign final <graph components> to two groups so that each meets at least $|W|/3\geq an/3$ <vertices> of $W$. This induces a <set partition> of the initial large <graph components>, of which there are at most $2^{n/K}$ possibilities.
For any fixed such split $W=A\cup B$, a uniform candidate <edge> joins $A$ to $B$ with <probability> at least $2a^2/9$. If both candidates do so, the selected <edge> cannot avoid the crossing. Thus the <probability> that the split survives all $s$ steps is at most $(1-a^4/81)^s$. The deliberately weaker constant also covers distinct candidate sampling for sufficiently large $n$. In the absent-edge version, as long as the split has survived, every $A$--$B$ <edge> is absent, so conditioning on absence can only increase this crossing <probability>. A <union bound> with $s=\lceil A(a)n/K\rceil$ and $A(a)=81(\log2+2)/a^4$ bounds failure by $e^{-2n/K}$. For fixed $K$, a further <union bound> makes the conclusion simultaneous over all starting steps $m\leq3n$. This proof is independent of how the rule chooses between the two candidates.
Back to article page
