= Simultaneous giant for fixed random-edge choice
{title2=$\mathbb P(\forall\omega\in[k]^{cn}:L_1(G_\omega)\geq2n/3)\to1$}
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)]>\log2$ suffices. The guarantee is simultaneous even for choices made after seeing every offered <edge>.
Back to article page
