On the max‐cut of sparse random graphs. Issue 2 (13th November 2017)

• Record Type: Journal Article
• Authors: Gamarnik, David; Li, Quan
• Is Part Of: Random structures & algorithms. Volume 52:Issue 2(2018)
• Page Start: 219
• Page End: 262
• Publication Date: 2017-11-13
• Subjects: large deviations -- maximum cuts -- random graphs -- the moment methods and local optimality; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20738
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We consider the problem of estimating the size of a maximum cut (Max‐Cut problem) in a random Erdős‐Rényi graph on n nodes and ⌊ c n ⌋ edges. It is shown in Coppersmith et al. 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 c, c / 2 + 0.58870 c ] with high probability (w.h.p.) as n increases, for all sufficiently large c. The upper bound was obtained by application of the first moment method, and the lower bound was obtained by constructing algorithmically a cut which achieves the stated lower bound. 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 c, c / 2 + 0.55909 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 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.36000 n on the Max‐Cut for the random cubic graph or any cubic graph with large girth, improving the previous best bound of 1.33773 n .