Persistence of unsampled graph components ($N_{[k,Dk)}\ge \alpha n\Rightarrow N_{[k,Dk)}\ge \beta n\text{ later}$)

Fix positive $\alpha$, $D\ge 2$ and $B>0$. Suppose a size band $[k,Dk)$ of an Achlioptas process contains at least $\alpha n$ vertices at time $m$. For every fixed $k$, at least $\beta n$ of those vertices remain in unchanged graph components throughout the next $T=\lceil Bn/k\rceil$ steps, with high probability, where one may take $\beta =\alpha e^{-16BD}/4$. This is a deliberately nonoptimal positive constant.

For independent uniform candidate edges, an initial graph component with $w<Dk$ vertices is untouched if none of the $2T$ candidate edges meets it. A uniform edge hits it with probability at most $3w/n$. For sufficiently large $n$, $(1-3w/n{)}^{2T}\ge e^{-16BD}$, so the expected value of the untouched vertex mass $Y$ is at least $\alpha e^{-16BD}n$. Replacing one row of two candidate edges can change $Y$ by at most $8Dk$, because only the initial graph components hit by an old or new endpoint can change status. The McDiarmid inequality therefore makes $Y\ge \alpha e^{-16BD}n/2$ except on an event of probability $e^{-cn/k}$, for a positive constant $c$ depending only on $\alpha ,B,D$. An untouched graph component stays unchanged whichever offered edge is selected.

For candidates restricted to absent edges, generate each by an independent uniform proposal stream and reject already present edges. During any interval of $O(n)$ steps with $O(n)$ present edges, each proposal has rejection probability $O(1/n)$ conditional on the past. The number of rejections is at most $O(\log n)$ except on an event of probability smaller than any inverse power of $n$: if there were $r$ rejections among $2T+r$ proposals, a union bound over their positions bounds this by $\left(\genfrac{}{}{0ex}{}{2T+r}{r}\right)(C/n{)}^r$. The first $2T$ proposals are independent and give the previous untouched-mass estimate. Extra proposals can touch at most $2r$ additional initial graph components, losing only $O(Dk\log n)=o(n)$ vertices for fixed $k$. This leaves the stated $\beta n$ bound. A union bound makes these estimates simultaneous over starting times $m\le 3n$. They hold through the entire interval, so deterministic or random stopping times within it are allowed.