Extremal Cuts of Sparse Random Graphs

ACO Seminar
Monday, October 5, 2015 - 1:05pm for 1 hour (actually 50 minutes)
Skiles 006
Amir Dembo – Stanford University
Prasad Tetali
The Max-Cut problem seeks to determine the maximal cut size in a given graph. With no polynomial-time efficient approximation for Max-Cut (unless P=NP), its asymptotic for a typical large sparse graph is of considerable interest. We prove that for uniformly random d-regular graph of N vertices, and for the uniformly chosen Erdos-Renyi 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 Sherrington-Kirkpatrick model, expressed analytically via Parisi's formula. This talk is based on a joint work with Subhabrata Sen and Andrea Montanari.