Mean cut size in generated graphs

Question

Assume an undirected simple graph $G=(V,E)$ is created randomly: an edge $e=(u,v)$ is in $E$ with probability $p$, independent of other edges.

Assume we select a random cut $(S,T = V\setminus S)$ in the graph. What is the expected value of its size? (The size of the cut is the number of edges $(u,v)\in E, u\in S, v\in T$)

I have made an attempt with the following approach: the maximal possible size of such a cut is $|S|\cdot|T|$ (every vertex in $S$ is connected to every vertex in $T$). So the mean cut can be calculated as follows:

$$\sum_{i=0}^{|S|\cdot|T|}i \cdot P(\text{size of the cut is } i)$$

However, I am having difficulty with $P(\text{size of the cut is } i)$. Somehow I must refer to the total number of edges. It is the probability that an edge $(u,v)$ exists ($p$), and that $u \in S$ and $v\in T$ (the probability that $u\in S, v\in T$ are not given...) and that all other edges do not satisfy any of those three conditions. Therefore, this sounds like an infeasible approach.

Answer 1

This sort of depends on how you select the random cut. We might do it uniformly: for every vertex $v$, we put $v \in S$ with probability $\frac12$, $v \in T$ otherwise, and make this decision independently for all vertices.

If we fix the cut $(S,T)$, then the formula $$\mathbb E[\text{size of $(S,T)$ cut}] = \sum_{i=0}^{|S||T|} i \cdot \Pr[\text{size is }i]$$ is valid, but it's much easier to approach this by linearity of expectation: each of the $|S||T|$ edges is present with probability $p$, so the expected number of edges present is $p|S||T|$.

This is a formula that depends on $S$ and $T$ (or rather, on their sizes). To get the overall formula, we can substitute the previous result into the summation

$$\mathbb E[\text{size of cut}] = \sum_{S \subseteq [n]} \mathbb E[\text{size of $(S,[n]\setminus S)$ cut}] \cdot \Pr[\text{the cut is }(S,[n]\setminus S)].$$

In the case where $S$ is chosen uniformly from all subsets of $[n]$, this is $$\sum_{S \subseteq [n]} p |S|(n-|S|) \cdot 2^{-n} = \sum_{k=0}^n pk(n-k) \binom nk 2^{-n}$$ where we get the second sum by grouping the sets $S$ together by size. This simplifies to $\frac14 n(n-1)p$.

We can also get this result much more directly by observing that each edge of the graph $G$ is present with probability $p$, and its endpoints end up on different sides of the cut with probability $\frac12$, so it ends up contributing $1$ to the size of the cut with probability $\frac p2$. By linearity of expectation, the size of the cut is $\frac p2 \binom n2 = \frac14 n(n-1)p$.