New upper bounds for the MAX CUT problem - Zhou, Guangyan (Global Journal of Mathematical Analysis, 2014)
Let f_cut(n,cn) be the expectation of the value of the maximum cut of a given random graph G(n,cn) with n vertices and cn edges. We study the asymptotic change of f_cut(n,cn)/cn as n tends to infinity with various densities c. In this paper, we provide new upper bounds by correcting the error items when applying the first moment method. Specifically, we extrapolate the region of c from c>1.386 to c>1.001. Keywords: MAX CUT, Upper Bound, Random Graph, First moment method.