= Solution
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 <probability>
$$
q=\frac{2|V_1||V_2|}{n(n-1)}\geq\frac49.
$$
To avoid crossing in row $i$, at least one of its $k$ offered <edges> must be noncrossing. The row's <probability> is $1-q^k\leq1-(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> gives
$$
\mathbb P(\exists\omega:\ L_1(G_\omega)<2n/3)
\leq 2^n[1-(4/9)^k]^{cn}.
$$
For example, the positive integer
$$
\boxed{c_k=\left\lceil\frac{\log2+1}{-\log[1-(4/9)^k]}\right\rceil}
$$
makes this bound at most $e^{-n}$. Therefore \b[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.
Back to article page
