Extremal Cuts of Sparse Random Graphs
Extremal Cuts of Sparse Random Graphs

Amir Dembo , Stanford University
Fine Hall 214
The MaxCut problem seeks to determine the maximal cut size in a given graph. With no polynomialtime efficient approximation for MaxCut (unless P=NP), its asymptotic for a typical large sparse graph is of considerable interest. We prove that for uniformly random dregular graph of N vertices, and for the uniformly chosen ErdosRenyi graph of M=N d/2 edges, the leading correction to M/2 (the typical cut size), is P_* sqrt(N M/2). Here P_* is the ground state energy of the SherringtonKirkpatrick model, expressed analytically via Parisi's formula. This talk is based on a joint work with Subhabrata Sen and Andrea Montanari.