# Mean cut size in generated graphs

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.

• Is this reference pertinent : (people.maths.ox.ac.uk/scott/Papers/planted.pdf) ? – Jean Marie Oct 27 '17 at 18:12
• From an initial look, I do not think so. The paper revolves around vertex classes, while I am referring to simple cuts. – TheNotMe Oct 27 '17 at 18:15

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

• I have a question regarding the last approach. "it ends up contributing $1$ to the size... with probability $\frac{p}{2}$", that I understand. How did we get the ${{n}\choose{2}}$ factor from the linearity of expectation? – TheNotMe Oct 30 '17 at 7:30
• There are $\binom n2$ potential edges. – Misha Lavrov Oct 30 '17 at 14:45
• Hi, first of all thanks for all these instructive answers. I was if you'd be potentially interested in this recent post: math.stackexchange.com/questions/2960593/… I feel sort of lost, have no clue how to tackle the question if i'm honest (even in the case of a finite example). Your help would be very valuable. – user929304 Oct 18 '18 at 10:56