Past exam of the mathematics course of the University of Cambridge / 2012 / iii / Paper 9 / 2

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$.

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.