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? 



Max cut value in a random graph
This is addressed in:


An upper bound for the maximum cut mean value
Alberto Bertoni, Paola Campadelli and Roberto Posenato


Their bound is the same as yours; more precisely, for a random graph with $n$ vertices and $x n$ edges, for sufficiently large $x,$ they claim the size of max cut divided by $x n$ is bounded above by


$$\frac12 + \frac1{\sqrt{x}} + \frac12 \frac{\log x}{x},$$


so I assume this is tight.


**EDIT**


A matching lower bound is provided in
MR2060633 (2005c:68088) 
Coppersmith, Don(1-IBM); Gamarnik, David(1-IBM); Hajiaghayi, Mohammad Taghi(1-MIT); Sorkin, Gregory B.(1-IBM)
Random MAX SAT, random MAX CUT, and their phase transitions. (English summary) 
Random Structures Algorithms 24 (2004), no. 4, 502–545. 
68Q25 (60C05 68T20 68W40 82B26 82B44) 


See Theorem 20.


