  We consider the problem of estimating the size of a maximum cut (Max-Cut
problem) in a random Erd\H{o}s-R\'{e}nyi graph on $n$ nodes and $\lfloor cn
\rfloor$ edges. It is shown in Coppersmith et al. ~\cite{Coppersmith2004} that
the size of the maximum cut in this graph normalized by the number of nodes
belongs to the asymptotic region $[c/2+0.37613\sqrt{c},c/2+0.58870\sqrt{c}]$
with high probability (w.h.p.) as $n$ increases, for all sufficiently large
$c$.
  In this paper we improve both upper and lower bounds by introducing a novel
bounding technique. Specifically, we establish that the size of the maximum cut
normalized by the number of nodes belongs to the interval
$[c/2+0.47523\sqrt{c},c/2+0.55909\sqrt{c}]$ w.h.p. as $n$ increases, for all
sufficiently large $c$. Instead of considering the expected number of cuts
achieving a particular value as is done in the application of the first moment
method, we observe that every maximum size cut satisfies a certain local
optimality property, and we compute the expected number of cuts with a given
value satisfying this local optimality property. Estimating this expectation
amounts to solving a rather involved two dimensional large deviations problem.
We solve this underlying large deviation problem asymptotically as $c$
increases and use it to obtain an improved upper bound on the Max-Cut value.
The lower bound is obtained by application of the second moment method, coupled
with the same local optimality constraint, and is shown to work up to the
stated lower bound value $c/2+0.47523\sqrt{c}$. It is worth noting that both
bounds are stronger than the ones obtained by standard first and second moment
methods.
  Finally, we also obtain an improved lower bound of $1.36000n$ on the Max-Cut
for the random cubic graph or any cubic graph with large girth, improving the
previous best bound of $1.33773n$.
