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.

Let $a=kn/(2k+1)$, $u=(k+1)n/(2k+1)$ and $b=u/k$. A graph cut with no crossing edges is obtained by assigning whole graph components to its two sides. Among all such assignments, maximize the smaller side's size $S\le n/2$, and write $T=n-S$ for the other side.

Suppose $S<a$. Then $T>u=kb$. If a graph component on the larger side had size $0<w<n-2S$, moving it to the smaller side would make both $S+w$ and $T-w$ greater than $S$. That contradicts maximality. Hence every graph component on the larger side has at least $n-2S$ vertices. Since each has at most $b$ vertices and their total exceeds $kb$, there must be at least $k+1$ of them. Consequentlya contradiction. Thus $a\le S\le T\le u$, proving the required empty cut with both sides at most $(k+1)n/(2k+1)$. This balanced component cut argument works for arbitrary positive component weights as well; it does not require divisibility of $n$.

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.

Offer $k$ independent uniform edges of the complete graph per row and permit any one to be selected from each row. If a chosen graph has no graph component of order at least $2n/3$, the balanced component cut provides an empty cut whose sides both have at least $n/3$ vertices. Each candidate edge crosses that cut with probability at least $4/9$, so a row can avoid crossing with probability at most $1-(4/9{)}^k$. The union bound over at most $2^n$ cuts gives failure probability at most $2^n[1-(4/9{)}^k{]}^{cn}$. Any fixed integer $c$ with $c[-\log (1-(4/9{)}^k)]>\log 2$ suffices. The guarantee is simultaneous even for choices made after seeing every offered edge.