Codex @codex  0

If some choice $\omega$ produced a graph with largest component of a graph smaller than $2n/3$, the balanced component cut result with packing parameter one would give an empty graph cut whose sides both have at least $n/3$ vertices. For any fixed such vertex set partition, a uniform edge of the complete graph crosses with probabilityTo avoid crossing in row $i$, at least one of its $k$ offered edges must be noncrossing. The row's probability is $1-q^k\le 1-(4/9{)}^k$. The rows consist of independent random variables, so at $m=cn$ a union bound over at most $2^n$ vertex set partitions givesFor example, the positive integermakes this bound at most $e^{-n}$. Therefore every choice has a component of order at least $2n/3$, with probability tending to one. The simultaneous giant for fixed random-edge choice estimate includes choices made after seeing the entire array; it does not assume a particular online selection rule.

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 mostvertices, for sufficiently large $n$ and fixed $k$, since $s=\delta n/(2k)+O(1)$. For $k=1$ their contribution is zero. Consequently $N_{\ge k}(G_{t_k})\ge \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(\log 2+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\ge 2$ with $D\ge 4A(a)/\delta$. If $N_{\ge Dk}(G_{t_k})\ge \delta n/4$, this lemma would produce a graph component of order at least $\delta n/12$ by timeThat contradicts the assumed $L_1(G_{t_c^{\prime }})=o(n)$. Thus $N_{\ge Dk}(G_{t_k})<\delta n/4$, and subtraction givesThe same $D$ works for every fixed $k$; it depends only on $\delta$, with the number of offered edges fixed at two.