Achlioptas process ($G_{m+1}=G_m\cup \{e_{m,{\omega }_m}\}$)

At each step offer a fixed number of independent uniform candidate edges on a fixed vertex set, and let a rule select one. The standard two-choice model offers two candidates. The rule may depend on the entire previously exposed history. Repeated already present edges make no change in the independent-candidate version; another usual version offers only absent edges. The forced merging of large components and persistence of unsampled graph components apply to both over a linear number of steps. Fixed choice is essential in the continuity of fixed-choice percolation argument.

A fixed-choice Achlioptas process cannot have its largest component of a graph jump from $o(n)$ to a fixed positive fraction of $n$ within $o(n)$ steps, with high probability. The proof combines forced merging of large components and persistence of unsampled graph components. An assumed jump forces positive vertex mass in each band $[k,Dk)$ slightly before the jump: insufficient smaller components can feed the final large component, while enough components above $Dk$ would merge too early. Persistence carries a fixed positive amount of each band to a common time. Taking sufficiently many disjoint bands with $k=1,D,D^2,\dots$ then counts more than $n$ vertices. The number of offered candidates is fixed throughout this argument. Riordan and Warnke establish this obstruction and broader continuity results in their original research paper.

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.

For the two-choice Achlioptas process, fix $a>0$ and $K\ge 1$. Conditional on any current graph with $N_{\ge K}\ge 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\ge 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(\log 2+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\le 3n$. This proof is independent of how the rule chooses between the two candidates.

This is the total number of vertices in graph components with orders in the specified half-open interval. It differs from the number of those graph components. Write $N_{\ge k}$ for the total above the lower endpoint. Then $N_{[k,\ell )}=N_{\ge k}-N_{\ge \ell }$. Disjoint size bands count disjoint sets of vertices at a common time, even though their mass may move between bands as an Achlioptas process adds edges.