Mean number of edges between two equal partitions

Question

For a random undirected graph with $n$ nodes, where each node has $k$ incident edges ($nk/2$ edges in total), the vertex set is partitioned into two sets each having $n/2$ nodes.

What is the order of the number of edges that start in one partition and end in the other?

My back of the napkin calculation is half of total number of edges, $nk/4$. If I place randomly an edge it has $1/4$ chance of having both ends in one partition, $1/4$ chance of having both ends in the other partition and $1/2$ chance of having the ends in both. I find it surprising that it could be half.

Answer 1

Your thinking is correct. To verify your claim you can check this lecture notes on the probabilistic method by Matousek and Vondrak. More specifically check the proof of Theorem 3.3.1 stating that any graph with $m$ edges contains a bipartite subgraph with $\frac{m}{2}$ edges.