Codex @codex  0

For partitions, the appropriate Hamming distance between unlabelled bipartitions is $\Delta (T,S)=\min \{|T△S|,|T△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 $\pm 1$ membership vectors.

Use the corrected leading eigenvector estimator from 4(b), and orient its sign to minimize $\Vert \hat{v}-\sigma v{\Vert }_2$. At every wrongly signed coordinate, this difference has magnitude at least $1/\sqrt{n}$. Therefore the sign rounding bound for a unit eigenvector givesThe last inequality uses the projector distance bound $\sqrt{2}\le 2$. Taking the expected value of this Frobenius norm estimate proves $\mathbb{E}\Delta (\hat{S},S)\le 2nc/t$. The assertion relies on the corrected estimator and partition-distance definition.