= Conditional expectations for maximum cut
Let $G=(V,E)$ be a finite undirected <simple graph>, with $n=|V|$ <vertices> and $m=|E|$ <edges>. A <cut of a graph> assigns each <vertex> a label zero or one; an <edge> crosses precisely when its endpoints have different labels. Its size is the number of crossing <edges>. A <maximum cut> maximizes that size.
For the analysis, assign <independent> fair <bits> $X_v$ to the <vertices>. For each <edge> $uv$, the <indicator random variable> $I_{uv}=\mathbf1_{\{X_u\ne X_v\}}$ has <expected value> $1/2$: exactly two of the four equally likely endpoint assignments cross. Thus <linearity of expectation> gives the <random cut lower bound>:
$$
C=\sum_{uv\in E}I_{uv},\qquad \mathbb E C=\sum_{uv\in E}\frac12=\frac m2.
$$
<Linearity of expectation> does not require the <indicator random variables> to be <independent>. What matters here is the stipulated distribution of the endpoint <bits>.
Back to article page
