Talks
Spring 2016

Extremal Cuts of Sparse Random Graphs

Monday, May 2nd, 2016 4:00 pm4:45 pm

Add to Calendar

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.

AttachmentSize
PDF icon Extremal Cuts of Sparse Random Graphs317.89 KB