Max cut value 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? 
 A: 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.
A: Sounds pretty credible to me. I'm reminded of the Alon/Spencer/Erd"os book "The Probabilistic Method" where they're addressing the clique number of a random graph. Again it's easy to see the probability that a particular clique is present. They then work quite hard giving counting and independence estimates for different potential cliques. Your situation sounds very similar. My guess would be that enough of the cuts are independent enough for you to pretend that their cut values are independent. Then if each one (of the roughly balanced cuts) has value $n^2/8\pm N$ where $N$ is normal with mean 0 and variance $\approx n^2$, the max of $2^n$ of these should be determined by the value that the normal takes with probability $2^{-n}$, namely $\Theta(n^{3/2})$.
