2 edited title

1

Max cut in a random graph

Let $G = G(n, 1/2)$ be an Erdos-Renyi graph in which each edge $e = (u,v)$ is present in the graph independently with probability $1/2$. For a subset of the vertices $S$, the cut value $c(S)$ is equal to the number of edges $(u,v)$ such that $u \in S$ and $v \not \in S$.

Clearly for any particular cut $S$, the expected value of $c(S)$ is $E[c(S)] = |S|\cdot|\bar{S}|/2 \leq n^2/8$.

By a Chernoff bound, the probability that any particular cut exceeds its expectation by an additive factor of $O(tn)$ is exponentially decreasing in $t^2$. By taking $t = \sqrt{n}$ and taking a union bound over all $2^n$ possible cuts $S$, we can see that with high probability:

$$\max_S \ c(S) \leq E[c(S)] + O(n^{3/2}) \leq n^2/8 + O(n^{3/2})$$

This naive analysis seems loose. My question is, can the $O(n^{3/2})$ term be improved asymptotically, or is this actually tight?