= Solution
For partitions, the appropriate <Hamming distance between unlabelled bipartitions> is $\Delta(T,S)=\min\{|T\mathbin\triangle S|,|T\mathbin\triangle S^c|\}$. It counts vertices assigned to the wrong group after the better global exchange of the two group names. The printed signed-indicator formula does not implement this exchange: negating a zero-one indicator is not taking its complement. It must be read as this partition distance, or written with the $\pm1$ membership vectors.
Use the corrected leading <eigenvector> estimator from 4(b), and orient its sign to minimize $\|\widehat v-\sigma v\|_2$. At every wrongly signed coordinate, this difference has magnitude at least $1/\sqrt n$. Therefore the <sign rounding bound for a unit eigenvector> gives
$$
\Delta(\widehat S,S)\leq n\min_\sigma\|\widehat v-\sigma v\|_2^2\leq n\|\widehat v\widehat v^\top-vv^\top\|_F^2\leq2n\|\widehat v\widehat v^\top-vv^\top\|_F.
$$
The last inequality uses the projector distance bound $\sqrt2\leq2$. Taking the <expected value> of this <Frobenius norm> estimate proves \b[$\mathbb E\Delta(\widehat S,S)\leq2nc/t$]. The assertion relies on the corrected estimator and partition-distance definition.
Back to article page
